rubyとschemeでmemo(fib)
sicpでやったfibonachi数の計算のmemo化をrubyでもしてみる
rubyのコード
class Memoize def initialize @a = [] end def memo_fib n @a[n] = @a[n] || fib(n) end def fib n case n when 0 0 when 1 1 else fib(n-2) + fib(n-1) end end end #benchmark用 m = Memoize.new require 'benchmark' Benchmark.bmbm do |x| n = 24 x.report("fib"){ n.times{ |i| m.fib(i)}} x.report("memo_fib"){ n.times{ |i| m.memo_fib(i)}} end
どうせなので速度も計ってみる
schemeのbenchmark用
(define (check f) (print f) (let ((f (lambda ()(time (f 24))))) (f) (f)))
計測結果
ruby(1.8)
Rehearsal -------------------------------------------- fib 0.460000 0.020000 0.480000 ( 0.478503) memo_fib 0.460000 0.010000 0.470000 ( 0.475565) ----------------------------------- total: 0.950000sec user system total real fib 0.440000 0.040000 0.480000 ( 0.476286) memo_fib 0.000000 0.000000 0.000000 ( 0.000082)
ruby(1.9)
Rehearsal -------------------------------------------- fib 0.070000 0.000000 0.070000 ( 0.071487) memo_fib 0.060000 0.000000 0.060000 ( 0.061775) ----------------------------------- total: 0.130000sec user system total real fib 0.070000 0.000000 0.070000 ( 0.061867) memo_fib 0.000000 0.000000 0.000000 ( 0.000032)
gauche(0.8.13)(対話的に実行)
3:user> ;(time (f 24)) ; real 0.049 ; user 0.050 ; sys 0.000 ;(time (f 24)) ; real 0.035 ; user 0.030 ; sys 0.000 #<closure fib> => 46368 4:user> ;(time (f 24)) ; real 0.000 ; user 0.000 ; sys 0.000 ;(time (f 24)) ; real 0.000 ; user 0.000 ; sys 0.000 #<closure (memoize memoize)>
gauche(0.8.13)(ファイルを直接実行)
#<closure fib> ;(time (f 24)) ; real 0.025 ; user 0.030 ; sys 0.000 ;(time (f 24)) ; real 0.025 ; user 0.020 ; sys 0.000 #<closure (memoize memoize)> ;(time (f 24)) ; real 0.000 ; user 0.000 ; sys 0.000 ;(time (f 24)) ; real 0.000 ; user 0.000 ; sys 0.000