Мемоизация

Мемоизация (запоминание, от англ. memoization (англ.) в программировании) — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:

• если не вызывалась, функция вызывается и результат её выполнения сохраняется;
• если вызывалась, используется сохранённый результат.

Мемоизация может использоваться не только для увеличения скорости работы программы. Например, она используется при простом взаимно-рекурсивном нисходящем синтаксическом разборе в обобщённом алгоритме нисходящего синтаксического анализа.

Несмотря на связь с кешированием, мемоизация является особым видом оптимизации, отличающимся от таких способов кеширования, как буферизация и подмена страниц.

В рамках языков логического программирования мемоизация известна под названием «табулирования».

См. также

• Понижение силы операций — оптимизация, заменяющая дорогостоящие операции более дешёвыми эквивалентами.
• Таблица поиска — ключевая структура данных, используемая при мемоизации.
• Приспособленец (шаблон проектирования) — шаблон, использующий мемоизацию.
• Динамическое программирование — приложения техник мемоизации.
• Отложенные вычисления.

Отрывок, характеризующий Мемоизация

– L'Angleterre a vecu, [Англии конец,] – проговорил он, нахмуриваясь и указывая на кого то пальцем. – M. Pitt comme traitre a la nation et au droit des gens est condamiene a… [Питт, как изменник нации и народному праву, приговаривается к…] – Он не успел договорить приговора Питту, воображая себя в эту минуту самим Наполеоном и вместе с своим героем уже совершив опасный переезд через Па де Кале и завоевав Лондон, – как увидал входившего к нему молодого, стройного и красивого офицера. Он остановился. Пьер оставил Бориса четырнадцатилетним мальчиком и решительно не помнил его; но, несмотря на то, с свойственною ему быстрою и радушною манерой взял его за руку и дружелюбно улыбнулся.
– Вы меня помните? – спокойно, с приятной улыбкой сказал Борис. – Я с матушкой приехал к графу, но он, кажется, не совсем здоров.
– Да, кажется, нездоров. Его всё тревожат, – отвечал Пьер, стараясь вспомнить, кто этот молодой человек.
Борис чувствовал, что Пьер не узнает его, но не считал нужным называть себя и, не испытывая ни малейшего смущения, смотрел ему прямо в глаза.
– Граф Ростов просил вас нынче приехать к нему обедать, – сказал он после довольно долгого и неловкого для Пьера молчания.
– А! Граф Ростов! – радостно заговорил Пьер. – Так вы его сын, Илья. Я, можете себе представить, в первую минуту не узнал вас. Помните, как мы на Воробьевы горы ездили c m me Jacquot… [мадам Жако…] давно.
– Вы ошибаетесь, – неторопливо, с смелою и несколько насмешливою улыбкой проговорил Борис. – Я Борис, сын княгини Анны Михайловны Друбецкой. Ростова отца зовут Ильей, а сына – Николаем. И я m me Jacquot никакой не знал.
Пьер замахал руками и головой, как будто комары или пчелы напали на него.