Мемоизация

Техника оптимизации программирования программного обеспечения

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

Этимология

Термин «мемоизация» был придуман Дональдом Мичи в 1968 году ^[3] и происходит от латинского слова « memorandum » («чтобы запомнить»), которое в американском английском обычно сокращается до «memo» и, таким образом, имеет значение «мемоизация». превращение [результатов] функции во что-то, что стоит запомнить». Хотя «мемоизацию» можно спутать с « запоминанием » (поскольку они этимологически родственны ), «мемоизация» имеет особое значение в вычислительной технике.

Обзор

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

Мемоизированные функции оптимизированы по скорости в обмен на более активное использование памяти компьютера . Временная/пространственная «стоимость» алгоритмов имеет в вычислительной технике особое название: вычислительная сложность . Все функции имеют вычислительную сложность во времени (т.е. для их выполнения требуется время) и в пространстве .

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

Рассмотрим следующую функцию псевдокода для вычисления факториала n :

функция факториал ( n — целое неотрицательное число) если n равно 0, то return 1 [ по соглашению, что  0! = 1 ] еще вернуть факториал( n – 1) раз n [ рекурсивно вызвать факториал  с параметром 1 меньше n ] конец, есликонечная функция

Для каждого целого числа n такого , что n ≥ 0конечный результат функции factorialинвариантен ; при вызове как , результат таков, что x всегда будет присвоено значение 6. Приведенная выше немемоизированная реализация, учитывая природу используемого рекурсивного алгоритма, потребует n + 1 вызовов для получения результата, и каждый из эти вызовы, в свою очередь, имеют соответствующую стоимость в виде времени, которое требуется функции для возврата вычисленного значения. В зависимости от машины эта стоимость может составлять сумму:x = factorial(3)factorial

1. Стоимость настройки кадра функционального стека вызовов.
2. Стоимость сравнения n с 0.
3. Стоимость вычитания 1 из n .
4. Стоимость настройки кадра стека рекурсивных вызовов. (Как указано выше.)
5. Стоимость умножения результата рекурсивного вызова factorialна n .
6. Стоимость сохранения возвращаемого результата, чтобы его можно было использовать вызывающим контекстом.

В реализации без мемоизации каждый вызов верхнего уровня factorialвключает совокупную стоимость шагов со 2 по 6, пропорциональную начальному значению n .

Ниже представлена ​​мемоизированная версия функции factorial:

функция факториал ( n — целое неотрицательное число) если n равно 0, то return 1 [ по соглашению, что  0! = 1 ] иначе, если n находится в справочной таблице , тогда вернуть значение-таблицы поиска для-n еще let x = Factorial(n – 1) раз n [ рекурсивно вызывать факториал  с параметром 1 меньше n ] сохраните x в таблице поиска в n- м слоте [ запомните результат n! Для последующего ] вернуть х конец, есликонечная функция

В этом конкретном примере, если factorialсначала вызывается значение 5, а затем вызывается позже с любым значением, меньшим или равным пяти, эти возвращаемые значения также будут запомнены, поскольку factorialбудут вызываться рекурсивно со значениями 5, 4, 3, 2, 1 и 0, и возвращаемые значения для каждого из них будут сохранены. Если затем он вызывается с номером больше 5, например 7, будет выполнено только 2 рекурсивных вызова (7 и 6), а значение 5! будут сохранены с предыдущего вызова. Таким образом, мемоизация позволяет функции более эффективно расходовать время, чем чаще она вызывается, что в конечном итоге приводит к общему ускорению.

Некоторые другие соображения

Функциональное программирование

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

Автоматическое запоминание

Хотя мемоизация может быть добавлена ​​к функциям внутренне и явно программистом во многом так же, как реализована описанная выше мемоизированная версия ,factorial ссылочно прозрачные функции также могут автоматически запоминаться извне . ^[1] Методы, использованные Питером Норвигом, применяются не только в Common Lisp (языке, на котором в его статье продемонстрировано автоматическое запоминание), но и в различных других языках программирования . Применение автоматического запоминания также официально изучалось при изучении переписывания терминов ^[4] и искусственного интеллекта . ^[5]

В языках программирования, где функции являются объектами первого класса (таких как Lua , Python или Perl ^[6] ), автоматическое запоминание может быть реализовано путем замены (во время выполнения) функции ее вычисленным значением после того, как значение было вычислено для заданный набор параметров. Функция, выполняющая такую ​​замену значения на объект-функцию, может в общих чертах обертывать любую ссылочно прозрачную функцию. Рассмотрим следующий псевдокод (где предполагается, что функции являются значениями первого класса):

