Мемоизация - Memoization

Не путать с Запоминание.
"Таблинг" перенаправляется сюда. Для парламентской процедуры см. Таблица (парламентская процедура).

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

Этимология

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

Обзор

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

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

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

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

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

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

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

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

Мемоизированная версия факториал функция следующая:

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

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

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

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

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

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

Автоматическая мемоизация

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

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

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

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

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

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

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

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

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

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

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

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

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

Парсеры

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

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

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

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

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

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

S → (A c) | (B d) A → X (а|б) B → X бX → Икс [ИКС]

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

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

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

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

  • Правило название рассматриваемого правила.
  • Позиция это смещение, которое в настоящее время рассматривается во входных данных.
  • Вход - рассматриваемый ввод.

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

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

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

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

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

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

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

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

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

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

  1. ^ а б c Норвиг, Питер (1991). «Методы автоматической мемоизации с приложениями для бесконтекстного анализа». Компьютерная лингвистика. 17 (1): 91–98.
  2. ^ Уоррен, Дэвид. "Таблинг и программирование журнала данных". Получено 29 мая 2009.
  3. ^ Мичи, Дональд (1968). "'Функции Memo и машинное обучение » (PDF). Природа. 218 (5136): 19–22. Bibcode:1968Натура.218 ... 19М. Дои:10.1038 / 218019a0. S2CID  4265138.
  4. ^ Хоффман, Бертольд (1992). «Перезапись терминов с обменом и мемоизацией». В Kirchner, H .; Леви, Г. (ред.). Алгебраическое и логическое программирование: Третья международная конференция, Труды, Вольтерра, Италия, 2–4 сентября 1992 г.. Конспект лекций по информатике. 632. Берлин: Springer. С. 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. ^ Фрост, Ричард; Шидловский, Барбара (1996). «Запоминание чисто функциональных языковых процессоров с возвратом сверху вниз». Sci. Comput. Программа. 27 (3): 263–288. Дои:10.1016/0167-6423(96)00014-7.
  7. ^ Фрост, Ричард (1994). «Использование мемоизации для достижения полиномиальной сложности чисто функциональных исполняемых спецификаций недетерминированных нисходящих синтаксических анализаторов». Уведомления SIGPLAN. 29 (4): 23–30. Дои:10.1145/181761.181764. S2CID  10616505.
  8. ^ Фрост, Ричард (2003). «Монадическая мемоизация к сохранению правильности сокращения поиска». Канадская конференция по AI 2003. Конспект лекций по информатике. 2671. С. 66–80. Дои: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. ^ а б Джонсон, Марк и Дорре, Йохен (1995). «Запоминание сопрограмм ограничений». Труды 33-го ежегодного собрания Ассоциации компьютерной лингвистики. Кембридж, Массачусетс. arXiv:cmp-lg / 9504028.
  11. ^ а б Форд, Брайан (2002). Парсинг Packrat: практический алгоритм линейного времени с возвратом (Дипломная работа). Массачусетский Институт Технологий. HDL:1721.1/87310.
  12. ^ Томита, Масару (1985). Эффективный синтаксический анализ естественного языка. Бостон: Клувер. ISBN  0-89838-202-5.
  13. ^ Acar, Umut A .; и другие. (2003). «Выборочная мемоизация». Материалы 30-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования, 15–17 января 2003 г.. Уведомления ACM SIGPLAN. 38. Новый Орлеан, Луизиана. С. 14–25. arXiv:1106.0447. Дои:10.1145/640128.604133.

внешняя ссылка

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