再帰による定義が有名なフィボナッチ数を複数の方法で計算して速度を比較する.
※2013年12月頃に Python 手習のため書いた短いコードをまとめたもの.
fib_orig()
: 定義通りの素直な実装.fib_memo()
: 途中結果をメモに保存して不要な再計算を避けた実装.fib_loop()
: 再帰でなく while ループで書いた実装
- MacBook Air (13-inch, Early 2015)
- プロセッサ 1.6 GHz Intel Core i5
- メモリ 8 GB 1600 MHz DDR3
$ python fib_bench.py
fib_orig(40) = 102334155 43.581925 s
fib_memo(40) = 102334155 0.000303 s
fib_loop(40) = 102334155 0.000008 s
$
大きい引数で比較(時間がかかりすぎるので orig
以外)
$ python fib_bench.py
fib_memo(200) = 280571172992510140037611932413038677189525 0.000719 s
fib_loop(200) = 280571172992510140037611932413038677189525 0.000027 s
$