Wydajny Pythonic generator ciągu Fibonacciego
Znalazłem to pytanie, próbując uzyskać najkrótszą generację tej sekwencji w Pythonie (później zdałem sobie sprawę, że widziałem podobne w propozycji rozszerzenia Pythona ) i nie zauważyłem nikogo innego wymyślającego moje konkretne rozwiązanie (chociaż najlepsza odpowiedź zbliża się, ale jeszcze mniej elegancko), więc oto jest, z komentarzami opisującymi pierwszą iterację, bo myślę, że to może pomóc czytelnikom zrozumieć:
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)
i zastosowanie:
for index, fibonacci_number in zip(range(10), fib()):
print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))
wydruki:
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
(Dla celów atrybucji zauważyłem ostatnio podobną implementację w dokumentacji Pythona na temat modułów, nawet przy użyciu zmiennych ai b, którą teraz pamiętam, widziałem przed napisaniem tej odpowiedzi. Ale myślę, że ta odpowiedź pokazuje lepsze użycie języka.)
Implementacja definiowana rekurencyjnie
Online Encyclopedia of Integer sekwencji definiuje Fibonacciego rekurencyjnie jako
F (n) = F (n-1) + F (n-2) przy F (0) = 0 i F (1) = 1
Zwięzłe zdefiniowanie tego rekurencyjnego w Pythonie można wykonać w następujący sposób:
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
Ale ta dokładna reprezentacja definicji matematycznej jest niewiarygodnie nieefektywna dla liczb znacznie większych niż 30, ponieważ każda obliczana liczba musi również obliczyć każdą liczbę poniżej niej. Możesz zademonstrować, jak powolne jest to, używając:
for i in range(40):
print(i, rec_fib(i))
Zapamiętana rekursja dla wydajności
Można go zapamiętać w celu zwiększenia szybkości (w tym przykładzie wykorzystuje się fakt, że domyślny argument słowa kluczowego jest tym samym obiektem za każdym razem, gdy wywoływana jest funkcja, ale normalnie nie używałbyś zmiennego argumentu domyślnego z tego właśnie powodu):
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
Przekonasz się, że zapamiętana wersja jest znacznie szybsza i szybko przekroczy maksymalną głębokość rekursji, zanim będziesz mógł nawet pomyśleć o wstaniu na kawę. Możesz zobaczyć, o ile szybciej jest to wizualnie, robiąc to:
for i in range(40):
print(i, mem_fib(i))
(Może się wydawać, że możemy po prostu wykonać poniższe czynności, ale w rzeczywistości nie pozwala nam to skorzystać z pamięci podręcznej, ponieważ wywołuje się przed wywołaniem 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
Generator definiowany rekurencyjnie:
Kiedy uczyłem się Haskell, natknąłem się na tę implementację w Haskell:
fib@(0:tfib) = 0:1: zipWith (+) fib tfib
Wydaje mi się, że najbliżej tego, co w tej chwili mogę uzyskać w Pythonie, jest:
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
To pokazuje:
[f for _, f in zip(range(999), fib())]
Może jednak wzrosnąć tylko do limitu rekursji. Zwykle 1000, podczas gdy wersja Haskell może dochodzić do 100 milionów, chociaż wykorzystuje do tego całe 8 GB pamięci mojego laptopa:
> length $ take 100000000 fib
100000000
Zużywanie iteratora w celu uzyskania n-tej liczby Fibonacciego
Komentator pyta:
Pytanie do funkcji Fib (), która jest oparta na iteratorze: a co jeśli chcesz otrzymać n-ty, na przykład 10-ty numer fib?
Dokumentacja itertools zawiera przepis na to:
from itertools import islice
def nth(iterable, n, default=None):
"Returns the nth item or a default value"
return next(islice(iterable, n, None), default)
i teraz:
>>> nth(fib(), 10)
55
