Rubyでメモ化を使ってフィボナッチ数を求める

tech

最近友達と始めたRubyの勉強会でお題として、フィボナッチ数を求めるプログラムを書いてみました。
メモ化という仕組みを実装したり、そのメモ化をさらに改善したり、再帰じゃない方法で書いてみたりと色々面白かったので、ちょっとまとめておきます。

フィボナッチ数とは

フィボナッチ数は以下のように定義されます

N番目のフィボナッチ数をF(n)とする。
- n >= 0
- F(0) = 0
- F(1) = 1
- F(n) = F(n - 1) + F(n - 2)

F(0)からF(10)までは以下のようになります。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

詳しくは以下を参照。
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

再帰を使って実装

def fibonacci(n)
  if n < 2
    return n;
  else
    return fibonacci(n - 2) + fibonacci(n - 1);
  end
end

10.times{|n| puts "fibonacci(#{n}) : #{fibonacci(n)}"}

説明不要ですね。

メモ化を実装する

module Fibonacci
  @@memo = [0 , 1];

  def self.[](n)
    @@memo[n] = self[n - 1] + self[n - 2] unless @@memo[n];
    return @@memo[n];
  end
end

10.times{|n| p "fibonacci(#{n}) : #{Fibonacci[n]}"}

メモ化は計算途中を保存してくことで、再計算のコストを省略するというもの（だと思っています）
これで連続したフィボナッチ数を求めるときに計算量を大きく減らすことができます。


実はこのメモ化にはまだ改善の余地があります。

改善したメモ化

module Fibonacci
  @@memo = [0 , 1];

  def self.[](n)
    if @@memo.size <= n
      @@memo[n - 1] = self[n - 1] unless @@memo[n - 1];
      @@memo[n] = @@memo[n - 2] + @@memo[n - 1];
    end

    return @@memo[n];
  end
end

10.times{|n| p "fibonacci(#{n}) : #{Fibonacci[n]}"}

改善前のメモ化では(n - 1)と(n - 2)をそれぞれ再帰によって求めていました。しかし実際は(n - 1)だけを再帰を使って求めれば良いのです。(n - 2)については(n - 1)を求める過程で計算されるので、それを保存しておきます。というか(n - 1)を求める過程で計算した全てのフィボナッチ数を保存しておきます。


改善前のメモ化ではF(10)を求めた後にF(5)を求めると、再度計算が必要です。しかし改善したメモ化ではF(10)を求めるとF(10)以下の全てのフィボナッチ数を求めているので、F(5)は計算なしに求めることができます。


そこで調子にのってF(3000)とかを求めようとすると、以下のエラーがでます。

./fibo22.rb:8:in `[]': stack level too deep (SystemStackError)
	from ./fibo22.rb:8:in `[]'
	from ./fibo22.rb:18

再帰によるスタック積み過ぎとのこと(´・ω・｀)
というわけで、再帰を使わないフィボナッチプログラムを書いてみます。

再帰を使わない実装

def fibonacci(n)
  if n < 2
    return n;
  else
    p2 = 0; #二つ前のfibonacciを保存していく
    p1 = 1; #一つ前のfibonacciを保存していく

    2.upto(n){ p2 , p1 = p1 , p2 + p1 }

    return p1;
  end
end

5000.times{|n| fibonacci(n) }

F(5000)とかも余裕で求められます！再帰を使わず初めて書いてみましたが、コード量はそんなに変わらないですね。
ではさらにこれをメモ化してみます。

再帰を使わない実装をメモ化

module Fibonacci
  @@memo = [0 , 1];

  def self.[](n)
    #既にメモされている最大の値から計算開始
    #求めたい値が既に計算済みならこのループは実行されない
    @@memo.size.upto(n){|i| @@memo[i] = @@memo[i - 1] + @@memo[i - 2]}
    return @@memo[n];
  end
end

5000.times{|n| Fibonacci[n]}

ループの初期値に少し気をつけなければならないですが、凄く簡単に求めることができます。
速度的には再帰を使わない方が断然早いです。（そりゃそうですよね）


というわけで、フィボナッチ数だけでこんなに遊べました。数論(初頭整数論)の勉強してみたいなー。



ちょっと調べたら行列を使ってフィボナッチ数を簡単に求めることができるそうです。
http://d.hatena.ne.jp/qnighy/20090120/1232446370