Hash でお手軽にメモ化 - はやくプログラムになりたい

Hash#new に2引数のブロックを渡すと，存在しないキーにアクセスしようとするとそのブロックが呼ばれるようにできることは前から知っていたけれど，それをキャッシュに利用できるのは知らなかった．

まず，Hash#new はこんな感じで使える．

# 存在しないキーにアクセスするとキーの2倍の値が返ってくるハッシュを作成
h = Hash.new do |_, key|
  key * 2
end

p h[3]      #=> 6
p h['poyo'] #=> "poyopoyo"

# キーが存在する場合はその値を返すのでブロックは呼ばれない
h[3] = 10
p h[3]      #=> 10

これを利用して，フィボナッチ数列を格納するハッシュを作成してみる．

fib = Hash.new do |hash, key|
  hash[key] = hash[key-1] + hash[key-2] # 計算結果を自分自身に代入する
end
fib[0] = 1
fib[1] = 1

p fib[100] #=> 573147844013817084101
p fib      #=> {0=>1, 1=>1, 2=>2, 3=>3, 4=>5, 5=>8, 6=>13, ...

Hash.new の第1引数には自分自身が渡るため，それに代入することで結果を自分自身に蓄えておくことが出来る．キーと，キーに対応する計算結果を値に持っておけば，2度目以降はすでにある要素にアクセスするだけで計算結果を得ることが出来る．これによって，フィボナッチ数列の第100項もほぼ一瞬で計算できる．なんか良いなぁと思うのは，ブロックの中に

fib[i] = fib[i-1] + fib[i-2]

という漸化式をそのまま書くことができる点だ．

外部で fib[0] = 1 という具合に初期化するのが気持ち悪ければ，

fib = Hash.new do |hash, key|
  if key == 0 || key == 1
    1
  else
    hash[key] = hash[key-1] + hash[key-2]
  end
end

と，ブロックの中に書いてしまうことも出来る．

ただし，普通のメソッドと見た目が全然違うため，実際に書くなら fib をラップするメソッドを作って，

def fib(i)
  @fib ||= Hash.new do |hash, key|
    if key == 0 || key == 1
      1
    else
      hash[key] = hash[key-1] + hash[key-2]
    end
  end
  @fib[i]
end

と書くか，簡単に任意のメソッドをメモ化できるようになる memoizer というライブラリを使ったほうが良い．（memoize という gem もあるが，実装を見てみるとメモをファイルにダンプしたりしていてパフォーマンスが悪そうだった）