19.5 Мемоизация

Мемоизация — это метод кэширования результатов медленных вызовов функций и возврата кэшированного значения при повторном вызове функции с теми же входными данными вместо повторного вычисления. Если одни и те же входные данные повторяются снова и снова известным и предсказуемым образом, часто вместо вызовов функций используют таблицы поиска. По сути, мемоизация — это развитие этой практики, при котором таблица поиска пополняется во время выполнения для новых аргументов, которые ранее не встречались. Основы теории можно найти в Википедии или в любом учебнике по информатике для студентов бакалавриата.

Функция memoize в Octave предоставляет готовую функциональность мемоизации для любой пользовательской функции или функции Octave, в том числе скомпилированной.

: mem_fcn_handle = memoize (fcn_handle)

Создать мемоизированную версию mem_fcn_handle функции fcn_handle.

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

Например, возьмём медленную пользовательскую функцию с именем slow_fcn и мемоизируем её, создав новый дескриптор cyc. Первые вызовы обеих версий занимают одинаковое время, но при последующих вызовах мемоизированной версии возвращается ранее вычисленное значение, поэтому время выполнения сокращается с 2,4 секунды до всего лишь 2,4 миллисекунды. Последняя проверка подтверждает, что обе версии вернули один и тот же результат.

>> tic; p = slow_fcn (5040); toc
Elapsed time is 2.41244 seconds.
>> tic; p = slow_fcn (5040); toc
Elapsed time is 2.41542 seconds.

>> cyc = memoize (@slow_fcn);
>> tic; r = cyc (5040); toc
Elapsed time is 2.42609 seconds.
>> tic; r = cyc (5040); toc
Elapsed time is 0.00236511 seconds.

>> all (p == r)
ans = 1

См. также: clearAllMemoizedCaches.

Чтобы мемоизировать функцию z = foo(x, y), используйте следующий общий шаблон:

foo2 = memoize (@(x, y) foo(x, y));
z = foo2 (x, y);

В приведённом выше примере первая строка создаёт мемоизированную версию foo2 функции foo. Для простых функций, требующих лишь минимальной обёртки, эту строку можно сократить до следующего вида:

foo2 = memoize (@foo);

Во второй строке z = foo2 (x, y); вызывается эта мемоизированная версия foo2 вместо исходной функции, что позволяет memoize перехватить вызов и заменить его значением, найденным в таблице, если такие входные данные уже встречались, вместо повторного вычисления исходной функции.

Обратите внимание, что это не ускорит первый вызов функции, а только последующие.

Обратите внимание, что из-за накладных расходов, необходимых memoize для создания таблиц поиска и управления ими для каждой функции, этот метод полезен только для функций, выполнение которых занимает как минимум пару секунд. Такие функции можно заменить поиском по таблице, который занимает всего около миллисекунды. Но если исходная функция выполнялась всего несколько миллисекунд, её мемоизация не приведёт к ускорению.

Рекурсивные функции также можно мемоизировать, используя шаблон следующего вида:

function z = foo (x, y)
  persistent foo2 = memoize (@foo);
  foo2.CacheSize = 1e6;

  ## Call the memoized version when recursing
  z = foo2 (x, y);
endfunction

Значение CacheSize можно при необходимости увеличить, если ожидается большое количество вызовов функции, например из рекурсивной функции. Если значение CacheSize превышено, таблицы мемоизации изменяют размер, что приводит к замедлению работы. Таким образом, увеличение значения CacheSize действует как предварительное выделение памяти и ускоряет выполнение.

Функция clearAllMemoizedCaches очищает таблицы мемоизации, когда в них больше нет необходимости.

: clearAllMemoizedCaches ()

Очистить все кэши мемоизации.

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

См. также: memoize.