Мемоизация

Не путать с запоминанием .

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

Этимология

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

Обзор

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

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

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

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

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

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

1. Стоимость настройки кадра функционального стека вызовов.
2. Стоимость сравнения n с 0.
3. Стоимость вычитания 1 из n .
4. Стоимость настройки кадра стека рекурсивных вызовов. (Как указано выше.)
5. Стоимость умножения результата рекурсивного вызова factorial по н .
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 й slot [  запомнить результат n!   Для последующего  ] 
          вернуть х 
      конец, если 
  конечная функция 
 

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

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

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

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

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

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

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

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

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

      если  Ф. ​   значения [аргументы]  пусты, тогда 
          Ф. ​   значения[аргументы]  =  F  (аргументы); 
      конец, если; 

      вернуть F.  значения[аргументы]  ; 
  конечная функция 
 

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

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

функция-конструктор-мемоизированный-функтор (  F  — параметр объекта функции) 
      выделите функциональный объект с именем  memoized-version  ; 

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

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

          вернуть себя.   значения[аргументы]  ; 
      конец пусть; 

      вернуть  мемоизированную версию  ; 
  конечная функция 
 

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

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

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

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

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

функция-конструктор-мемоизированный-функтор (  F  — параметр объекта функции) 
      выделите функциональный объект с именем  memoized-version  ; 

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

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

          вернуть себя.   значения[аргументы]  ; 
      конец пусть; 

      вернуть  мемоизированную версию  ; 
  конечная функция 
 

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

Парсеры

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

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

Мемоизация была снова исследована в контексте синтаксического анализа в 1995 году Марком Джонсоном и Йохеном Дёрре. В 2002 году он был достаточно глубоко исследован Брайаном Фордом в форме, названной разбором Packrat .

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

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

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

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

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

S → (А  c  ) |   (Б  д  ) 
  А → Икс (  а  |  б  ) 
  Б → Х  б 
  Икс →  х  [Х] 
 

(Примечание: в приведенном выше примере продукция 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 . Фактически, любое количество x может быть перед b . Хотя вызов S должен рекурсивно спускаться в X столько раз, сколько существует x , B вообще никогда не придется спускаться в X, поскольку возвращаемое значение RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) будет 16 (в данном конкретном случае).

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

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

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

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

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

См. также

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

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

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

• 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++ .
• 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 .