Статья Автор: Деникина Н.В., Деникин А.В.

Две функции и запоминание

Две функции F и G: свой словарь → lru_cache

Одна функция обращается к другой

F(n) = n + 10, если n < 10;
F(n) = n % 10 + G(F(n // 10)), если n ≥ 10;
G(n) = n + 10, если n < 10;
G(n) = n % 10 + G(n // 10), если n ≥ 10.

Определите сумму F(n) для всех натуральных n < 1 000 000.

// — целочисленное деление. Важный момент: G(F(n // 10)) — вложенный вызов, а не G(n // 10).


Свой кэш

Словарь memo запоминает вычисленные значения G. При повторном обращении не вычисляем G заново.

Порядок записи

Сначала определяем G, затем F. Заранее заполнять G не требуется.



Теперь тот же алгоритм короче

@lru_cache(maxsize=None) сам запоминает значения G(n). По умолчанию кэш хранит до 128 результатов; maxsize=None убирает этот предел, но увеличивает возможный расход памяти.



Ограничения: аргументы кэшируемой функции должны быть хешируемыми; кэш не увеличивает глубину рекурсии. При необходимости sys.setrecursionlimit(5000) изменяет предел вызовов, но слишком большое значение опасно переполнением стека. lru_cache не обязательно медленнее словаря: скорость зависит от количества повторов и размера кэша.
Печать