Мемоизация

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

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

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

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

См. также

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