フィボナッチ数と Python で遊んだ

README.md

手習（フィボナッチ数）

再帰による定義が有名なフィボナッチ数を複数の方法で計算して速度を比較する.

※2013年12月頃に Python 手習のため書いた短いコードをまとめたもの.

フィボナッチ数とは

フィボナッチ数 - Wikipedia 参照.

実装

• 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
$

fib_bench.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

# 定義に忠実なフィボナッチ数
def fib_orig(n):
  if n < 2:
    return n
  else:
    return fib_orig(n-1) + fib_orig(n-2)

# メモ化
def memoize(f):
  memo = {}
  def function(*args):
    if not args in memo:
      memo[args] = f(*args)
    return memo[args]
  return function

@memoize
def fib_memo(n):
  if n < 2:
    return n
  else:
    return fib_memo(n-1) + fib_memo(n-2)

# 非再帰
def fib_loop(n):
  a, b = 0, 1
  while(n > 0):
    a,b = b, a+b
    n -= 1
  return a
  


# 実行速度計測
# 再帰の深さの上限を増やしておく
import sys
sys.setrecursionlimit(10000)

n = 40

import time

print 'fib_orig(%d) \t =' % (n),
start = time.time()
print fib_orig(n),
end = time.time()
print '\t%f s' % (end - start)

print 'fib_memo(%d) \t =' % (n),
start = time.time()
print fib_memo(n),
end = time.time()
print '\t%f s' % (end - start)

print 'fib_loop(%d) \t =' % (n),
start = time.time()
print fib_loop(n),
end = time.time()
print '\t%f s' % (end - start)