Введение

Метод оптимизации программного обеспечения

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

Этимология

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

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

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

Анализаторы

Когда анализатор сверху вниз пытается обработать неоднозначный ввод относительно неоднозначной контекстно-свободной грамматики (CFG), ему может потребоваться экспоненциальное число шагов (относительно длины ввода), чтобы перебрать все альтернативы CFG и построить все возможные деревья разбора. Это в конечном итоге потребует экспоненциального объема памяти. Мемоизация была исследована как стратегия разбора в 1991 году Питером Норвигом, который показал, что алгоритм, аналогичный использованию динамического программирования и множеств состояний в алгоритме Эрли (1970) и таблиц в алгоритме CYK Кокка, Янгера и Касами, может быть получен путем добавления автоматической мемоизации к простому рекурсивному спусковому анализатору для решения проблемы экспоненциальной временной сложности. Фрост показал, что базовые комбинаторы парсеров могут использоваться как строительные блоки для создания сложных парсеров в виде исполняемых спецификаций CFG. В 1995 году Марк Джонсон и Йохен Дёрре вновь исследовали мемоизацию в контексте разбора. В 2002 году Брайан Форд подробно изучил ее в форме, известной как packrat-разбор. В 2007 году Фрост, Хафиз и Каллаган описали алгоритм разбора сверху вниз, который использует мемоизацию для предотвращения избыточных вычислений и поддержки любой формы неоднозначной CFG за полиномиальное время (Θ(n⁴) для леворекурсивных грамматик и Θ(n³) для нелеворекурсивных грамматик). Их алгоритм разбора сверху вниз также требует полиномиального пространства для потенциально экспоненциальных неоднозначных деревьев разбора благодаря «компактному представлению» и «группировке локальных неоднозначностей». Их компактное представление сопоставимо с компактным представлением Томиты для разбора снизу вверх. Использование мемоизации не ограничивается только извлечением ранее вычисленных результатов при повторном применении парсера к одной и той же позиции ввода (что необходимо для обеспечения полиномиальной временной сложности); оно специализировано для выполнения следующих дополнительных задач: Процесс мемоизации (который можно рассматривать как «оболочку» вокруг любого выполнения парсера) поддерживает постоянно растущий прямой левый рекурсивный разбор, накладывая ограничения на глубину относительно длины ввода и текущей позиции ввода. Процедура поиска в таблице мемоизации также определяет возможность повторного использования сохраненного результата путем сравнения вычислительного контекста сохраненного результата с текущим контекстом парсера. Это контекстуальное сравнение является ключом к поддержке неявной (или скрытой) левой рекурсии. При успешном поиске в таблице мемоизации процесс возвращает не весь набор результатов, а только ссылки на фактические результаты, что в конечном итоге ускоряет общие вычисления. При обновлении таблицы мемоизации процесс мемоизации группирует (потенциально экспоненциальные) неоднозначные результаты и обеспечивает полиномиальное требование к пространству. Фрост, Хафиз и Каллаган также описали реализацию алгоритма в PADL’08 в виде набора функций высшего порядка (называемых комбинаторами парсеров) на языке Haskell, что позволяет создавать непосредственно исполняемые спецификации CFG в качестве языковых процессоров. Важность способности их полиномиального алгоритма поддерживать «любую форму неоднозначной CFG» при разборе сверху вниз имеет решающее значение для синтаксического и семантического анализа при обработке естественного языка. Более подробная информация об алгоритме и деталях реализации доступна на сайте X SAIGA. Хотя Норвиг повысил мощность парсера с помощью мемоизации, расширенный парсер оставался столь же сложным по времени, как алгоритм Эрли, что демонстрирует пример использования мемоизации не для оптимизации скорости. Джонсон и Дёрре.