Воспоминание - Memoization

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

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

Этимология

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

Обзор

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

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

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

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

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else
        return factorial(n – 1) times n [recursively invoke factorial 
                                        with the parameter 1 less than n]
    end if
end function

Для каждого целого числа п такое , что 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функции: 

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else if n is in lookup-table then
        return lookup-table-value-for-n
    else
        let x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
        store x in lookup-table in the nth slot [remember the result of n! for later]
        return x
    end if
end function

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

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

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

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

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

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

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

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

function memoized-call (F is a function object parameter)
    if F has no attached array values then
        allocate an associative array called values;
        attach values to F;
    end if;

    if F.values[arguments] is empty then
        F.values[arguments] = F(arguments);
    end if;

    return F.values[arguments];
end function

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

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

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;

    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = F(arguments);
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

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

 memfact = construct-memoized-functor(factorial)

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

 factorial = construct-memoized-functor(factorial)

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

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;

    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
            allocate a new function object called alias;
            attach alias to self; [for later ability to invoke F indirectly]
            self.alias = F;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = self.alias(arguments); [not a direct call to F]
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

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

Парсеры

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

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

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

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

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

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

S → (A c) | (B d)
A → X (a|b)
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
A → /* some rule */

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

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

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

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

использованная литература

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

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