Memoization (я встречала только один перевод на русский и он ужасен - "мемоизация") - это оптимизационный прием, который подробно с примерами описан в Википедии. Буквы r там в середине нет, все правильно!
Опишу вкратце. Идея состоит в том, чтобы результат вызова функции заносить в таблицу какую-нибудь. Позже, получив те же аргументы во второй раз, можно все заново не считать, а из этой таблицы вытащить. Таблица эта - не данность, она заполняется в процессе мемоизации. В итоге получаются некоторые потери по памяти в обмен на выигрыш по скорости. При этом надо помнить, что функция функции рознь и не для каждой функции этот метод можно использовать.
четверг, мая 31, 2007
Memoization
Подписаться на:
Комментарии к сообщению (Atom)
Atom feed
15 коммент.:
Алена, а в чем разница с кэшированием? Подобные вещи довольно часто используются, особенно в базах данных, в частности когда строятся планы выполнения запросов, которые зачастую являются наиболее ресурсоемкими.
Вообще-то, если для вашей функции этот приём использовать нельзя, то она и не функция вовсе. В математическом смысле.
Позвольте несогласиться, просто результат функции будет зависеть и от прочих, явно не указанных, параметров. Если принимать во внимание все возможные параметры, то можно использовать этот прием. Но(!) иногда невозможно либо нецелесообразно использовать данный способ по причине большого количества или, как я уже сказал, неявности этих самых параметров.
Пример:
функция перехода дороги,
вход: есть ли машина, внимателен ли пешеход, есть ли светофор, какой горит свет, есть ли ямы на дороге, ведутся ли дорожные работы и еще много чего...
выход: пешеход перешел/сбит
Количество входных параметров конечно, но слишком велико для использования подобных вещей.
2Exo:
Алена, а в чем разница с кэшированием?
В Википедии мемоизация классифицируется как один из видов кэширования.
2Lev Serebryakov:
Вообще-то, если для вашей функции этот приём использовать нельзя, то она и не функция вовсе. В математическом смысле.
Ну в computer science функциям позволено больше свободы. :-) И разные результаты выдавать в зависимости от количества вызовов и еще что-нибудь в этом роде...
Побочные эффекты и state dependence - это плохо. Даже в императивном программировании.
Хе. В PostgreSQL можно такое поведение объявить для хранимой процедуры.
и люди продолжают изобретать для императивных языков функции из функциональных :-)
Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)
2Alex Ott:
и люди продолжают изобретать для императивных языков функции из функциональных :-)
:-)
Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)
В memoization обязательно должно быть построение таблицы _в процессе_ работы с функцией. Если эти таблицы продолжают дозаполняться в процессе работы - то да, это memoization.
Побочные эффекты и state dependence - это плохо.
В каком смысле "плохо"? Да, сложнее, чем чистое функциональное программирование, но с ним одним далеко не уедешь :-).
На самом деле, с этой сложностью вполне справляется инкапсуляция. Например дорогой метод объекта может кешировать свой результат в своем объекте, а методы объекта, влияющие на его состояние, и меняющие результат функции, могут этот кеш сбрасывать.
В книге "Алгоритмы: построение и н анализ" Кормена, Лейзерсона и Ривеста этот процесс называется динамическим программированием. Это один из любимейших разделов для олимпиадных программистов. В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц
В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц
да, в частности оптимальный его порядок (т.к. умножение ассоциативно).
если я правильно понимаю, memoization также подходит для итеративного решения рекурсивных задач. тривиальный пример: пишем числа фибоначи в матрицу размером 1xN. в более общем смысле, с помощью memoization можно более эффективно решать задачи "на перебор", записывая в матрицу оценку того или иного варианта и их комбинацию.
В общем-то 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
В книге "Алгоритмы: построение и н анализ" Кормена, Лейзерсона и Ривеста этот процесс называется динамическим программированием. Это один из любимейших разделов для олимпиадных программистов. В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц
AFAIK динамическое программирование - более широкое понятие. Ну опять приведу ссылку на Википедию: dynamic programming.
первая мысль этаж просто кэширование, вторая
про:
Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)
а это мы применяли в курсаче по компьютерной графике.
Отправить комментарий