четверг, мая 31, 2007

Memoization

Memoization (я встречала только один перевод на русский и он ужасен - "мемоизация") - это оптимизационный прием, который подробно с примерами описан в Википедии. Буквы r там в середине нет, все правильно!
Опишу вкратце. Идея состоит в том, чтобы результат вызова функции заносить в таблицу какую-нибудь. Позже, получив те же аргументы во второй раз, можно все заново не считать, а из этой таблицы вытащить. Таблица эта - не данность, она заполняется в процессе мемоизации. В итоге получаются некоторые потери по памяти в обмен на выигрыш по скорости. При этом надо помнить, что функция функции рознь и не для каждой функции этот метод можно использовать.

15 коммент.:

Exo комментирует...

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

Lev Serebryakov комментирует...

Вообще-то, если для вашей функции этот приём использовать нельзя, то она и не функция вовсе. В математическом смысле.

Exo комментирует...

Позвольте несогласиться, просто результат функции будет зависеть и от прочих, явно не указанных, параметров. Если принимать во внимание все возможные параметры, то можно использовать этот прием. Но(!) иногда невозможно либо нецелесообразно использовать данный способ по причине большого количества или, как я уже сказал, неявности этих самых параметров.

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

Количество входных параметров конечно, но слишком велико для использования подобных вещей.

Alena комментирует...

2Exo:
Алена, а в чем разница с кэшированием?

В Википедии мемоизация классифицируется как один из видов кэширования.

2Lev Serebryakov:
Вообще-то, если для вашей функции этот приём использовать нельзя, то она и не функция вовсе. В математическом смысле.

Ну в computer science функциям позволено больше свободы. :-) И разные результаты выдавать в зависимости от количества вызовов и еще что-нибудь в этом роде...

Victor комментирует...

Побочные эффекты и state dependence - это плохо. Даже в императивном программировании.

norguhtar комментирует...

Хе. В PostgreSQL можно такое поведение объявить для хранимой процедуры.

Alex Ott комментирует...

и люди продолжают изобретать для императивных языков функции из функциональных :-)

Анонимный комментирует...

Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)

Alena комментирует...

2Alex Ott:
и люди продолжают изобретать для императивных языков функции из функциональных :-)

:-)

Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)

В memoization обязательно должно быть построение таблицы _в процессе_ работы с функцией. Если эти таблицы продолжают дозаполняться в процессе работы - то да, это memoization.

Maniac комментирует...

Побочные эффекты и state dependence - это плохо.

В каком смысле "плохо"? Да, сложнее, чем чистое функциональное программирование, но с ним одним далеко не уедешь :-).

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

Dmitry комментирует...

В книге "Алгоритмы: построение и н анализ" Кормена, Лейзерсона и Ривеста этот процесс называется динамическим программированием. Это один из любимейших разделов для олимпиадных программистов. В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц

Павел комментирует...

В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц

да, в частности оптимальный его порядок (т.к. умножение ассоциативно).

если я правильно понимаю, memoization также подходит для итеративного решения рекурсивных задач. тривиальный пример: пишем числа фибоначи в матрицу размером 1xN. в более общем смысле, с помощью memoization можно более эффективно решать задачи "на перебор", записывая в матрицу оценку того или иного варианта и их комбинацию.

Lormus комментирует...

В общем-то memoization скорее паттерн, из функционального программирования, где кэширование находится внутри, а не вне объекта.

Memoization (also called tabulation) is a technique that enables a procedure to record, in a
local table, values that have previously been computed.

(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))

where the memoizer is defined as

(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))

Из книги Structure and Interpretation of Computer Programs

Alena комментирует...

В книге "Алгоритмы: построение и н анализ" Кормена, Лейзерсона и Ривеста этот процесс называется динамическим программированием. Это один из любимейших разделов для олимпиадных программистов. В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц

AFAIK динамическое программирование - более широкое понятие. Ну опять приведу ссылку на Википедию: dynamic programming.

Iv комментирует...

первая мысль этаж просто кэширование, вторая
про:

Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)

а это мы применяли в курсаче по компьютерной графике.