Мемоизация

Уберите из текста все пробелы и знаки препинания. Сколькими способами его можно снова разрезать на слова? «Наполеон» читается двумя: «наполеон» и «на поле он». А вот абзац о Наташе из третьего тома «Войны и мира» — двадцатью семью миллиардами. Напишите свой текст или выберите готовый: программа считает прочтения прямо в браузере, по словарю из 14 871 слова романа.

Посмотрите на средний счётчик. Рекурсия, которая честно перебирает прочтения, на этом абзаце сделала бы 337 816 617 486 вызовов: около четырнадцати часов на Go и двое-трое суток на Python. Программа отвечает за миллисекунду, потому что знает простой приём: каждый ответ она запоминает и второй раз не считает. Различных вопросов здесь всего 133 — «сколькими способами дочитать текст с буквы номер i».

Идея

Если функция для одних и тех же аргументов всегда возвращает одно и то же, её ответы можно запоминать: при первом вызове посчитать и положить в словарь, при следующих — взять из словаря. Это мемоизация. Она ничего не меняет в логике программы, но рекурсия, которая много раз решает одну и ту же подзадачу, превращается в рекурсию, которая решает каждую подзадачу один раз.

Вот рекурсия из сцены. Пусть ways(i) — сколькими способами можно дочитать текст, начиная с буквы i. Перебираем, каким словом начинается остаток: если буквы с i по j − 1 образуют слово, добавляем ways(j). Дочитать пустой остаток можно одним способом: ways(n) = 1.

Формула верна, но к позиции j рекурсия приходит много раз — столько, сколькими способами читается начало текста до неё. И каждый раз заново пересчитывает весь хвост. Посмотрите на дерево вызовов:

Одинаковые цвета — одна и та же позиция, то есть одна и та же работа, сделанная заново. В «москвасгорела» 51 вызов, а разных позиций, до которых вообще можно дойти, — 12. Включите память: каждая позиция раскрывается один раз, а при следующих встречах ответ берётся готовым, и от дерева остаются только первые вхождения. На коротком слове экономия скромная, но число повторов растёт с длиной текста как экспонента: на абзаце о Наташе дерево состояло бы из трёхсот с лишним миллиардов узлов.

Когда работает

Нужны два условия.

• Функция чистая. Результат зависит только от аргументов: она не читает время, случайные числа, файлы и глобальные переменные, которые меняются, и не изменяет ничего вокруг. Иначе ответ из памяти может оказаться устаревшим — а повторный вызов не выполнит нужных побочных действий.
• Подзадачи повторяются. Одни и те же аргументы приходят много раз. В сортировке слиянием каждая половина массива сортируется один раз, и память ничего не даст. В задаче о прочтениях одна позиция приходит миллиарды раз.

Если оба условия выполнены, время работы — это число разных аргументов, умноженное на работу одного вызова без учёта вложенных. Здесь позиций n + 1, а на каждой нужно проверить не больше 24 кусков — самое длинное слово словаря. Абзац в 232 буквы — несколько тысяч проверок вместо сотен миллиардов вызовов.

Код

В Python запоминание — один декоратор: @functools.cache (а с ограничением размера — @functools.lru_cache(maxsize=…)). В Go готового нет, и память — это словарь, заведённый рядом с функцией. Программа считает прочтения абзаца, вызовы, которые сделала бы рекурсия без памяти, и прочтения с наименьшим и наибольшим числом слов. Самое короткое прочтение почти совпадает с текстом Толстого: 55 слов вместо 56, потому что «так же» склеилось в «также» — такое слово в словаре тоже есть.

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

Ключ и подвохи

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

Ключ должен быть неизменяемым. functools.cache хранит аргументы в словаре, и список в аргументах даст TypeError: unhashable type. Списки превращают в кортежи, множества — во frozenset, наборы флагов — в битовые маски. В Go ключом словаря может быть число, строка, массив фиксированной длины или структура из таких полей, но не срез.

Память не бесплатна. Каждый запомненный ответ занимает место, и кэш без ограничения живёт, пока жив процесс. Если разных аргументов много, а нужны в основном недавние, берут lru_cache(maxsize=…): он выбрасывает то, к чему дольше всего не обращались (как устроен такой кэш — в статье о кэше LRU). А кэш на методе класса держит в памяти и сам объект self — частая причина утечек.

Рекурсия остаётся рекурсией. На тексте в пять тысяч букв запоминающая функция уйдёт вглубь на пять тысяч вызовов, а Python по умолчанию останавливается на тысяче. Тогда либо поднимают предел через sys.setrecursionlimit, либо заполняют ту же таблицу ответов без рекурсии, в таком порядке, чтобы нужные значения всегда были уже посчитаны, — здесь с конца текста к началу. Это и есть динамическое программирование «снизу вверх». Мемоизация — то же самое «сверху вниз»: порядок вычислений находит сама рекурсия.

Сколько это стоит

Время — число различных аргументов, умноженное на работу одного вызова без вложенных, плюс поиск в словаре памяти, в среднем O(1). Память — по ответу на каждый различный аргумент. Без памяти время равно числу узлов дерева вызовов, и оно бывает экспоненциальным: у наивного Фибоначчи 1,618ⁿ вызовов, у прочтений абзаца — 3,4·10¹¹.

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

История

Слово придумал исследователь искусственного интеллекта Дональд Мичи. В 1968 году в журнале Nature вышла его статья «“Memo” functions and machine learning»: функция, которая заводит себе памятку — memo — и сверяется с ней, прежде чем считать, «учится» на собственном опыте. Мичи во время войны работал над взломом шифров, а потом основал одну из первых лабораторий искусственного интеллекта.

Задачи

Первая — те же прочтения, но для текстов до пяти тысяч букв, где рекурсия уже упирается в предел глубины. Во второй числа на пути гипотезы Коллатца уходят далеко за пределы таблицы, и нужно решить, что именно запоминать.