fib by ruby

fib by ruby

#!/usr/local/bin/ruby
# -*- encoding:utf-8 -*-
require 'benchmark'
require "memoize"
include Memoize

def fib_time n
  a, b = 0, 1
  n.times do
    a, b = a, a+b
  end
  a
end

def fib_inj n
  (1..n).inject([0,1]) do |mem, i|
    mem << mem[i-1] + mem[i]
  end[-2]
end

def fib_inj2 n
  (1..n).inject([0,1]) do |mem, i|
    mem = mem[1], mem[0] + mem[1]
  end[0]
end

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

def fib_memo n
  return n if n < 2
  @series ||= []
  @series[n] ||= fib_memo(n-2) + fib_memo(n-1)
end

def fib_memoize n
  return n if n < 2
  fib_memoize(n-1) + fib_memoize(n-2)
end
memoize :fib_memoize

series = []
fib_proc = lambda do |n|
  return n if n < 2
  series[n] ||= fib_proc[n-1] + fib_proc[n-2]
end

def fib_proc_def(n)
  series = []
  _fib = lambda do |n|
    return n if n < 2
    series[n] ||= _fib[n-1] + _fib[n-2]
  end
  _fib[n]
end

N = 2500

Benchmark.bmbm do |x|
  x.report "fib with time" do
    fib_time N
  end
 
  x.report "fib with inject" do
    fib_inj N
  end
 
  x.report "fib with inject2" do
    fib_inj2 N
  end
  # x.report "fib with recur" do
  #   fib_recur N
  # end
 
  x.report "fib_memo" do
    fib_memo N
  end
 
  # x.report "fib_memoize" do
  #   fib_memoize N
  # end
 

  x.report "fib_proc_def" do
    fib_proc_def N
  end
 
  # x.report "fib_proc" do
  #   fib_proc[N]
  # end
end

# series = []
# def fib_proc n
#   return n if [0,1].include? n
#   res = lambda { series[n] ||= fib_proc(n-1) + fib_proc(n-2) }
#   res.call
# end
# p fib_proc(20)