функция memoized-call ( F — параметр объекта функции) если F не имеет присоединенных значений массива , тогда выделить ассоциативный массив с именемvalues ; прикрепить значения к F ; конец, если; если Ф. _ значения[аргументы] пусты, то F . значения[аргументы] = F (аргументы); конец, если; вернуть F. значения[аргументы] ;конечная функция

Чтобы вызвать автоматически запоминаемую версию factorialиспользования вышеуказанной стратегии, вместо factorialпрямого вызова, код вызывает . Каждый такой вызов сначала проверяет, выделен ли массив-держатель для хранения результатов, и если нет, присоединяет этот массив. Если в позиции нет записи (где используются в качестве ключа ассоциативного массива), выполняется реальный вызов с предоставленными аргументами. Наконец, запись в массиве в ключевой позиции возвращается вызывающей стороне.memoized-call(factorial(n))values[arguments]argumentsfactorial

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

функция-конструктор-мемоизированный-функтор ( F — параметр объекта функции) выделите функциональный объект с именем memoized-version ; пусть memoized-версия(аргументы) будет если у self нет присоединенных значений массива, тогда [ self является ссылкой на этот объект ] выделить ассоциативный массив с именемvalues ; придавать ценности себе ; _ конец, если; если сам. значения [аргументы] пусты, тогда себя. значения[аргументы] = F (аргументы); конец, если; вернуть себя. значения[аргументы] ; конец пусть; вернуть мемоизированную версию ;конечная функция

Вместо вызова factorialновый объект функции memfactсоздается следующим образом:

memfact = конструкция-мемоизированный-функтор (факториал)

В приведенном выше примере предполагается, что функция factorialуже определена доconstruct-memoized-functor выполнения вызова . С этого момента вызывается всякий раз, когда требуется факториал n . В таких языках, как Lua, существуют более сложные методы, которые позволяют заменять функцию новой функцией с тем же именем, что позволяет:memfact(n)

факториал = конструкция-мемоизированный-функтор (факториал)

По сути, такие методы включают в себя присоединение исходного объекта функции к созданному функтору и перенаправление вызовов исходной функции, запоминаемой через псевдоним, когда требуется вызов фактической функции (во избежание бесконечной рекурсии ), как показано ниже:

функция-конструктор-мемоизированный-функтор ( F — параметр объекта функции) выделите функциональный объект с именем memoized-version ; пусть мемоизированная версия (аргументы) будет если у self нет присоединенных значений массива, тогда [ self является ссылкой на этот объект ] выделить ассоциативный массив с именемvalues ; придавать ценности себе ; _ выделите новый объект функции с именем alias ; прикрепить псевдоним к себе ; [ для последующей возможности косвенно вызывать F ] себя. псевдоним = F ; конец, если; если сам. значения [аргументы] пусты, тогда себя. значения [аргументы] = self. псевдоним (аргументы); [ не прямой звонок F ] конец, если; вернуть себя. значения[аргументы] ; конец пусть; вернуть мемоизированную версию ;конечная функция

(Примечание. Некоторые из показанных выше шагов могут неявно управляться языком реализации и приведены для иллюстрации.)

Парсеры

Когда нисходящий синтаксический анализатор пытается проанализировать неоднозначные входные данные относительно неоднозначной контекстно-свободной грамматики (CFG), ему может потребоваться экспоненциальное количество шагов (относительно длины входных данных), чтобы опробовать все альтернативы CFG. для создания всех возможных деревьев разбора. В конечном итоге это потребует экспоненциального объема памяти. Мемоизация была исследована как стратегия синтаксического анализа в 1991 году Питером Норвигом, который продемонстрировал, что алгоритм, аналогичный использованию динамического программирования и наборов состояний в алгоритме Эрли (1970), а также таблиц в алгоритме CYK Кока, Янгера и Касами, может генерироваться путем введения автоматического запоминания в простой анализатор рекурсивного спуска с обратным отслеживанием для решения проблемы экспоненциальной временной сложности. ^[1] Основная идея подхода Норвига заключается в том, что когда к входным данным применяется синтаксический анализатор, результат сохраняется в memotable для последующего повторного использования, если тот же синтаксический анализатор когда-либо повторно применяется к тем же входным данным.

Ричард Фрост и Барбара Шидловски также использовали мемоизацию, чтобы уменьшить экспоненциальную временную сложность синтаксических комбинаторов , описывая результат как запоминающий чисто функциональный языковой процессор с нисходящим обратным отслеживанием. ^[7] Фрост показал, что базовые мемоизированные комбинаторы парсеров могут использоваться в качестве строительных блоков для создания сложных парсеров как исполняемых спецификаций CFG. ^{[8] [9]}

