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

gaucheって

直接実行した時と、emacsから対話的に実行した時とで速度が違うみたい。知らなかった。