Benchmarking various implementations of the Fibonacci sequence, with and without memoization.

gistfile1.rb

require 'benchmark'

module Memo
  @@memo = { 0 => 0, 1 => 1 }

  def memoize(method)
    alias_method "old_#{method}".to_sym, method

    define_method(method) do |*args|
      @@memo[args] ||= self.send("old_#{method}".to_sym, *args)
    end
  end
end

module Memo2
  def memoize(method)
    old_method = instance_method(method)
    memo = {}

    define_method(method) do |*args|
      memo[args] ||= old_method.bind(self).call(*args)
    end
  end
end

class Fib1
  @@memo = { 0 => 0, 1 => 1 }

  def self.fib_rec(n)
    @@memo[n] ||= fib_rec(n - 1) + fib_rec(n - 2)
  end
end

class Fib2
  extend Memo

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

  memoize :fib_rec
end

class Fib3
  extend Memo2

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

  memoize :fib_rec
end


repeat = 100000
num = 1000

Benchmark.bm(7) do |x|
  x.report("Fib1:") { repeat.times{ Fib1.fib_rec(num) } }
  x.report("Fib2:") { repeat.times{ Fib2.new.fib_rec(num) } }
  x.report("Fib3:") { repeat.times{ Fib3.new.fib_rec(num) } }
end