19.5 Кэширование результатов вычислений ¶

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

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

: mem_fcn_handle = memoize (fcn_handle) ¶

Создать мемоизированную версию функции fcn_handle с именем mem_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.