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

Рекуррентные функции — Две функции и запоминание


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

SilverTests № 39779

Одна функция обращается к другой
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 не обязательно медленнее словаря: скорость зависит от количества повторов и размера кэша.
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Печать