Эффективный генератор Питона последовательности Фибоначчи
Я нашел этот вопрос, пытаясь получить самое короткое Pythonic-поколение этой последовательности (позже понял, что видел подобное в Python Enhancement Proposal ), и я не заметил, чтобы кто-нибудь еще подходил с моим конкретным решением (хотя верхний ответ становится близким, но все же менее элегантным), так что здесь, с комментариями, описывающими первую итерацию, потому что я думаю, что это может помочь читателям понять:
def fib():
a, b = 0, 1
while True: # First iteration:
yield a # yield 0 to start with and then
a, b = b, a + b # a will now be 1, and b will also be 1, (0 + 1)
и использование:
for index, fibonacci_number in zip(range(10), fib()):
print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))
печать:
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
(Для целей атрибуции я недавно заметил похожую реализацию в документации Python по модулям, даже используя переменные a и b, которые я сейчас вспоминаю, когда видел перед написанием этого ответа. Но я думаю, что этот ответ демонстрирует лучшее использование языка.)
Рекурсивно определенная реализация
Онлайн-энциклопедия целочисленных последовательностей рекурсивно определяет последовательность Фибоначчи как
F (n) = F (n-1) + F (n-2) с F (0) = 0 и F (1) = 1
Сжать это рекурсивное определение в Python можно следующим образом:
def rec_fib(n):
'''inefficient recursive function as defined, returns Fibonacci number'''
if n > 1:
return rec_fib(n-1) + rec_fib(n-2)
return n
Но это точное представление математического определения невероятно неэффективно для чисел, намного превышающих 30, потому что каждое вычисляемое число также должно рассчитываться для каждого числа ниже него. Вы можете продемонстрировать, насколько это медленно, используя следующее:
for i in range(40):
print(i, rec_fib(i))
Memoized рекурсия для эффективности
Это можно запомнить, чтобы повысить скорость (в этом примере используется тот факт, что аргумент ключевого слова по умолчанию является одним и тем же объектом при каждом вызове функции, но обычно по этой причине вы не будете использовать изменяемый аргумент по умолчанию) :
def mem_fib(n, _cache={}):
'''efficiently memoized recursive function, returns a Fibonacci number'''
if n in _cache:
return _cache[n]
elif n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n
Вы обнаружите, что запомненная версия намного быстрее и быстро превысит вашу максимальную глубину рекурсии, прежде чем вы даже сможете подумать, чтобы встать на чашку кофе. Вы можете увидеть, насколько быстрее это визуально, выполнив это:
for i in range(40):
print(i, mem_fib(i))
(Может показаться, что мы можем просто сделать следующее, но на самом деле это не позволяет нам использовать преимущества кэша, потому что он вызывает себя до вызова setdefault.)
def mem_fib(n, _cache={}):
'''don't do this'''
if n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n
Рекурсивно определенный генератор:
Поскольку я изучал Haskell, я натолкнулся на эту реализацию в Haskell:
fib@(0:tfib) = 0:1: zipWith (+) fib tfib
Самое близкое, я думаю, что я могу добраться до этого в Python на данный момент:
from itertools import tee
def fib():
yield 0
yield 1
# tee required, else with two fib()'s algorithm becomes quadratic
f, tf = tee(fib())
next(tf)
for a, b in zip(f, tf):
yield a + b
Это демонстрирует это:
[f for _, f in zip(range(999), fib())]
Впрочем, он может доходить только до предела рекурсии. Обычно 1000, тогда как версия на Haskell может доходить до сотен миллионов, хотя для этого используются все 8 ГБ памяти моего ноутбука:
> length $ take 100000000 fib
100000000