Мемоизация: кеш поверх рекурсии, lru_cache и отличие от таблицы

Короткий ответ. Мемоизация это кеш поверх рекурсии. Функция запоминает ответ для каждого набора аргументов. При повторном вызове она отдаёт его из словаря. Так экспоненциальная рекурсия становится линейной или квадратичной. В Python это одна строка: декоратор lru_cache. Ниже, когда это работает, код, разбор и отличие от таблицы снизу вверх.

Что такое мемоизация?

Рекурсивная функция часто вызывает себя с одними и теми же аргументами. Числа Фибоначчи: fib(5) вызывает fib(4) и fib(3), а fib(4) снова вызывает fib(3). Дерево вызовов растёт как 2ⁿ.

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

Это динамическое программирование сверху вниз. Таблица та же, порядок заполнения выбирает рекурсия.

Слово «мемоизация» пишется без «р». Оно происходит от «memo», заметка. Функция оставляет себе заметки о прошлых ответах.

Когда мемоизация помогает, а когда нет?

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

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

Есть и второй способ проверить. Посчитайте число разных наборов аргументов. Если оно много меньше числа вызовов, кеш окупится. У Фибоначчи n наборов против 2ⁿ вызовов.

Как это выглядит на примере?

fib(5) без кеша: 15 вызовов. fib(5) с кешем: fib(5), fib(4), fib(3), fib(2), fib(1), fib(0) считаются по разу. Остальные вызовы возвращаются из словаря сразу. Всего 6 настоящих вычислений.

Для n = 40 разница уже в сотни миллионов вызовов против сорока.

Как написать мемоизацию на Python?

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

# то же самое руками
def fib_memo(n, memo=None):
    memo = {} if memo is None else memo
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

@lru_cache(maxsize=None)
def unique_paths(r, c):
    if r == 1 or c == 1:
        return 1
    return unique_paths(r - 1, c) + unique_paths(r, c - 1)

def word_break(s, words):
    words = set(words)

    @lru_cache(maxsize=None)
    def can(i):                      # можно ли разбить s[i:]
        if i == len(s):
            return True
        return any(s[i:j] in words and can(j) for j in range(i + 1, len(s) + 1))

    return can(0)

lru_cache хеширует аргументы, поэтому они должны быть числами, строками или кортежами. Списки превращайте в кортежи.

Чем мемоизация отличается от таблицы снизу вверх?

Признак	Мемоизация	Таблица снизу вверх
Код	Рекурсия плюс словарь	Цикл плюс массив
Порядок вычислений	Выбирает рекурсия	Выбираете вы
Лишние состояния	Не считаются	Считаются все
Память	Словарь плюс стек вызовов	Массив, часто ужимается
Ограничение	Глубина рекурсии в Python	Нужно найти порядок
Когда брать	Переход сложный, состояний разреженно	Состояний много, память важна

Как решить Unique Paths через мемоизацию?

Сетка r на c, идти можно вправо и вниз. Сколько путей из угла в угол? Число путей из клетки это сумма путей из двух соседних: справа и снизу. База: одна строка или один столбец, путь один.

Состояний r · c, каждое считается раз. Время O(r · c). Без кеша это экспонента.

Как решить Word Break?

Можно ли разбить строку на слова из словаря? Функция can(i) отвечает про хвост с позиции i. Пробуем каждую границу j. Префикс должен быть в словаре, а хвост от j разбиваться. Кеш на i делает время O(n²) при проверке подстрок.

Как решить Climbing Stairs с мемоизацией?

Лестница из n ступенек, шаг на одну или две. Способы дойти до n это способы дойти до n - 1 плюс способы до n - 2. Это Фибоначчи со сдвигом. Функция с lru_cache решает задачу за O(n).

Когда мемоизации мало и нужен цикл?

Когда n больше десяти тысяч. Рекурсия уйдёт на глубину n, и Python остановит её. Тогда переписываем в цикл снизу вверх. Переход остаётся тем же, меняется только форма кода.

Второй случай: память. Словарь хранит все состояния. Цикл с двумя переменными хранит два числа. На собеседовании про это спрашивают после рабочего решения.

На каких ошибках ломается мемоизация?

• Изменяемый аргумент по умолчанию memo={}. Кеш живёт между вызовами функции.
• Функция зависит от внешней переменной, а в ключ кеша она не входит.
• Глубина рекурсии больше лимита Python. Нужен sys.setrecursionlimit или цикл.
• Кеш на объектах, которые сравниваются по ссылке. Одинаковые данные дают разные ключи.

Как объяснить приём на собеседовании?

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

Сложность назовите как число разных состояний, умноженное на работу в одном вызове. Для Фибоначчи это O(n).

Отработать узнавание приёма можно на странице рекурсия с мемоизацией. Восходящий вариант разобран на странице динамическое программирование.

Вопросы и ответы

Чем lru_cache отличается от cache?

functools.cache это lru_cache без ограничения размера. Появился в Python 3.9. Для собеседования разницы нет.

Как мемоизировать метод класса?

Декоратор работает, но self попадёт в ключ. Лучше вынести вычисление во вложенную функцию внутри метода.

Можно ли мемоизировать функцию с двумя аргументами?

Да, ключом станет кортеж аргументов. Число состояний это произведение диапазонов, следите за памятью.

Где мемоизация встречается в реальных системах?

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