Мемоизация была снова исследована в контексте синтаксического анализа в 1995 году Марком Джонсоном и Йохеном Дёрре. ^{[10] [11]} В 2002 году он был подробно исследован Брайаном Фордом в форме, называемой разбором пакетов . ^[12]

В 2007 году Фрост, Хафиз и Каллаган ^{[ нужна ссылка ]} описали алгоритм синтаксического анализа сверху вниз, который использует мемоизацию для воздержания от избыточных вычислений, чтобы приспособить любую форму неоднозначной CFG за полиномиальное время ( Θ (n ⁴ ) для леворекурсивных грамматик и Θ( n ³ ) для нелеворекурсивных грамматик). Их алгоритм нисходящего анализа также требует полиномиального пространства для потенциально экспоненциальных неоднозначных деревьев анализа посредством «компактного представления» и «группировки локальных неоднозначностей». Их компактное представление сравнимо с компактным представлением восходящего синтаксического анализа Томиты . ^[13] Их использование мемоизации не ограничивается только получением ранее вычисленных результатов, когда анализатор многократно применяется к одной и той же входной позиции (что важно для требования полиномиального времени); он специализируется на выполнении следующих дополнительных задач:

• Процесс мемоизации (который можно рассматривать как «обертку» для выполнения любого синтаксического анализатора) обеспечивает постоянно растущий прямой леворекурсивный анализ, налагая ограничения на глубину в отношении длины ввода и текущей позиции ввода.
• Процедура «поиска» таблицы заметок алгоритма также определяет возможность повторного использования сохраненного результата путем сравнения вычислительного контекста сохраненного результата с текущим контекстом синтаксического анализатора. Это контекстное сравнение является ключом к использованию косвенной (или скрытой) левой рекурсии .
• При успешном поиске в memotable вместо возврата полного набора результатов процесс возвращает только ссылки на фактический результат и в конечном итоге ускоряет общие вычисления.
• Во время обновления таблицы памяти процесс запоминания группирует (потенциально экспоненциальные) неоднозначные результаты и обеспечивает требования к полиномиальному пространству.

Фрост, Хафиз и Каллаган также описали реализацию алгоритма в PADL'08 ^{[ нужна ссылка ]} как набор функций высшего порядка (называемых комбинаторами синтаксического анализатора ) в Haskell , что позволяет создавать непосредственно исполняемые спецификации CFG как языковых процессоров. Важность способности их полиномиального алгоритма справляться с «любой формой неоднозначных CFG» с нисходящим синтаксическим анализом жизненно важна для синтаксического и семантического анализа во время обработки естественного языка . На сайте X-SAIGA можно найти дополнительную информацию об алгоритме и деталях реализации.

Хотя Норвиг увеличил мощность анализатора за счет мемоизации, расширенный анализатор по-прежнему был таким же сложным по времени, как алгоритм Эрли, который демонстрирует случай использования мемоизации для чего-то другого, кроме оптимизации скорости. Джонсон и Дорре ^[11] демонстрируют еще одно такое применение мемоизации, не связанное со скоростью: использование мемоизации для задержки разрешения лингвистических ограничений до момента синтаксического анализа, где накоплено достаточно информации для разрешения этих ограничений. Напротив, в применении мемоизации для оптимизации скорости Форд продемонстрировал, что мемоизация может гарантировать, что синтаксический анализ грамматик выражений может анализировать за линейное время даже те языки , которые приводят к наихудшему поведению с возвратом. ^[12]

Рассмотрим следующую грамматику :

S → (А c ) | (Б д )А → Икс ( а | б )B → X b
X → x [X]

(Примечание: в приведенном выше примере продукция S → (A c ) | (B d ) гласит: «An S — это либо A , за которым следует a c , либо B, за которым следует a d ». Продукция X → x [ X] гласит: « X — это x , за которым следует необязательный X ».)

Эта грамматика генерирует один из следующих трех вариантов строки : xac , xbc или xbd (где x здесь понимается как один или несколько x ). Далее рассмотрим, как эта грамматика, используемая в качестве спецификации синтаксического анализа, может повлиять на Разбор строки xxxxxxbd сверху вниз и слева направо :

Правило A распознает xxxxxb (сначала спускаясь в X , чтобы распознать один x , и снова спускаясь в X до тех пор, пока все x не будут израсходованы, а затем распознавая b ), а затем возвращаясь в S и не распознавая c . . Следующее предложение S затем спустится в B, который, в свою очередь, снова спустится в X и распознает x посредством множества рекурсивных вызовов X , а затем a b , вернется к S и, наконец, распознает a d .

