フィボナッチ数列
フィボナッチ数列について。
def fib(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return b print([fib(i) for i in range(10)]) # [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
メモ化した場合
fib_memo = {} def fib(n): if n < 3: return 1 if n not in fib_memo: fib_memo[n] = fib(n-1) + fib(n-2) return fib_memo[n] print(fib(10)) # 55
このメモ化だと、fib_memoという辞書が使用後も残ってしまったり、
n>1000だとrecursive errorが出たりする。
@lru_cacheデコレータ(Least-recently-used cache decorator)を使う。
関数の引数と戻り値を記憶し、同じ引数で呼ばれたら関数を実行せずに値を返す。
同じ引数で何度も呼び出す関数だと劇的に速くなる。
counter = 0 def fib1(n): global counter counter += 1 if n in [0, 1]: return 1 return fib1(n - 1) + fib1(n - 2) print(fib1(24)) print(counter, "回の関数呼び出し") # 75025 # 150049 回の関数呼び出し from functools import lru_cache counter = 0 @lru_cache(maxsize=1024) def fib2(n): global counter counter += 1 if n in [0, 1]: return 1 return fib2(n - 1) + fib2(n - 2) print(fib2(24)) print(counter, "回の関数呼び出し") # 75025 # 25 回の関数呼び出し
lru_cacheなしだと関数を15万回呼び出していたが、lru_cacheありだと25回で済む。
一般項の公式
より、ループなしでフィボナッチ数列の項を求めることもできます。
def fib(n): f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5 return int(f) print(fib(10)) # 55
2項間の比を調べてみると
import numpy as np import matplotlib.pyplot as plt x = np.arange(20) y = np.array([fib(i + 1) / fib(i) for i in range(20)]) plt.plot(x, y, "ro-") plt.show()
1.62くらいに収束してます。