Контекст
Вы разрабатываете программу для оптимизации вычислений чисел Фибоначчи. Числа Фибоначчи вычисляются рекурсивной функцией, каждое число равно сумме двух предыдущих чисел. Однако вы заметили, что при больших значениях чисел Фибоначчи вычисления занимают значительное время, так как многие значения вычисляются повторно. Вам поручено создать декоратор, который кэширует результаты вызова функции и позволяет избежать повторных вычислений для одних и тех же аргументов.
Задача
Создайте декоратор, который кэширует (сохраняет для дальнейшего использования) результаты вызова функции и, при повторном вызове с теми же аргументами, возвращает сохранённый результат.
Примените его к рекурсивной функции вычисления чисел Фибоначчи. В итоге декоратор должен проверять аргументы, с которыми вызывается функция, и, если такие аргументы уже использовались, должен вернуть сохранённый результат вместо запуска расчёта.
Советы
- Для хранения результатов удобно использовать словарь, так как поиск элементов внутри словаря будет иметь сложность, равную в среднем O(1).
- При этом не стоит хранить все вычисления в одном словаре, созданном снаружи функций (в глобальной области видимости). Лучше создавать отдельные словари для каждой декорируемой функции.
#Задача решается с помощью @lru_cache модуля functools
def number_cache(func):
"""Декоратор кэширует полученные ранее занчения и возвращает их"""
cache = dict()
def inner(*args, **kwargs):
if args in cache:
return cache[args]
else:
value = func(*args, **kwargs)
cache[args] = value
return value
return inner
@number_cache
def fibonacci(number):
if number <= 1:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
# Вычисление числа Фибоначчи с использованием кеширования
print(fibonacci(10)) # Результат будет кеширован
# Повторное вычисление числа Фибоначчи с теми же аргументами
print(fibonacci(10)) # Результат будет взят из кеша
# Вычисление числа Фибоначчи с другим аргументом
print(fibonacci(5)) # Результат будет вычислен и закеширован