メモ化を知った

この投稿はRuby Advent Calendar 2012の16日目の記事としてQiitaに投稿したものです。

はじめに

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

あらすじ

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

   describe "テストコードはてきとう" do

     let(:test) { "TEST" }

     it "test let" do

       test.should == "TEST"

     end

   end

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

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

一番簡単なメモ化

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

普通に書いた場合

def f(n)

  if n <= 1 then

    n

  else

    f(n-1) + f(n-2)

  end

end

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

これを メモ化 してみる。

メモ化した場合

# こっちは変わらず

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を読み返してみたらバッチリ書いてあるし！！

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