Ключевое понятие здесь заложено во фразе снова спускается в X. Процесс просмотра вперед, неудачи, резервного копирования и повторной попытки следующей альтернативы известен в синтаксическом анализе как возврат назад, и именно возврат назад предоставляет возможности для запоминания при синтаксическом анализе. Рассмотрим функцию RuleAcceptsSomeInput(Rule, Position, Input), параметры которой следующие:

• Rule— имя рассматриваемого правила.
• Positionэто смещение, которое в данный момент рассматривается во входных данных.
• Inputявляется рассматриваемым входом.

Пусть возвращаемое значение функции RuleAcceptsSomeInputбудет длиной входных данных, принятых Rule, или 0, если это правило не принимает никаких входных данных с этим смещением в строке. В сценарии обратного отслеживания с такой мемоизацией процесс синтаксического анализа выглядит следующим образом:

Когда правило A спускается в X со смещением 0, оно запоминает длину 5 относительно этой позиции и правила X. После неудачи в d , B затем, вместо того, чтобы снова спуститься в X , запрашивает позицию 0 по правилу X в механизме запоминания и возвращает длину 5, тем самым избавляя от необходимости снова спускаться в X , и продолжает как если бы он спускался в X столько же раз, сколько раньше.

В приведенном выше примере может произойти один или несколько спусков на X , что позволяет использовать такие строки, как xxxxxxxxxxxxxxxxbd . Фактически, перед b может быть любое количество x . Хотя вызов S должен рекурсивно спускаться в X столько раз, сколько существует x , B вообще никогда не придется спускаться в X, поскольку возвращаемое значение будет 16 (в данном конкретном случае).RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

Те парсеры, которые используют синтаксические предикаты , также способны запоминать результаты анализа предикатов, тем самым сокращая такие конструкции, как:

С → (А)? АA → /* какое-то правило */

к одному спуску в A .

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

Поскольку для любого синтаксического анализатора с обратным отслеживанием или синтаксическими предикатами не каждая грамматика потребует обратного отслеживания или проверки предикатов, накладные расходы на сохранение результатов анализа каждого правила относительно каждого смещения во входных данных (и сохранение дерева синтаксического анализа, если процесс синтаксического анализа делает это неявно) могут фактически замедляет парсер. Этот эффект можно смягчить путем явного выбора тех правил, которые анализатор будет запоминать. ^[14]

Смотрите также

• Приближенные вычисления - категория методов повышения эффективности.
• Теория сложности вычислений – дополнительная информация о сложности алгоритмов
• Строка директора – быстрый поиск свободных переменных в выражениях.
• Шаблон Flyweight — шаблон проектирования объектного программирования , который также использует своего рода мемоизацию.
• Hashlife — метод запоминания для ускорения вычислений клеточных автоматов.
• Ленивая оценка - разделяет некоторые концепции с мемоизацией.
• Материализованное представление – аналогичное кэширование в запросах к базе данных.
• Частичная оценка - родственный метод автоматической оптимизации программы.

Рекомендации

