フィボナッチ数列を再帰で組んでみた -> 行列実装に完敗

数列、勉強しないとな〜と思ってネットを検索していたらフィボナッチ数列発見。
フィボナッチ数列と言えば、この本を思い出しますｗ

数学ガール
posted with amazlet at 11.05.14
結城浩
ソフトバンククリエイティブ
売り上げランキング: 2487
Amazon.co.jp で詳細を見る

それはともかく･･･気になるページを見つけました。
O(log n)でフィボナッチ数を求める - 趣味的にっき

ふむ･･･O(log n)で計算できるってかなり速いのね･･･。

これまであまり実行速度とか気にしてプログラムを組んでこなかったので、いい練習だと思って真面目に再帰を行うメソッドとメモ化再帰を行うメソッドの２つを作ってみました。

# 再帰を使った場合（指数関数時間）
def fib3(n)
  return 0 if n == 0
  return 1 if n == 1
  return fib3(n-2) + fib3(n-1)
end

# 動的計画法？を使った場合
$memo = Hash.new
def fib4(n)
  return 0 if n == 0
  return 1 if n == 1

  return $memo[n] if $memo.key?(n) == true
  $memo[n] = fib4(n-2) + fib4(n-1)
  return $memo[n]
end

こいつらと、リンク先のメソッドで速度を見たらどうなるんだろうと思ったので計測もしてみました。
fib1, fib2のメソッドはリンク先と同じなのでそちらで確認してください。ちなみに、fib1はループ内でメモ化を使ったプログラム、fib2はベクトルを使ったプログラムです。
速度的には太刀打ちできないと思いますが果たして･･･

n = 35のときの結果

user system total real
fib1(35): 0.000000 0.000000 0.000000 ( 0.000000)
fib2(35): 0.000000 0.000000 0.000000 ( 0.000000)
fib3(35): 39.813000 0.031000 39.844000 ( 40.299296)
fib4(35): 0.000000 0.000000 0.000000 ( 0.000000)
9227465

再帰を使ったものは、この時点で40秒くらいかかってます。他の関数は時間が計測できないくらい早いですね。

動的計画法のものと差を出すためにもっと大きい値を与えてみました。

n = 10,000のときの結果

user system total real
fib1(10000): 0.047000 0.015000 0.062000 ( 0.062511)
fib2(10000): 0.000000 0.000000 0.000000 ( 0.000000)
fib4(10000): 0.110000 0.016000 0.126000 ( 0.125024)

負けてますね（当たり前）。メソッド呼び出しのオーバヘッドとハッシュのオーバヘッドってこんなもんなんでしょうか･･･。

本当はもっと大きな値で測定しようと思ったのですが、これ以上*1にするとSystemStackErrorが発生するので測定できませんでした。
それにしても、O(log n)のアルゴリズムは早いですね･･･。

これだけですが、かなり勉強になりました。再帰を使うと数学の定義そのままで実装ができることとか、単純なメモ化で効率が一気に上がることとか。あと、実は再帰を実際に書いてみたのも初めてだったり^^;
O記法って本当なんだな、というのを実際に動かして確認するのも初めてでした･･･。

やっぱり、自分でプログラムを動かさないといけないですね･･･。