フィボナッチ数列の効率的な Pythonic ジェネレーター
このシーケンスの最短の 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、この回答を書く前に見たことを思い出しました。しかし、この回答は言語のより良い使用法を示していると思います。)
再帰的に定義された実装
Online Encyclopedia of Integer Sequencesは、フィボナッチ数列を次のように再帰的に定義しています。
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))
効率化のためのメモ化された再帰
速度を向上させるためにメモ化することができます (この例では、関数が呼び出されるたびにデフォルトのキーワード引数が同じオブジェクトであるという事実を利用していますが、通常は、まさにこの理由で変更可能なデフォルト引数を使用しません):
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 GB のメモリがすべて使用されます。
> length $ take 100000000 fib
100000000
n 番目のフィボナッチ数を取得するために反復子を使用する
コメント投稿者は次のように尋ねます。
イテレータに基づく Fib() 関数に関する質問: n 番目、たとえば 10 番目の fib 番号を取得したい場合はどうしますか?
itertools のドキュメントには、このためのレシピがあります。
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)
そしていま：
>>> nth(fib(), 10)
55