1. Норвиг, Питер (1991). «Методы автоматического запоминания с приложениями для контекстно-свободного анализа». Компьютерная лингвистика . 17 (1): 91–98.
2. Уоррен, Дэвид С. (1 марта 1992 г.). «Мемориалы для логических программ». Коммуникации АКМ . 35 (3): 93–111. дои : 10.1145/131295.131299 . ISSN  0001-0782.
3. Мичи, Дональд (1968). «Функции Memo и машинное обучение» (PDF) . Природа . 218 (5136): 19–22. Бибкод : 1968Natur.218...19M. дои : 10.1038/218019a0. S2CID  4265138.
4. Хоффман, Бертольд (1992). «Переписывание терминов с обменом и мемоизацией». В Киршнере, Х.; Леви, Г. (ред.). Алгебраическое и логическое программирование: Третья международная конференция, материалы, Вольтерра, Италия, 2–4 сентября 1992 г. Конспекты лекций по информатике. Том. 632. Берлин: Шпрингер. стр. 128–142. дои : 10.1007/BFb0013824. ISBN 978-3-540-55873-6.
5. Мэйфилд, Джеймс; и другие. (1995). «Использование автоматического запоминания как инструмента разработки программного обеспечения в реальных системах искусственного интеллекта» (PDF) . Материалы одиннадцатой конференции IEEE по искусственному интеллекту для приложений (CAIA '95) . стр. 87–93. дои : 10.1109/CAIA.1995.378786. hdl : 11603/12722. ISBN 0-8186-7070-3. S2CID  8963326.
6. «Бриколаж: Мемоизация».
7. Фрост, Ричард; Шидловски, Барбара (1996). «Запоминание чисто функциональных языковых процессоров с нисходящим обратным отслеживанием». наук. Вычислить. Программа . 27 (3): 263–288. дои : 10.1016/0167-6423(96)00014-7 .
8. Фрост, Ричард (1994). «Использование мемоизации для достижения полиномиальной сложности чисто функциональных исполняемых спецификаций недетерминированных нисходящих парсеров». Уведомления SIGPLAN . 29 (4): 23–30. дои : 10.1145/181761.181764. S2CID  10616505.
9. Фрост, Ричард (2003). «Монадическая мемоизация к сокращению поиска, сохраняющему корректность». Канадская конференция по искусственному интеллекту 2003 г. Конспекты лекций по информатике. Том. 2671. стр. 66–80. дои : 10.1007/3-540-44886-1_8. ISBN 978-3-540-40300-5.
10. Джонсон, Марк (1995). «Мемоизация нисходящего синтаксического анализа». Компьютерная лингвистика . 21 (3): 405–417. arXiv : cmp-lg/9504016 . Бибкод : 1995cmp.lg....4016J.
11. Джонсон, Марк и Дорре, Йохен (1995). «Мемоизация сопрограммных ограничений». Материалы 33-го ежегодного собрания Ассоциации компьютерной лингвистики . Кембридж, Массачусетс. arXiv : cmp-lg/9504028 .{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
12. Форд, Брайан (2002). Анализ Packrat: практический алгоритм линейного времени с обратным отслеживанием (магистерская диссертация). Массачусетский Институт Технологий. hdl : 1721.1/87310.
13. Томита, Масару (1985). Эффективный синтаксический анализ естественного языка . Бостон: Клювер. ISBN 0-89838-202-5.
14. Ачар, Умут А.; и другие. (2003). «Выборочная мемоизация». Материалы 30-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования, 15–17 января 2003 г. Том. 38. Новый Орлеан, Луизиана. стр. 14–25. arXiv : 1106.0447 . дои : 10.1145/640128.604133. {{cite book}}: |journal=игнорируется ( помощь )CS1 maint: отсутствует местоположение издателя ( ссылка )

Внешние ссылки

Примеры мемоизации на различных языках программирования

• groovy.lang.Closure#memoize() — Memoize — это функция языка Apache Groovy 1.8.
• Memoize — Memoize — небольшая библиотека, написанная Тимом Брэдшоу, для выполнения мемоизации в Common Lisp .
• IncPy — специальный интерпретатор Python , выполняющий автоматическое запоминание (без обязательных пользовательских аннотаций).
• Макросы Дэйва Хермана для определения мемоизированных процедур в Racket .
• Memoize.pm – модуль Perl , реализующий мемоизированные функции.
• Мемоизация Java — пример использования динамических прокси-классов на языке Java для создания общего шаблона мемоизации.
• memoization.java — библиотека мемоизации Java.
• C++Memo ^{[ постоянная мертвая ссылка ]} — платформа мемоизации C++ .
• C-Memo — универсальная библиотека мемоизации для C, реализованная с использованием макросов-оболочек функций препроцессора.
• Tek271 Memoizer – Java-мемоайзер с открытым исходным кодом, использующий аннотации и подключаемые реализации кэша.
• memoizable — драгоценный камень Ruby , реализующий мемоизированные методы.
• Мемоизация Python — пример мемоизации Python .
• Мемоизация OCaml — реализована как расширение синтаксиса Camlp4 .
• Мемоизация в Lua — два примера реализации общей функции мемоизации в Lua .
• Мемоизация в Mathematica — Мемоизация и ограниченная мемоизация в Mathematica .
• Мемоизация в Javascript — расширение прототипа функции в JavaScript (архивная версия http://talideon.com/weblog/2005/07/javascript-memoization.cfm).
• Мемоизация в Javascript – Примеры мемоизации в Javascript с использованием собственного механизма кэширования и использования библиотеки YUI.
• X-SAIGA – исполняемые спецификации грамматик. Содержит публикации, связанные с алгоритмом синтаксического анализа сверху вниз, который поддерживает левую рекурсию и неоднозначность в полиномиальном времени и пространстве.
• Мемоизация в схеме — пример мемоизации Scheme на веб-странице класса.
• Мемоизация в комбинаторной логике — веб-сервис для сокращения комбинаторной логики при запоминании каждого шага в базе данных.
• MbCache — результаты метода кэширования в .NET .