rubyでdfsでメモ化再帰
いや、早くなるのは分かってたけどめちゃくちゃ早かった*1のでw−
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)
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