メモ化を知った

はじめに

あんまりRuby関係ないんですが、一応、The RSpec Bookを読んでいて知ったのがきっかけなので…。

あらすじ

The RSpec Book のletの解説には以下のように記述されています。

sample.rb

   describe "テストコードはてきとう" do
     let(:test) { "TEST" }
     it "test let" do
       test.should == "TEST"
     end
   end

メソッドが最初に呼び出されたときに戻り値がキャッシュされ、それ以降、同じスコープ内でメソッドが呼び出されるたびにキャッシュされた値が返されることを意味します。

これをメモ化というそうです。で、メモ化って？

一番簡単なメモ化

調べてみると、だいたいフィボナッチ数を求める例が多い。なのでn番目のフィボナッチ数を求めるメソッドを書いてみる。

普通に書いた場合

fib1.rb

def f(n)
  if n <= 1 then
    n
  else
    f(n-1) + f(n-2)
  end
end

実行していくと、己のPCスペックではf(30) = 832040 くらいからマシンがもたついてきた。

これを メモ化 してみる。

メモ化した場合

fib2.rb

# こっちは変わらず
def f(n)
  if n <= 1 then
    n
  else
    f(n-1) + f(n-2)
  end
end
def f_memo(n)
  @cache ||= []
  @cache[n] ||= f(n)
end

実行すると、最初の一発目は同じくらい遅いんだけど、一回実行すればキャッシュとして @cache に格納されるので二回目以降はバク速で求められる。

||= とは

上の例の @cache[n] ||= f(n) は @cache[n] = @cache[n] || f(n) と同義。@cache[n]が真ならば@cache[n]を返す。偽ならnのフィボナッチ数を求める。 @cache[n]が真ならば、f(n)は評価しない、実行しない 。だから早い。

||=の例。

irb(main):001:0> a          # 未定義の時はエラー
NameError: undefined local variable or method `a' for main:Object
from (irb):1
from C:/rubies/Ruby-193-p0/bin/irb:12:in `<main>'
irb(main):002:0> a ||= 500  # a || 500 a は偽なので500
=> 500
irb(main):003:0> a
=> 500
irb(main):004:0> b = 0
=> 0
irb(main):005:0> b
=> 0
irb(main):006:0> b ||= 500  # b || 500 b は真なので0のまま
=> 0
irb(main):007:0> b
=> 0

…って所まで調べて、初めてのRubyを読み返してみたらバッチリ書いてあるし！！

初期化イディオム として紹介されていました。。。