Рекурсия предлагает программистам удобный способ разбить более крупные проблемы на управляемые части. Рассмотрим итерационные и рекурсивные решения для суммы Фибоначчи.
# iterative
def fib_iterative(n):
if (n == 0):
return 0
elif (n == 1):
return 1
elif (n >1 ):
fn = 0
fn1 = 1
fn2 = 2
for i in range(3, n):
fn = fn1+fn2
fn1 = fn2
fn2 = fn
return fn
# recursive
def fib(n):
if n == 0:return 0
if n == 1:return 1
else: return fib(n-1) + fib(n-2)
Рекурсивные решения часто легче читать и писать для проблем ветвления. Обходы по деревьям, графам и математические ряды (часто) обрабатываются более интуитивно с помощью рекурсии.
Хотя это обеспечивает удобство, затраты времени на вычисление рекурсии для задач ветвления растут экспоненциально с увеличением значения n.
Давайте посмотрим на стек вызовов для fib (6)
Мы выполняем примерно вдвое больше операций на каждом последующем уровне дерева. Дает нам временную сложность O (2 ^ n).
Если мы внимательно рассмотрим наше дерево, вы заметите, что мы повторяем работу. fib (2) вычисляется пять раз, fib (3) вычисляется трижды и так далее. Хотя это не проблема для малых значений n, представьте себе количество повторяющейся работы при вычислении fib (1000). После того, как мы пересмотрим наше рекурсивное решение, попробуйте выполнить одну и ту же задачу (скажем, 20) для обеих версий и обратите внимание на значительную разницу во времени выполнения.
Конечно, есть хороший способ предотвратить повторяющуюся работу и сохранить наше элегантное решение?
Воспоминание: вы можете съесть свой торт и съесть его!
С помощью мемоизации мы можем «запоминать» (запоминать, сохранять) результат проблем, с которыми мы сталкивались раньше, и возвращать сохраненный результат вместо повторения вычислений.
Например, после вычисления fib (2) мы можем сохранить результат и использовать его в следующие четыре раза, когда будет встречаться fib (2).
Это сокращает время выполнения с O (2 ^ n) до O (n), потому что мы вычисляем каждое из fib (0)… fib (n) только один раз.
Один из способов добиться этого - использовать словарь.
__fib_cache = {}
def fib_memo(n):
if n in __fib_cache:
return __fib_cache[n]
else:
__fib_cache[n] = n if n < 2 else fib_memo(n-2) + fib_memo(n-1)
return __fib_cache[n]
И вуаля! Мы успешно запомнили рекурсивную функцию!
Однако мы можем пойти еще дальше и создать абстрактную мемоизацию для любой рекурсивной функции!
Декораторы: функции, использующие функции для выполнения других функций.
Декораторы известны как «функции высшего порядка»: функции, которые принимают другие функции в качестве параметров. Здесь мы будем использовать декоратор для обобщения мемоизации.
Вот оформленное решение:
def memoize(func):
cache = func.cache = {}
@functools.wraps(func)
def memoized_func(*args, **kwargs):
key = str(args) + str(kwargs)
if key not in cache:
cache[key] = func(*args, **kwargs)
return cache[key]
return memoized_func
@memoize
def fibonacci(n):
if n == 0:return 0
if n == 1:return 1
else: return fib(n-1) + fib(n-2)
Давайте разберем его построчно.
Наш декоратор - это функция, которая принимает другую функцию в качестве аргумента, мы объявляем ее как таковую в строке 1.
Затем мы объявляем словарь func.cache = {}, который объявлен как свойствоfunc. Здесь мы будем хранить каждый уникальный вызов, сделанный func.
Мы вернемся к @functools.wraps.
def memoized_func(*args, **kwargs): - Внутри декоратора мы определяем новую мемоизированную функцию на основе переданного func, и она принимает те же параметры, что и func. Мы называем эту новую версию memoized_func.
*args - ключевое слово, указывающее, что memoizer принимает произвольное количество аргументов, например, def memoize(one two three) или def memoize(just_one) оба допустимы. Аналогично *kwargs представляет произвольное количество аргументов ключевого слова (параметры, определенные при вызове функции), например. def memoize(one = 1, two = 2, three = 3). Примечание. Вы можете использовать эти специализированные параметры в любой функции.
Следующая строка объявляет key для нашего func.cache на основе заданных параметров. Если мы видели эту комбинацию параметров раньше, мы извлекаем результат из func.cache, в противном случае создаем новый ключ, используя исходный func, как он был определен (например, используя fib), и присваиваем его значение результату, например (сохранить результат fib(2)).
Последняя строка внутри memoized_func() возвращает результат единственного вызова func с заданными параметрами.
Последняя строка возвращает memoized_func(), который представляет измененную версию нашей исходной функции с добавленными (украшенными) функциями, то есть сохранением результата каждого нового вызова.
Наконец, мы помечаем нашу исходную функцию знаком @memoize. Обозначение «@» указывает компилятору передать функцию непосредственно под ним в функцию более высокого порядка с именем memoized_func, которая в нашем случае возвращает мемоизированную версию fibonacci(). Эта версия функции немедленно вернет результаты, которые мы вычислили ранее, в противном случае она вызовет исходную fib() функцию, чтобы определить, каким должно быть это число.
Что такое @ functools.wraps?
@functools.wraps - еще один декоратор, встроенный в Python. Он позволяет decoratormemoize хранить информацию, относящуюся к запомненной строке документации функции или имени функции, чтобы к информации можно было получить доступ позже. Если бы мы спросили у python fib.__name__ или fib.__doc__ (они встроены в свойства функций), без @functools.wraps мы бы вернули имя и строку документации для memoized_fib, а не самого fib. В целях отладки полезно иметь доступ к имени и строке документации исходной вызываемой функции, а не к функции украшения, поскольку один и тот же декоратор может применяться к множеству функций.
Попробуй сам!
В следующий раз, когда вы столкнетесь с рекурсивной функцией, подумайте, можно ли улучшить ее производительность с помощью мемоизации, а затем перенесите эту мемоизацию на другие функции, добавив декоратор!
