В чем разница между кешированием и мемоизацией?

114

Я хотел бы знать, в чем на самом деле разница между cachingи memoization.
На мой взгляд, оба варианта подразумевают отказ от повторных вызовов функций для получения данных путем их сохранения .

В чем основная разница между ними?

caching terminology memoization Джон
источник
Интересно, могли бы вы сказать «мемоизация для кеширования» как «массив для разреженного массива». Другими словами, вы сохраняете вещи только «по запросу», а не перечисляете все возможные комбинации входных данных.
Шридхар Сарнобат

Ответы:

110

Мемоизация - это особая форма кэширования, которая включает в себя кеширование возвращаемого значения функции на основе ее параметров .

Кэширование - это более общий термин; например, HTTP-кеширование - это кеширование, но не мемоизация.

Википедия говорит :

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

SLaks
источник
2
но вы всегда можете заменить ту часть, где кеш используется функцией, и окрестили ее «мемоизацией». хотя разница в том, что вы контролируете политику кэширования в своей функции, тогда как мемоизация - это более высокий порядок и происходит вне функции, я думаю.
Николас
Почему HTTP-кеширование не запоминается? это также зависит от параметра (URL-адрес запрошенного ресурса).
topo Reinstate Monica
@topomorto: из-за таких функций If-Matchи истечения срока действия. Мемоизация имеет смысл только для чистой функции, что редко бывает с HTTP.
SLaks
@nicolas, я думаю, не совсем. Я думаю, что в мемоизации термин «функция» используется в чисто математическом смысле. Загрузка веб-страницы с заданного адреса не может считаться функцией, потому что может случиться так, что страница изменится.
Алексей
@Alexey, разве это не относится к кешированию? все эти стратегии полагаются на один и тот же вызов функции, дающий один и тот же результат, иначе говоря, отсутствие побочного эффекта восходящего потока .
nicolas
47

Как я видел, «мемоизация» - это «кэширование результата детерминированной функции», который может быть воспроизведен в любое время с той же функцией и входными данными.

«Кэширование» включает в себя практически любую стратегию буферизации вывода, независимо от того, воспроизводимо ли исходное значение в данный момент времени. Фактически, кэширование также используется для обозначения стратегий буферизации ввода , таких как кэш записи на диске или в памяти. Так что это гораздо более общий термин.

Харпо
источник
Вы уверены, что функция должна быть детерминированной?
Gherman
4
@German, да, мемоизация зависит от детерминизма. Классический пример - рекурсивный алгоритм, такой как последовательность Фибоначчи или факториал. Вместо того, чтобы полностью пересчитывать до базового случая, мемоизированная функция могла бы выполнить короткое замыкание, повторно используя более ранние результаты для значений, которые она уже вычислила. Это, очевидно, зависит от того, что один и тот же вход всегда дает один и тот же результат, что является определением детерминизма. Кэширование, с другой стороны, часто используется для недетерминированных (например, случайных или отмеченных временем) процессов, с пониманием того, что результаты могут не соответствовать «обновленному» значению.
harpo
6

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

МК.
источник
1

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

Пьер-Ив Сомон
источник
0

К другим отличным ответам я хотел бы добавить, что мемоизация также известна как таблинг . Я думаю, что этот термин также важен для тех, кто знает, что такое мемоизация и кеширование.

VS
источник