tag:blogger.com,1999:blog-10303035.post7951409667741824661..comments2024-02-04T23:20:04.066+03:00Comments on Алёна C++: MemoizationAlenahttp://www.blogger.com/profile/09389124127364799922noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-10303035.post-21363451842348942482007-06-04T12:36:00.000+04:002007-06-04T12:36:00.000+04:00первая мысль этаж просто кэширование, втораяпро: Ф...первая мысль этаж просто кэширование, вторая<BR/>про: <BR/><B><BR/>Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)<BR/></B><BR/>а это мы применяли в курсаче по компьютерной графике.Ivhttps://www.blogger.com/profile/09724511625118329123noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-17120044429330894232007-06-01T12:05:00.000+04:002007-06-01T12:05:00.000+04:00В книге "Алгоритмы: построение и н анализ" Кормена...<I>В книге "Алгоритмы: построение и н анализ" Кормена, Лейзерсона и Ривеста этот процесс называется динамическим программированием. Это один из любимейших разделов для олимпиадных программистов. В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц</I><BR/><BR/>AFAIK динамическое программирование - более широкое понятие. Ну опять приведу ссылку на Википедию: <A HREF="http://en.wikipedia.org/wiki/Dynamic_programming" REL="nofollow">dynamic programming</A>.Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-69625018580033984282007-06-01T07:40:00.000+04:002007-06-01T07:40:00.000+04:00В общем-то memoization скорее паттерн, из функцион...В общем-то memoization скорее паттерн, из функционального программирования, где кэширование находится внутри, а не вне объекта.<BR/><BR/>Memoization (also called tabulation) is a technique that enables a <I>procedure</I> to record, in a<BR/>local table, values that have previously been computed.<BR/><BR/>(define memo-fib<BR/> (memoize (lambda (n)<BR/> (cond ((= n 0) 0)<BR/> ((= n 1) 1)<BR/> (else (+ (memo-fib (- n 1))<BR/> (memo-fib (- n 2))))))))<BR/><BR/>where the memoizer is defined as<BR/><BR/>(define (memoize f)<BR/> (let ((table (make-table)))<BR/> (lambda (x)<BR/> (let ((previously-computed-result (lookup x table)))<BR/> (or previously-computed-result<BR/> (let ((result (f x)))<BR/> (insert! x result table)<BR/> result))))))<BR/><BR/>Из книги Structure and Interpretation of Computer Programsmewpewpewhttps://www.blogger.com/profile/17592254611840007615noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-45167357726652140842007-06-01T02:28:00.000+04:002007-06-01T02:28:00.000+04:00В качестве простейшей задачи можно рассмотреть опт...<I>В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матриц</I><BR/><BR/>да, в частности оптимальный его порядок (т.к. умножение ассоциативно).<BR/><BR/>если я правильно понимаю, memoization также подходит для итеративного решения рекурсивных задач. тривиальный пример: пишем числа фибоначи в матрицу размером 1xN. в более общем смысле, с помощью memoization можно более эффективно решать задачи "на перебор", записывая в матрицу оценку того или иного варианта и их комбинацию.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-61585682142442229922007-06-01T01:29:00.000+04:002007-06-01T01:29:00.000+04:00В книге "Алгоритмы: построение и н анализ" Кормена...В книге "Алгоритмы: построение и н анализ" Кормена, Лейзерсона и Ривеста этот процесс называется динамическим программированием. Это один из любимейших разделов для олимпиадных программистов. В качестве простейшей задачи можно рассмотреть оптимальное умножение(с точки зрения количества действий) матрицTNThttps://www.blogger.com/profile/01330005583089470848noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-33596244205520942212007-06-01T01:02:00.000+04:002007-06-01T01:02:00.000+04:00Побочные эффекты и state dependence - это плохо.В ...<I>Побочные эффекты и state dependence - это плохо.</I><BR/><BR/>В каком смысле "плохо"? Да, сложнее, чем чистое функциональное программирование, но с ним одним далеко не уедешь :-).<BR/><BR/>На самом деле, с этой сложностью вполне справляется инкапсуляция. Например дорогой метод объекта может кешировать свой результат в своем объекте, а методы объекта, влияющие на его состояние, и меняющие результат функции, могут этот кеш сбрасывать.Ivan Sagalaevhttps://www.blogger.com/profile/08658726720189436784noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-82049732741792391942007-06-01T00:00:00.000+04:002007-06-01T00:00:00.000+04:002Alex Ott:и люди продолжают изобретать для императ...2Alex Ott:<BR/><I>и люди продолжают изобретать для императивных языков функции из функциональных :-)</I><BR/><BR/>:-)<BR/><BR/><I>Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)</I><BR/><BR/>В memoization обязательно должно быть построение таблицы _в процессе_ работы с функцией. Если эти таблицы продолжают дозаполняться в процессе работы - то да, это memoization.Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-80856644100104408502007-05-31T20:24:00.000+04:002007-05-31T20:24:00.000+04:00Функции sin/cos, построенные на заранее просчитанн...Функции sin/cos, построенные на заранее просчитанных таблицах можно считать memoization? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-81081116967104038612007-05-31T18:57:00.000+04:002007-05-31T18:57:00.000+04:00и люди продолжают изобретать для императивных язык...и люди продолжают изобретать для императивных языков функции из функциональных :-)Alex Otthttps://www.blogger.com/profile/13001951608173211050noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-50979514449398186892007-05-31T17:40:00.000+04:002007-05-31T17:40:00.000+04:00Хе. В PostgreSQL можно такое поведение объявить дл...Хе. В PostgreSQL можно такое поведение объявить для хранимой процедуры.norguhtarhttps://www.blogger.com/profile/01590300726098472855noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-89369143899257630892007-05-31T16:12:00.000+04:002007-05-31T16:12:00.000+04:00Побочные эффекты и state dependence - это плохо. Д...Побочные эффекты и state dependence - это плохо. Даже в императивном программировании.Victor Sergienkohttps://www.blogger.com/profile/03248158339739606306noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-40143576362032292642007-05-31T15:53:00.000+04:002007-05-31T15:53:00.000+04:002Exo:Алена, а в чем разница с кэшированием?В Викип...2Exo:<BR/><I>Алена, а в чем разница с кэшированием?</I><BR/><BR/>В Википедии мемоизация классифицируется как один из видов кэширования.<BR/><BR/>2Lev Serebryakov:<BR/><I>Вообще-то, если для вашей функции этот приём использовать нельзя, то она и не функция вовсе. В математическом смысле.</I><BR/><BR/>Ну в computer science функциям позволено больше свободы. :-) И разные результаты выдавать в зависимости от количества вызовов и еще что-нибудь в этом роде...Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-9639632965873267002007-05-31T15:49:00.000+04:002007-05-31T15:49:00.000+04:00Позвольте несогласиться, просто результат функции ...Позвольте несогласиться, просто результат функции будет зависеть и от прочих, явно не указанных, параметров. Если принимать во внимание все возможные параметры, то можно использовать этот прием. Но(!) иногда невозможно либо нецелесообразно использовать данный способ по причине большого количества или, как я уже сказал, неявности этих самых параметров.<BR/><BR/>Пример:<BR/>функция перехода дороги,<BR/>вход: есть ли машина, внимателен ли пешеход, есть ли светофор, какой горит свет, есть ли ямы на дороге, ведутся ли дорожные работы и еще много чего...<BR/>выход: пешеход перешел/сбит<BR/><BR/>Количество входных параметров конечно, но слишком велико для использования подобных вещей.Anonymoushttps://www.blogger.com/profile/16659099732079480206noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-30585692567521156592007-05-31T15:32:00.000+04:002007-05-31T15:32:00.000+04:00Вообще-то, если для вашей функции этот приём испол...Вообще-то, если для вашей функции этот приём использовать нельзя, то она и не функция вовсе. В математическом смысле.blacklionhttps://www.blogger.com/profile/07027467380237335137noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-5406521284303649102007-05-31T15:31:00.000+04:002007-05-31T15:31:00.000+04:00Алена, а в чем разница с кэшированием? Подобные ве...Алена, а в чем разница с кэшированием? Подобные вещи довольно часто используются, особенно в базах данных, в частности когда строятся планы выполнения запросов, которые зачастую являются наиболее ресурсоемкими.Anonymoushttps://www.blogger.com/profile/16659099732079480206noreply@blogger.com