В сегодняшней статье мы рассмотрим как оптимизировать время выполнения программы в Python c помощью операции кэширования.
Мы рассмотрим данную операцию на примере рекурсивной функции в Python. Но сначала — пара слов о рекурсии.
Рекурсия — это понятие в программировании, при котором функция вызывает сама себя один или несколько раз. Данные типы функций часто сталкиваются с проблемами скорости, из-за того, что функция постоянно вызывает сама себя. Операция рекурсии занимает достаточно много памяти из за постоянного повторения одних и тех же шагов. Кэшировнаие или Мемоизация (англ. memoization от англ. memory и англ. optimization) помогает этому процессу, сохраняя значения, которые уже были рассчитаны для последующего использования. Давайте сначала вспомним что такое рекурсивные функции.
Давайте посмотрим несколько примеров!
Написание факториальной функции.
Факториалы — один из самых простых примеров рекурсии, и является результатом умножения всех чисел меньших на единицу чем данное:
def factorial(n):
# установите базовый случай!
if n <= 1:
return 1
else:
return factorial( n – 1 ) * n
print( factorial(5) ) # результат от умножения 5 * 4 * 3 * 2 * 1
# вывод
120
Последовательность Фибоначчи.
Последовательность Фибоначчи — одна из самых известных формул в математике. Это также
одна из самых известных рекурсивных функций в программировании. Каждое число в
последовательность — это сумма двух предыдущих чисел, таких, что fib(5) = fib(4) + fib(3).
Вычислим ее для 20.
from datetime import datetime
import time
def fib(n):
if n <= 1:
return n
else:
return fib( n - 1 ) + fib( n - 2 )
start_time = datetime.now()
print(fib(35))
print(datetime.now() - start_time)
# вывод
9227465
0:00:17.647056 # время вычисления
Как видно на вычисление результата для числа 35, ушло целых 17 секунд.
По мере того, как растет количество передаваемых данных, растет структура и количество
рекурсивных вызовов . Он экспоненциальный, что может значительно замедлить работу программы. Даже
попытка выполнить fib(40) может занять пару минут, а fib(100) обычно не работает
из-за проблем с максимальной глубиной рекурсии. Что приводит нас к нашей следующей теме о том, как
решить эту проблему… кэширование .
Понимание мемоизации.
Когда вы заходите на веб-страницу в первый раз, вашему браузеру требуется некоторое время, чтобы загрузить
изображения и файлы, необходимые странице. Когда вы во второй раз зайдете на ту же самую страницу, она
обычно загружается намного быстрее. Это связано с тем, что ваш браузер использует технику, известную как
«кэширование».
В вычислительной технике мемоизация — это метод оптимизации, используемый в первую очередь для ускорения
программы, сохраняя результаты ранее вызванных функций и возвращая сохраненный результат при попытке вычислить ту же последовательность. Это просто известно как кэширование.
Использование мемоизации.
Чтобы применить ее к последовательности Фибоначчи, мы должны понять, какой наилучший метод кэширования значений. В Python словари дают нам возможность для хранения значений на основе заданного ключа. Благодаря скорости и уникальной ключевой структуре словарей мы можем использовать их для хранения
значение каждой последовательности Фибоначчи. Таким образом, как только одна последовательность, такая как fib(3), рассчитывается, его не нужно вычислять снова. Он просто сохраняется в кэше и
извлекаются по мере необходимости. Давайте попробуем:
cache = { }
def fib(n):
if n in cache:
return cache[ n ]
result = 0
if n < = 1:
result = n
else:
result = fib( n – 1 ) + fib( n -2 )
cache[ n ] = result
return result
print( fib(50) )
Использование @lru_cache
Теперь, когда мы знаем, как самостоятельно создать систему кэширования, давайте воспользуемся встроенными средствами Python.
способ запоминания. Он известен как lru_cache.
from functools import lru_cache
@lru_cache( ) # встроенный инструмент кэширования
def fib(n):
if n <= 1:
return n
else:
return fib( n – 1 ) + fib( n – 2 )
fib(50)
Мы получим тот же результат, что и в предыдущем примере, но на этот раз с меньшим количеством строк.
Таким образом, язык Python предоставляет возможность оптимизации кода библиотекой functools.