フィボナッチ数列

gdgd

感想

特に面白いことはなかった　

一番素朴な実装が最速な件について

#fib(1000)を計算したとき
           user     system      total        real
fib1   0.010000   0.000000   0.010000 (  0.010997)
fib2   0.010000   0.000000   0.010000 (  0.001816)
fib4   0.010000   0.000000   0.010000 (  0.010691)

コード

def fib1(n,r=[0,1])
  r[n] ||= fib1(n-2,r) + fib1(n-1,r) 
end
def fib2(n)
  a,b=0,1
  n.times{ a,b=b,a+b}
  a
end
def fib3 n
  case n
    when 0 : 0
    when 1 : 1
    else
    fib3(n-2)+fib3(n-1)
  end
end
class Fib
  def initialize
    @r=[0,1]
  end
  def fib4 n
    @r[n]||=fib4(n-2)+fib4(n-1)
  end
end

require 'benchmark'
Benchmark.bmbm do |x|
  n=1000
  x.report("fib1"){fib1 n}
  x.report("fib2"){fib2 n}
  x.report("fib4"){Fib.new.fib4 n}
end

fib1,fib3,fib4はほとんど同じなんだけど・・

それぞれの違い

  • fib3 何回も何回も無駄に計算
  • fib1 ひとつの計算中では１回だけしかr[n]にあたる式を計算しない。
  • fib4 インスタンスが存在する限りは、何度計算してもr[n]を１回だけしか計算しない。

だから、n.times { |i| fib i}のときなどはfib4が早い

でも・・・

include Math
def fib5 n 
  ((((1+sqrt(5))/2)**n) - (((1-sqrt(5))/2)**n))/sqrt(5)
end
      user     system      total        real
fib5  0.000000   0.010000   0.010000 (  0.013327)

どう考えても最速はこれです。本当に(ry*1

*1:1000.times { |i| fib i}などだとfib4の方が早くなる。でもメモリ消費量も莫大。