Мемоизация

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Norvig, Peter Techniques for Automatic Memoization with Applications to Context-Free Parsing // Computational Linguistics. — 1991. — Т. 17, № 1. — С. 91–98.