rubyでdfsでメモ化再帰

 いや、早くなるのは分かってたけどめちゃくちゃ早かった*1のでw−

P.S.
チーター本の7章「動的計画法、メモ化」のサンプルのrubyでのベンチ結果です。

dfs

$ ruby -v
ruby 2.1.5p273 (2014-11-13) [arm-linux-gnueabihf]

$ time ruby hello_dfs.rb
119759850

real    13m50.176s
user    13m50.080s
sys     0m0.050s
hello_dfs.rb
$h = 13
$w = 17

def dfs(nowh, noww)
  return 0 if nowh >  $h || noww > $w
  return 1 if nowh == $h && noww == $w

  dfs(nowh+1, noww) + dfs(nowh, noww+1)
end

puts dfs(0, 0)

dfs with memo

$ time ruby hello_dfs2memo.rb
119759850

real    0m0.325s
user    0m0.320s
sys     0m0.010s
hello_dfs2memo.rb
$h = 13
$w = 17

$memo = Array.new($h+1){Array.new($w+1, 0)}

def dfs(nowh, noww)
  return 0 if nowh >  $h || noww > $w
  return 1 if nowh == $h && noww == $w
  return $memo[nowh][noww] unless $memo[nowh][noww].zero?

  $memo[nowh][noww] = dfs(nowh+1, noww) + dfs(nowh, noww+1)
  $memo[nowh][noww]
end

puts dfs(0, 0)

with c++

 参考に、c++での再帰とメモ化再帰の実行時間。さすがに早いですね。

$ gcc --version
gcc (Raspbian 4.9.2-10) 4.9.2
...

$ time ./dfscpp
119759850

real    0m9.905s
user    0m9.870s
sys     0m0.020s

$ time ./dfscpp2memo
119759850

real    0m0.010s
user    0m0.000s
sys     0m0.000s

P.S. 2017/3/10

ちなみに、計測はrasbian on rpi2で*2図ってますw−

with mruby

 なんか、知らないけど興味持たれたようなので、mrubyの場合も*3
わーい、YARVよりメモ化再帰が、はやーい。すごーい。

$ ~/git/mruby/bin/mruby -v
mruby 1.2.0 (2015-11-17)

$ time ~/git/mruby/bin/mruby hello_dfs.rb
119759850

real    48m11.377s
user    48m11.260s
sys     0m0.010s

$time ~/git/mruby/bin/mruby hello_dfs2memo.rb
119759850

real    0m0.064s
user    0m0.050s
sys     0m0.010s

*1:アルゴリズムって大切ですね^^

*2:まあお仕事がARM Linuxなのでそれでの速度感覚の練習がてらです^^;

*3:今日のHeadの取れたてぴちぴちです><