fib2.rb

# -*- encoding: utf-8 -*-
require 'benchmark/ips'

def fib_naive(n)
  return 1 if n <= 2
  fib_naive(n - 1) + fib_naive(n - 2)
end

def fib_memo(n)
  fib_memo_recur(n, {})
end

def fib_memo_recur(n, memo)
  return memo[n] if memo.key?(n)
  return memo[n] = 1 if n <= 2
  memo[n] = fib_memo_recur(n - 1, memo) + fib_memo_recur(n - 2, memo)
end

def fib_iter_inner(prev2, prev1, cnt)
  if cnt == 1
    prev2 + prev1
  else
    fib_iter_inner(prev1, prev2 + prev1, cnt - 1)
  end
end

def fib_iter(n)
  return 1 if n <= 2
  fib_iter_inner(1, 1, n - 2)
end


def main
  Benchmark.ips do |x|
    x.config(:time => 5, :warmup => 0)
    x.report('naive') {
      fib_naive(30)
    }
    x.report('memo') {
      fib_memo(30)
    }
    x.report('iter') {
      fib_iter(30)
    }
  end
end

case $PROGRAM_NAME
when __FILE__
  main
when /spec[^\/]*$/
  # {spec of the implementation}
end

# >> Calculating -------------------------------------
# >>                naive         1 i/100ms
# >>                 memo         1 i/100ms
# >>                 iter         1 i/100ms
# >> -------------------------------------------------
# >>                naive        9.9 (±0.0%) i/s -         50 in   5.067318s
# >>                 memo    80426.9 (±5.0%) i/s -     258215 in   4.200047s
# >>                 iter   343313.9 (±7.2%) i/s -     721430 in   2.385844s