Ruby memoization made easy

memoize.rb

# Memoization made easy. Use it the following way
#
# Memoize all calls
# memoize def my_function(n)
#   ...
# end
#
# Memoize only a ratio of calls (5% here):
# memoize 0.05 def my_function(n)
#   ...
# end
#
#
# Playing on the ratio lets us choose a memory vs. 
# speed tradeoff, for instance:

# require 'benchmark'

# memoize def memoized_fibo_100(n)
#   return n if n <= 1
#   memoized_fibo_100(n-1) + memoized_fibo_100(n-2)
# end
# memoize 0.1, def memoized_fibo_10(n)
#   return n if n <= 1
#   memoized_fibo_10(n-1) + memoized_fibo_10(n-2)
# end
# memoize 0.01, def memoized_fibo_1(n)
#   return n if n <= 1
#   memoized_fibo_1(n-1) + memoized_fibo_1(n-2)
# end

# n = 4 * 10**3

# Benchmark.bm(15) do |x|
#   x.report('100% memoization') { memoized_fibo_100(n) }
#   x.report(' 10% memoization') { memoized_fibo_10(n) }
#   x.report('  1% memoization') { memoized_fibo_1(n) }
# end

# Produces the following benchmark
#                       user     system      total        real
# 100% memoization  0.020000   0.000000   0.020000 (  0.023679)
#  10% memoization  0.130000   0.000000   0.130000 (  0.122192)
#   1% memoization  0.980000   0.010000   0.990000 (  0.987860)

$memoized = {}

def memoize(ratio = 1, func)
  $memoized[func] = {}
  aliased = :"__memoized_#{func}"
  eval("alias #{aliased} #{func}")

  define_method func do |*args|
    if $memoized[func].key?(args)
      return $memoized[func][args]
    else
      result = __send__(aliased, *args)
      $memoized[func][args] = result if Random.rand < ratio
      return result
    end
  end
end