Rubyでフィボナッチのメモ化

仕事つかれたー、なんかリフレッシュしたーい。 なんて時によくフィボナッチを書いて、それをメモ化してにやにやします。 で、今も仕事の合間にそんなことをしていたのですが、需要少しはあるかなーと記事にしてみた。

普通にフィボナッチ

irb(main):001:0> def fib n
irb(main):002:1>   n <= 1 ? n : fib(n-2) + fib(n-1)
irb(main):003:1> end
=> nil
irb(main):006:0* fib 10
=> 55
irb(main):007:0> require 'benchmark'
=> true
irb(main):011:0> Benchmark.measure { fib 40 }
=> #<Benchmark::Tms:0x007f84932ef3c8 @label="", @real=31.694596, @cstime=0.0, @cutime=0.0, @stime=0.04000000000000001, @utime=31.199999999999996, @total=31.239999999999995>

40とかすると遅いですね。

メモ化

irb(main):014:0* def fib_memo n
irb(main):015:1>   @memo ||= []
irb(main):016:1>   @memo[n] ||= n <= 1 ? n : fib_memo(n-2) + fib_memo(n-1)
irb(main):017:1> end
irb(main):020:0> Benchmark.measure { fib_memo 40 }
=> #<Benchmark::Tms:0x007f8493305858 @label="", @real=3.5e-05, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.0, @total=0.0>

メモ化、サラマンダーよりはや〜(ry 1000でも1瞬で終わります。

さって仕事しよう。