Memoize

ruby_Hash_memoize

この関数は毎回新しいオブジェクトを作って返す（でも文字列としての値は同じ）。

 
def oid
    @o = "aaa"
    puts "#{@o} #{@o.object_id}"
end
 
> oid
aaa 70116235649760
=> nil
 
> oid
aaa 70116235752500
=> nil
 

一度作ったオブジェクトを繰り返し参照するようにするには ||= で2回目以降の代入を避ける。

 
def oid
    @o ||= "aaa"
    puts "#{@o} #{@o.object_id}"
end
 
> oid
aaa 70116235752500
=> nil
 
> oid
aaa 70116235752500
=> nil
 

このことを踏まえて、Hash.new を使ったメモ化の手法を見てみよう。

まず Hash.new は「未定義の key を要求された時にデフォルトで返す value を予約できる」というものだ。

この「予約できる」のは単なる値に限らない。

つまりコードブロックも予約できるのだ。

 
> h = Hash.new {|hash, key| hash[key] = "#{key} #{key.object_id}"}
=> {}
 
# 存在しない key が呼び出された時にだけコードブロックが実行される 
> h["aaa"]
=> "aaa 70116240527500"
 
# だから（というか Hash とはそういうものだが）同じ key で再度呼び出しても
# その object_id は変わらない
> h["aaa"]
=> "aaa 70116240527500"
 

メモ化の例としてこんな状況を考えよう。

テキストが何万個とある。でも、それを編集する正規表現は限定されている。

つまり正規表現での置換の部分をメモ化する。

 
# 比較のためにメモ化なしバージョンも定義する
def uncached_replace(str)
    str.gsub(/(\w)\w+/, "\\1")
end
 
def cached_replace(str)
    # この関数が初めて呼ばれた時に Hash が定義される
    # key(この場合 str) に対する処理が予約されると言い換えてもいい
    @rep ||= Hash.new do |h, k|
        h[k] = k.gsub(/(\w)\w+/, "\\1")
    end
 
    # 未知の str に対しては予約された処理を実行して Hash に登録した上で結果を返す
    # 既知の str に対しては単に Hash にメモ化済みの値を返す	
    @rep[str]
end
 

ベンチマークを測って比べてみよう。

 
require "benchmark"
 
# test sample
# この文字列を、
text = <<EOT
aaa aaa aaa
bbb bbb bbb
ccc ccc ccc
EOT
# => "aaa aaa aaa\nbbb bbb bbb\nccc ccc ccc\n"
# 50万回繰り返し処理させる
N = 500000
 
Benchmark.bmbm do |bm|
    bm.report("uncached") do
        N.times{ uncached_replace(text) }
    end
    bm.report("cached") do
        N.times{ cached_replace(text) }
    end
end
 
# 実行結果
               user     system      total        real
uncached   6.320000   0.150000   6.470000 (  6.456125)
cached     0.120000   0.000000   0.120000 (  0.126552)
 

頻繁に同じ処理の呼び出しがある場合はメモ化が有効だ。

なお Memoizable というモジュールは、上記のようなメモ化を自動で行ってくれる。

コードが複雑になるのを避けたいときはこのようなモジュールを使うのがベターだ。

ただし、モジュール側のオブジェクト生成によるオーバーヘッドがあるので、自作したメモ化より速度は劣る。

http://rubydoc.info/gems/memoizable/0.4.2/frames

おまけ。

文字列オブジェクトの生成を重複させないようにするだけでも速度は改善される。

 
def uncached_but_string_once_replace(str)
    @rgx ||= /(\w)\w+/
    @rep ||= "\\1"
    str.gsub(@rgx, @rep)
end
 
Benchmark.bmbm do |bm|
    bm.report("uncached") do
        N.times{ uncached_replace(text) }
    end
    bm.report("once") do
        N.times{ uncached_but_string_once_replace(text) }
    end
end
 
               user     system      total        real
uncached   6.280000   0.100000   6.380000 (  6.383904)
once       4.390000   0.030000   4.420000 (  4.410662)