読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

プログラミングコンテストの練習

Google Code Jamが通常のプログラムコンテストと違うのは、ローカルで答えを出せばいい点、
つまり標準ではないライブラリが使える!!!わおー
ということで、役に立つかはわからないけど、自分が知っているRuby gemを紹介させてください。
今回はmemoize。

http://rubygems.org/gems/memoize

DPなんかで再帰的(部分問題に帰着される)に定義された関数に対し、
1回計算した引数の場合の結果をハッシュすることで高速化してくれます。
これを使うと自前でメモ化せずに短いコードで解けちゃいます。
注意点はクラスメソッドではなくグローバルでメソッドを定義する必要があることと、テストケースによって関数の結果が違う場合には、引数にテストケースの番号も入れる必要がある点。
使い方は至って簡単。requireして、includeして、メソッド定義してmemoizeに登録するだけ。

実際、フィボナッチ数列と竹内関数でどのくらい違うか比較してみた。
ついでにruby2.0とruby1.9も比較してみた。

フィボナッチ数列

require "memoize"
include Memoize

def fib1(n)
  return 1 if n<2
  fib1(n-1)+fib1(n-2)
end

def fib2(n)
  return 1 if n<2
  fib2(n-1)+fib2(n-2)
end

memoize(:fib2)

require "benchmark"

Benchmark.bm{|x|
  x.report("fib standard case :"){
    puts fib1(35)
  }
  x.report("fib memoize case:"){
    puts fib2(35)
  }
}

#ruby2.0
#       user     system      total        real
#fib standard case :14930352
#  1.690000   0.000000   1.690000 (  1.682795)
#fib memoize case:14930352
#  0.000000   0.000000   0.000000 (  0.000184)

#ruby1.9
#fib standard case :14930352
#  2.400000   0.000000   2.400000 (  2.402543)
#fib memoize case:14930352
#  0.000000   0.000000   0.000000 (  0.000244)

竹内関数

require "memoize"
include Memoize

require "benchmark"

def tarai1(x,y,z)
  x<=y ? y : tarai1(tarai1(x-1,y,z),tarai1(y-1,z,x),tarai1(z-1,x,y))
end

def tarai2(x,y,z)
  x<=y ? y : tarai2(tarai2(x-1,y,z),tarai2(y-1,z,x),tarai2(z-1,x,y))
end

memoize(:tarai2)

Benchmark.bm{|x|
  x.report("Tarai standard case :"){
    puts tarai1(18,15,5)
  }
  x.report("Tarai memoize case:"){
    puts tarai2(18,15,5)
  }
}

#ruby2.0
#       user     system      total        real
#Tarai standard case :18
#  9.280000   0.010000   9.290000 (  9.283853)
#Tarai memoize case:18
#  0.000000   0.000000   0.000000 (  0.001410)

#ruby1.9
#       user     system      total        real
#Tarai standard case :18
# 11.800000   0.010000  11.810000 ( 12.028938)
#Tarai memoize case:18
#  0.000000   0.000000   0.000000 (  0.002076)

memoizeちょっぱや!
バージョンもRuby2.0使ったほうがいい感じ。