メモ化でフィボナッチ数列(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}
仕組み
値が設定されていないハッシュ要素を参照するとその都度ブロックを 実行し、その結果を返します。 ブロックにはそのハッシュとハッシュを参照したときのキーが渡されます
とあるように、
RubyのHashオブジェクトを作成するときにブロックを渡すとdefault_proc
を設定することができる。
procに渡される引数は2つで、1つ目がself、2つ目がkeyとして指定した値になる。
設定したdefault_proc
は実行時、指定したkeyが無い場合にcallされる。
丁度@foo ||= bar
みたいな処理になるイメージ。
処理内容
こういう計算処理系は苦手なので処理内容も書いてみた。
- valの値
- 0
- fibo[0]
- 0
- fibo == {}
- fibo[0]
- 1
- fibo[1]
- 1
- fibo == {}
- fibo[1]
- 2
- fibo[2] = fibo[1](== 1) + fibo[0](== 0)
- fibo[2] = 1 + 0
- fibo == {2=>1}
- fibo[2] = fibo[1](== 1) + fibo[0](== 0)
- 3
- fibo[3] = fibo[2](== 1) + fibo[1](== 1)
- fibo[3] = 1 + 1
- fibo == {2=>1,3=>2}
- fibo[3] = fibo[2](== 1) + fibo[1](== 1)
- 4
- fobo[4] = fibo[3](== 2) + fibo[2](== 1)
- fibo[4] = 2 + 1
- fibo == {2=>1,3=>2,4=>3}
- fobo[4] = fibo[3](== 2) + fibo[2](== 1)
- 5
- fibo[5] = fibo[4](== 3) + fibo[3](== 2)
- fibo[5] = 3 + 2
- fibo == {2=>1,3=>2,4=>3,5=>5}
- fibo[5] = fibo[4](== 3) + fibo[3](== 2)
- 6
- fibo[6] = fibo[5](== 5) + fibo[4](== 3)
- fibo[6] = 5 + 3
- fibo == {2=>1,3=>2,4=>3,5=>5,6=>8}
- fibo[6] = fibo[5](== 5) + fibo[4](== 3)
- 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}
- fibo[7] = fibo[6](== 8) + fibo[5](== 5)
- 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}
- fibo[8] = fibo[7](== 13) + fibo[6](== 8)
- 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}
- fibo[9] = fibo[8](== 21) + fibo[7](== 13)
- 0