メモ化でフィボナッチ数列(Ruby)

ちょっと調べたのでメモがてら書く。

実装

fibo = Hash.new do |hash, num|
  if num < 2
    num
  else
    hash[num] = hash[num - 1] + hash[num - 2]
  end
end

10.times { |val| puts fibo[val] }
puts fibo

実行結果

0
1
1
2
3
5
8
13
21
34

{2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34}

仕組み

• singleton method Hash.new

値が設定されていないハッシュ要素を参照するとその都度ブロックを 実行し、その結果を返します。 ブロックにはそのハッシュとハッシュを参照したときのキーが渡されます

とあるように、
RubyのHashオブジェクトを作成するときにブロックを渡すとdefault_procを設定することができる。

procに渡される引数は2つで、1つ目がself、2つ目がkeyとして指定した値になる。

設定したdefault_procは実行時、指定したkeyが無い場合にcallされる。

丁度@foo ||= barみたいな処理になるイメージ。

処理内容

こういう計算処理系は苦手なので処理内容も書いてみた。

• valの値
  • 0
    • fibo[0]
      • 0
    • fibo == {}
  • 1
    • fibo[1]
      • 1
    • fibo == {}
  • 2
    • fibo[2] = fibo[1](== 1) + fibo[0](== 0)
      • fibo[2] = 1 + 0
    • fibo == {2=>1}
  • 3
    • fibo[3] = fibo[2](== 1) + fibo[1](== 1)
      • fibo[3] = 1 + 1
    • fibo == {2=>1,3=>2}
  • 4
    • fobo[4] = fibo[3](== 2) + fibo[2](== 1)
      • fibo[4] = 2 + 1
    • fibo == {2=>1,3=>2,4=>3}
  • 5
    • fibo[5] = fibo[4](== 3) + fibo[3](== 2)
      • fibo[5] = 3 + 2
    • fibo == {2=>1,3=>2,4=>3,5=>5}
  • 6
    • fibo[6] = fibo[5](== 5) + fibo[4](== 3)
      • fibo[6] = 5 + 3
    • fibo == {2=>1,3=>2,4=>3,5=>5,6=>8}
  • 7
    • fibo[7] = fibo[6](== 8) + fibo[5](== 5)
      • fibo[7] = 8 + 5
    • fibo == {2=>1,3=>2,4=>3,5=>5,6=>8,7=>13}
  • 8
    • fibo[8] = fibo[7](== 13) + fibo[6](== 8)
      • fibo[8] = 13 + 8
    • fibo == {2=>1,3=>2,4=>3,5=>5,6=>8,7=>13,8=>21}
  • 9
    • fibo[9] = fibo[8](== 21) + fibo[7](== 13)
      • fibo[9] = 21 + 13
    • fibo == {2=>1,3=>2,4=>3,5=>5,6=>8,7=>13,8=>21,9=>34}

参考

• RubyのHash.default_procを用いたメモ化再帰
• singleton method Hash.new
• instance method Hash#default_proc