■
Python.use(better) 《記事一覧》
ベンチマーク Fibonacci
《著》後藤いるか・森こねこ《監修》小泉ひよ子とタマゴ倶楽部
第0版♪1988/03/30 ● 第1版♪2000/05/23 ● 更新♪2008/10/28
事例：timeit を使って
まず、手抜きで timeit モジュールを利用しました。
from timeit import * S = """ def fib(n): if n==0: return 0 elif n==1: return 1 return fib(n-2)+fib(n-1) print "%%8d"%%fib(%d),"->", """ for e in range(40): print "%2d:"%e, Timer(S%e).timeit(1)
やはり、試行回数が１（timeit の引数）では、ms 程の微妙な変化を捉えるのには適さないようです（10 程に設定すると単調増加の兆候が見られます）。
出力結果
>>> 0: 0 -> 0.0632491111755 1: 1 -> 0.0632839202881 2: 1 -> 0.0638530254364 3: 2 -> 0.0638959407806 4: 3 -> 0.0641460418701 5: 5 -> 0.0807800292969 6: 8 -> 0.0635600090027 7: 13 -> 0.0793199539185 8: 21 -> 0.0638210773468 9: 34 -> 0.0638799667358 10: 55 -> 0.0643339157104 11: 89 -> 0.0638649463654 12: 144 -> 0.0631790161133 13: 233 -> 0.0631620883942 14: 377 -> 0.0635581016541 15: 610 -> 0.0814418792725 16: 987 -> 0.0635118484497 17: 1597 -> 0.0638928413391 18: 2584 -> 0.0665688514709 19: 4181 -> 0.0683479309082 20: 6765 -> 0.0644021034241 21: 10946 -> 0.0638990402222 22: 17711 -> 0.0642380714417 23: 28657 -> 0.0800960063934 24: 46368 -> 0.149417161942 25: 75025 -> 0.147248983383 26: 121393 -> 0.247319936752 27: 196418 -> 0.34779882431 28: 317811 -> 0.481822967529 29: 514229 -> 0.749199867249 30: 832040 -> 1.16822600365 31: 1346269 -> 1.95424485207 32: 2178309 -> 3.04078888893 33: 3524578 -> 4.84699010849 34: 5702887 -> 7.691603899 35: 9227465 -> 12.3758189678 36: 14930352 -> 21.5737960339 37: 24157817 -> 32.6966710091 38: 39088169 -> 51.9828338623 39: 63245986 -> 85.1851811409 ...
事例：time を使って
次に、手抜きをせずに time モジュールを利用します。
from time import time def spy(f): def g(*args): t0 = time(); r = f(*args); t1 = time() return r,t1-t0 return g def fib(n): if n==0: return 0 elif n==1: return 1 return fib(n-2)+fib(n-1) @spy def ex(n): return fib(n) for e in range(40): r,t = ex(e) print "%2d: %8d -> %.10f"%(e,r,t)
トリボナッチ、テトラボナッチの試行結果については省略します。
出力結果
0: 0 -> 0.0000030994 1: 1 -> 0.0000040531 2: 1 -> 0.0000059605 3: 2 -> 0.0000078678 4: 3 -> 0.0000131130 5: 5 -> 0.0000140667 6: 8 -> 0.0000209808 7: 13 -> 0.0000319481 8: 21 -> 0.0000510216 9: 34 -> 0.0000791550 10: 55 -> 0.0002269745 11: 89 -> 0.0002009869 12: 144 -> 0.0003168583 13: 233 -> 0.0005798340 14: 377 -> 0.0007901192 15: 610 -> 0.0012800694 16: 987 -> 0.0020878315 17: 1597 -> 0.0018708706 18: 2584 -> 0.0050859451 19: 4181 -> 0.0049960613 20: 6765 -> 0.0081200600 21: 10946 -> 0.0184180737 22: 17711 -> 0.0212621689 23: 28657 -> 0.0398969650 24: 46368 -> 0.0560359955 25: 75025 -> 0.0918719769 26: 121393 -> 0.1460170746 27: 196418 -> 0.2342529297 28: 317811 -> 0.3900308609 29: 514229 -> 0.6087081432 30: 832040 -> 1.0280330181 31: 1346269 -> 1.5868830681 32: 2178309 -> 2.5655310154 33: 3524578 -> 4.1797921658 34: 5702887 -> 6.6807990074 35: 9227465 -> 10.8573260307 36: 14930352 -> 17.6869089603 37: 24157817 -> 28.8623528481 38: 39088169 -> 47.6617209911 39: 63245986 -> 79.1336889267 ...
余録
デモとしては「１分」程で結果が得られるものが望ましいと考え、その適切な回数（ここでは 40 あたり）を見極めるのが目的でした。
