Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с запоминанием .
"Таблинг" перенаправляется сюда. О парламентской процедуре см. Таблицу (парламентская процедура) .

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

Этимология [ править ]

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

Обзор [ править ]

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

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

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

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

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

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

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

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

Мемоизированная версия factorialфункции:

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

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

Некоторые другие соображения [ править ]

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

Основная статья: Thunk § Функциональное программирование

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

Автоматическая мемоизация [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Парсеры [ править ]

Когда нисходящий синтаксический анализатор пытается проанализировать неоднозначный ввод относительно неоднозначной контекстно-свободной грамматики (CFG), ему может потребоваться экспоненциальное количество шагов (относительно длины ввода), чтобы попробовать все альтернативы CFG. для создания всех возможных деревьев синтаксического анализа. В конечном итоге это потребует экспоненциального пространства памяти. Мемоизация была исследована как стратегия синтаксического анализа в 1991 году Питером Норвигом, который продемонстрировал, что алгоритм, подобный использованию динамического программирования и наборов состояний в алгоритме Эрли (1970), и таблиц в алгоритме CYK Кока, Янгера и Касами, может быть сгенерирован путем введения автоматической мемоизации в простой синтаксический анализатор рекурсивного спуска с возвратом для решения проблемы экспоненциальной временной сложности. [1] Основная идея в подходе Норвига состоит в том, что когда синтаксический анализатор применяется к входу, результат сохраняется в memotable для последующего повторного использования, если тот же анализатор когда-либо повторно применяется к тому же входу. Ричард Фрост также использовал мемоизацию, чтобы уменьшить экспоненциальную временную сложность комбинаторов синтаксического анализатора , что можно рассматривать как метод синтаксического анализа «чисто функциональный поиск с возвратом сверху вниз». [6] Он показал, что базовые комбинаторы мемоизированного синтаксического анализатора могут использоваться в качестве строительных блоков для создания сложных синтаксических анализаторов в качестве исполняемых спецификаций CFG. [7] [8]Он был снова исследован в контексте анализа в 1995 году Джонсоном и Дорре. [9] [10] В 2002 году он был подробно исследован Фордом в форме, названной синтаксическим анализом пакетов . [11]

В 2007 году Frost, Hafiz и Callaghan [ необходима цитата ] описали алгоритм нисходящего синтаксического анализа, который использует мемоизацию для предотвращения избыточных вычислений, чтобы приспособить любую форму неоднозначного CFG за полиномиальное время ( Θ (n 4 ) для леворекурсивных грамматик и Θ ( п 3 ) для не леворекурсивных грамматик). Их алгоритм нисходящего синтаксического анализа также требует полиномиального пространства для потенциально экспоненциальных неоднозначных деревьев синтаксического анализа с помощью «компактного представления» и «группировки локальных неоднозначностей». Их компактное представление сравнимо с компактным представлением Томиты восходящего синтаксического анализа . [12]Их использование мемоизации не ограничивается только получением ранее вычисленных результатов, когда синтаксический анализатор многократно применяется к одной и той же позиции ввода (что важно для требования полиномиального времени); он специализируется на выполнении следующих дополнительных задач:

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

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

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

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

S → (A c ) | (B d )А → Х ( а | б )B → X b
X → x [X]

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

Эта грамматика генерирует один из следующих трех вариаций строки : XAC , XBC или XBD (где х здесь понимается одним или несколькими х «ами ). Далее, рассмотрим , как эта грамматика, используется в качестве синтаксического анализа спецификации, мог бы осуществить синтаксический анализ строки xxxxxbd сверху вниз, слева направо :

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

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

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

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

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

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

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

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

на один спуск в A .

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

Примеры мемоизации на разных языках программирования
  • 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 - ВЫПОЛНЯЕМЫЕ ОСОБЕННОСТИ ГРАММАТИКИ. Содержит публикации, связанные с алгоритмом нисходящего синтаксического анализа, который поддерживает левую рекурсию и неоднозначность в полиномиальном времени и пространстве.
  • Мемоизация в схеме - пример схемы мемоизации на веб-странице класса.
  • Мемоизация в комбинаторной логике - веб-сервис для уменьшения комбинаторной логики , запоминая каждый шаг в базе данных.
  • MbCache - метод кеширования результатов в .NET .