19.5 Мемоизация

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

Функция Octave memoize предоставляет функциональность мемоизации «подключить и использовать» для любых пользовательских функций или функций 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.