Подтема 3 из 6
Повторные вызовы и таблица
Почему программа с двумя вызовами себя считает долго и как её ускорить: @cache, прогрев кеша и таблица значений циклом.
Повторные вызовы
Почему программа может считать минуты, хотя аргумент небольшой?
Если функция вызывает себя дважды, одни и те же значения считаются снова и снова. Возьмём F(n) = 1 при n ≤ 2; F(n) = F(n − 1) + F(n − 2) при n > 2 — это числа Фибоначчи: 1, 1, 2, 3, 5, 8, … Программа по определению:
def F(n): if n <= 2: return 1 return F(n - 1) + F(n - 2) print(F(5))Какие вызовы она делает для F(5), показывает левое дерево:
С ростом n повторов становится лавина: для F(30) программа делает больше полутора миллионов вызовов, для F(40) — больше двухсот миллионов. А разных значений среди них всего сорок.
@cache
Как убрать повторы?
Запоминать каждое найденное значение и при повторном вызове брать готовый ответ. Это делает .
from functools import cache @cachedef F(n): if n <= 2: return 1 return F(n - 1) + F(n - 2) print(F(50))Строка from functools import cache подключает готовое запоминание, а @cache над def включает его для F. Формула остаётся прежней. Правое дерево на схеме — та же F(5) с @cache: повторные вызовы сразу получают ответ из памяти. Поэтому F(50) считается мгновенно.
Тонкости:lru_cache и как устроено запоминание
В разборах часто пишут @lru_cache(None) из того же модуля — это то же запоминание. У @lru_cache() без None память ограничена 128 значениями. Внутри это словарь «аргумент → значение»: перед вычислением функция смотрит, нет ли там ответа, а после кладёт его туда.
Прогрев кеша
А если программа с @cache всё равно падает с RecursionError?
Кеш не уменьшает глубину: первый вызов F(2026) всё равно спускается до базы через две тысячи ждущих вызовов. Глубину убирает прогрев — вызвать функцию по очереди, начиная от базы. Задача темы с прогревом:
from functools import cache @cachedef F(n): if n == 1: return 1 return n * F(n - 1) for n in range(1, 2027): F(n) print((F(2026) + 3 * F(2025)) // F(2024))Цикл считает F(1), F(2), F(3), … по очереди. Когда доходит очередь до F(100), значение F(99) уже лежит в кеше — вызов делает один шаг вниз, а не сто. Ждущих вызовов всё время мало, и предел поднимать не нужно. Результат F(n) в цикле никуда не записываем: вызов нужен только ради кеша.
Прогревают всегда от базы. Если база сверху — например, F(n) = n при n ≥ 5000 и F(n) = F(n + 3) + 5 при n < 5000, — цикл идёт по убыванию: for n in range(5002, 0, -1). Тогда к вызову F(n) значение F(n + 3) уже готово.
Таблица циклом
Можно ли обойтись совсем без рекурсии?
Да: завести список, где f[n] хранит F(n), и заполнить его циклом по формуле. Задача темы таблицей:
f = [0] * 2027f[1] = 1for n in range(2, 2027): f[n] = n * f[n - 1] print((f[2026] + 3 * f[2025]) // f[2024])[0] * 2027 создаёт из 2027 нулей с номерами от 0 до 2026 — так появляется место для f[2026]. Элемент f[0] не используется, а остальные нули — заготовки, их заменит цикл. Когда цикл считает f[n], значение f[n − 1] уже готово.
Порядок заполнения задают зависимости. Если формула берёт значения слева — F(n − 1), F(n − 2), — список заполняют слева направо. Если справа — F(n + 1), — справа налево, от верхней базы:
Такой способ — сохранять ответы маленьких задач и строить из них следующие — называют динамическим программированием. Прогрев кеша делает то же самое, только значения хранит @cache.
Тонкости:заполнение справа налево
Функция из подтемы 1: F(n) = n при n ≥ 10 и F(n) = n + F(n + 1) при n < 10.
f = [0] * 11f[10] = 10for n in range(9, 0, -1): f[n] = n + f[n + 1] print(f[7])range(9, 0, -1) даёт 9, 8, …, 1: третье число — шаг −1, а 0 не входит.
Две функции
Что делать, если в условии две функции и они вызывают друг друга?
Записать обе по определению — каждую своей def — и вызывать их после того, как описаны обе. Например: F(1) = 1, G(1) = 2; при n > 1 F(n) = F(n − 1) + G(n − 1), G(n) = 2 · F(n − 1) + G(n − 1). Найдём F(5) + G(5). Вручную — таблицей по строкам:
| n | F(n) | G(n) |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 1 + 2 = 3 | 2 · 1 + 2 = 4 |
| 3 | 3 + 4 = 7 | 2 · 3 + 4 = 10 |
| 4 | 7 + 10 = 17 | 2 · 7 + 10 = 24 |
| 5 | 17 + 24 = 41 | 2 · 17 + 24 = 58 |
Обе функции берут значения из предыдущей строки. Ответ: 41 + 58 = 99. Программой:
from functools import cache @cachedef F(n): if n == 1: return 1 return F(n - 1) + G(n - 1) @cachedef G(n): if n == 1: return 2 return 2 * F(n - 1) + G(n - 1) print(F(5) + G(5))F ссылается на G, описанную ниже, — это нормально: Python ищет G только в момент вызова. Главное, чтобы print стоял после обеих def. @cache нужен каждой функции: обе вызывают по две функции, и без запоминания при больших n повторы разрастаются, как у Фибоначчи.
Итого
- Два вызова себябез запоминания значения считаются много раз
@cacheкаждое значение считается один раз- Глубинакеш её не уменьшает: поднять предел или прогреть кеш
- Прогреввызвать F(n) по очереди, начиная от базы
- Таблицаf[n] = F(n), цикл идёт от базы; список на N + 1 элемент
- Две функциидве def, вызов после обеих
Проверьте себя
Ответь сначала сам, потом открой ответ.
@cache считает F(40) так долго, хотя разных значений всего сорок?ОтветСкрыть ответ
@cache и вызвали F(6). Поможет ли это?ОтветСкрыть ответ
@cache вызов F(1) всё равно падает. В какую сторону прогревать кеш?ОтветСкрыть ответ
for n in range(3000, 0, -1). Тогда к вызову F(n) значение F(n + 1) уже готово.f = [0] * 2026. Можно ли записать значение в f[2026]?ОтветСкрыть ответ
[0] * 2027 — на один элемент больше.g[n] или для f[n]?ОтветСкрыть ответ
g[n]: формуле F(n) нужно уже новое G(n).Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Три предыдущих значения
F(n) = 1 при n ≤ 3; F(n) = F(n − 1) + F(n − 2) + F(n − 3) при n > 3. Найди F(40).
Введите число.
Подсказка
Функция вызывает себя трижды — без запоминания ответа не дождаться. Добавь @cache.
Решение
Каждый вызов порождает три новых, и одни и те же значения считаются снова и снова. С @cache каждое F(k) считается один раз:
from functools import cache @cachedef F(n): if n <= 3: return 1 return F(n - 1) + F(n - 2) + F(n - 3) print(F(40))Ответ: 9129195487
Числа Фибоначчи с @cache
F(n) = 1 при n ≤ 2; F(n) = F(n − 1) + F(n − 2) при n > 2. Найди F(70).
Введите число.
Подсказка
Без запоминания F(70) потребует триллионы вызовов — добавь @cache над def.
Решение
Программа по определению с @cache: каждое значение от F(1) до F(70) считается один раз.
from functools import cache @cachedef F(n): if n <= 2: return 1 return F(n - 1) + F(n - 2) print(F(70))Ответ: 190392490709135
Задача в формате экзамена: F(30)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 2 при n ≥ 40; F(n) = F(n + 1) + F(n + 2) при n < 40. Чему равно значение функции F(30)?
Введите число.
Подсказка
F(n) вызывает F(n + 1) и F(n + 2) — с @cache это быстро.
Решение
Функция вызывает себя дважды, поэтому добавляем @cache. От баз F(40) = F(41) = 2 значения вниз: 4, 6, 10, 16, …, и F(30) = 288.
from functools import cache @cachedef F(n): if n >= 40: return 2 return F(n + 1) + F(n + 2) print(F(30))Ответ: 288
Прогрев от верхней базы
F(n) = n при n ≥ 5000; F(n) = F(n + 2) + 1 при n < 5000. Найди F(1).
Введите число.
Подсказка
От 1 до базы — 2500 ждущих вызовов. Прогрей кеш по убыванию, от базы.
Решение
Аргументы 1, 3, …, 4999, 5001: 2500 переходов по +1 и база F(5001) = 5001, итого 7501. Программа прогревает кеш от базы вниз, поэтому ждущих вызовов всё время мало:
from functools import cache @cachedef F(n): if n >= 5000: return n return F(n + 2) + 1 for n in range(5001, 0, -1): F(n) print(F(1))Ответ: 7501
Таблица справа налево
F(n) = n при n ≥ 20; F(n) = F(n + 2) + n при n < 20. Найди F(15).
Введите число.
Подсказка
Аргументы растут через один: 15, 17, 19, … Какая база попадёт в цепочку?
Решение
Таблицу заполняют справа налево, от верхних баз F(20) = 20 и F(21) = 21. От 15 аргументы 15, 17, 19, 21 — нужна база F(21): F(15) = 15 + 17 + 19 + 21 = 72.
f = [0] * 22f[20] = 20f[21] = 21for n in range(19, 0, -1): f[n] = f[n + 2] + n print(f[15])Ответ: 72
Половина аргумента
F(1) = 1; F(n) = F(n − 1) + F(n // 2) при n > 1. Найди F(100).
Введите число.
Подсказка
Каждому f[n] нужны f[n − 1] и f[n // 2] — оба левее, заполняй список слева направо.
Решение
Оба нужных значения — с меньшими аргументами, поэтому список заполняем по возрастанию n:
f = [0] * 101f[1] = 1for n in range(2, 101): f[n] = f[n - 1] + f[n // 2] print(f[100])Ответ: 102829
Две связанные функции
F(1) = 2, G(1) = 1; при n > 1 F(n) = F(n − 1) + G(n − 1), G(n) = 2 · F(n − 1). Найди F(4) + G(4).
Введите число.
Подсказка
Обе функции берут значения из предыдущей строки — составь таблицу n, F(n), G(n).
Решение
n = 2: F = 2 + 1 = 3, G = 2 · 2 = 4. n = 3: F = 3 + 4 = 7, G = 2 · 3 = 6. n = 4: F = 7 + 6 = 13, G = 2 · 7 = 14. F(4) + G(4) = 13 + 14 = 27.
def F(n): if n == 1: return 2 return F(n - 1) + G(n - 1) def G(n): if n == 1: return 1 return 2 * F(n - 1) print(F(4) + G(4))Ответ: 27
Задача в формате экзамена: F(12) + G(12)
Алгоритм вычисления значений функций F(n) и G(n), где n — натуральное число, задан следующими соотношениями: F(1) = G(1) = 1; F(n) = F(n − 1) + 2 · G(n − 1), G(n) = F(n − 1) + G(n − 1) при n > 1. Чему равно значение выражения F(12) + G(12)?
Введите число.
Подсказка
Новые F и G считаются по старым значениям обеих функций — две def и @cache у каждой.
Решение
Записываем обе функции по определению и печатаем сумму: F(12) = 19 601, G(12) = 13 860.
from functools import cache @cachedef F(n): if n == 1: return 1 return F(n - 1) + 2 * G(n - 1) @cachedef G(n): if n == 1: return 1 return F(n - 1) + G(n - 1) print(F(12) + G(12))Ответ: 33461