Мемоизация

Термин «мемоизация» был введён Дональдом Мичи в 1968 году^[3] и происходит от латинского слова лат. memorandum («то, что следует помнить»), обычно сокращаемого до «memo» в американском английском. Термин подразумевает «превращение [результатов] функции в нечто запоминаемое».

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

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

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

Рассмотрим следующий пример на псевдокоде для вычисления факториала числа n:

function factorial (n — неотрицательное целое)
    if n равно 0 then
        return 1 [по соглашению 0! = 1]
    else
        return factorial(n – 1) умножить на n [рекурсивный вызов]
    end if
end function

Для каждого целого n ≥ 0 итоговый результат вычислений функции всегда инвариантен (например, вызов x = factorial(3) всегда даст x = 6). Нереализованный с мемоизацией вариант алгоритма осуществляет n + 1 вызов функции, каждый из которых требует дополнительных временных затрат, связанных с:

1. установкой фрейма стека вызова,
2. сравнением n с 0,
3. вычитанием 1 из n,
4. установкой нового фрейма стека для рекурсивного вызова,
5. умножением результата рекурсивного вызова на n,
6. сохранением результата для передачи в вызывающий контекст.

В такой реализации каждый вызов на верхнем уровне содержит совокупную стоимость перечисленных шагов, пропорциональную исходному значению n.

Мемоизированная версия функции factorial выглядит так:

function factorial (n — неотрицательное целое)
    if n равно 0 then
        return 1 [по соглашению 0! = 1]
    else если n есть в таблице поиска then
        return значение для n из таблицы
    else
        x = factorial(n – 1) умножить на n [рекурсивный вызов]
        сохранить x в таблице поиска в ячейку n
        return x
    end if
end function

В этом примере, если factorial вызывается с аргументом 5, а затем с любым меньшим или равным 5 значением, то все результаты уже будут сохранены в таблице, поскольку рекурсивные вызовы охватили значения от 5 до 0. При последующем вызове с большим числом, например, 7, рекурсивно требуется только два вызова (7 и 6), а значение для 5! будет использоваться из кэша. Таким образом, мемоизация позволяет функции работать всё быстрее по мере повторных вызовов.

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

Функциональные языки программирования и их компиляторы активно используют мемоизацию, особенно при указательной (call by name) стратегии вычислений. Для снижения накладных расходов на вычисление значений аргументов применяются функции-заглушки (thunks), которые мемоизируются для предотвращения повторных вычислений.

Мемоизация может быть реализована явно программистом внутри функции — как показано выше на примере factorial. Однако референциально прозрачные функции могут быть мемоизированы автоматически и внешне^[1]. Исследования Питера Норвига показывают, что техники автоматической мемоизации применимы не только в Common Lisp, но и в других языках программирования. Такие подходы рассматриваются, например, при анализе переписывания термов^[4] и в системах искусственного интеллекта^[5].

В языках, где функции являются объектами первого класса (например, Lua, Питон (Python), Perl^[6]), автоматическую мемоизацию можно реализовать путём подмены функции кэшированным значением при получении нового набора параметров. Функция-обёртка универсально мемоизирует любую референциально прозрачную функцию. Пример псевдокода:

function memoized-call (F — объект-функция)
    если у F нет массива values
        создать ассоциативный массив values;
        прикрепить values к F;
    end if;
    если F.values[аргументы] пусто
        F.values[аргументы] = F(аргументы);
    end if;
    вернуть F.values[аргументы];
end function

Чтобы воспользоваться автоматически мемоизированной функцией factorial, вместо обычного вызова используется вызов memoized-call(factorial)(n).

Для языков с поддержкой замыканий мемоизация может быть реализована через функцию-фабрику, возвращающую объект-обёртку (функтор), оборачивающий исходную функцию, зачастую с использованием шаблона «декоратор».

Когда нисходящий парсер пытается разобрать неоднозначный КС-грамматику, ему может потребоваться экспоненциальное число шагов, чтобы рассмотреть все варианты. Мемоизация была предложена в 1991 году Питером Норвигом как способ автоматизации построения мемо-таблиц для хранения промежуточных результатов во время разбора, что позволяет существенно снизить экспоненциальную сложность до полиномиальной^[1]. Подход близок к методам динамического программирования, используемым в алгоритме Эрли (1970), или таблицам в алгоритме Кока-Янгера-Касами (CYK).

Ричард Фрост и Барбара Шидловски также применяли мемоизацию для снижения экспоненциальной сложности комбинаторов-парсеров, добившись полиномиального времени работы и возможности использования выразительных спецификаций грамматик.^[7][8][9]

Мемоизация в контексте парсинга продолжала изучаться: в 1995 году в работах Марка Джонсона и Йохена Дёрре^[10][11], а в 2002 году — в работах Брайана Форда по packrat-парсингу^[12].

В 2007 году Фрост, Хафиз и Каллахан описали алгоритм нисходящего разбора с мемоизацией, обеспечивающий полиномиальную сложность разбора неоднозначных грамматик (Θ(n⁴) для лево-рекурсивных и Θ(n³) для не лево-рекурсивных грамматик). Решения по использованию мемоизации в парсерах существенно влияют на анализ естественного языка и синтаксис-ориентированные задачи.

В некоторых случаях мемоизация применяется не столько для ускорения, сколько для отсроченной проверки лингвистических ограничений при парсинге^[11]. В других же задачах (например, Packrat-парсинг) мемоизация может гарантировать линейную сложность разбора даже для классов языков, где обычно требуется бэктрекинг^[12].