Skip to content

Instantly share code, notes, and snippets.

@tdeo
Last active July 6, 2018 09:24
Show Gist options
  • Save tdeo/828787648320fa06fd657395d0ed4343 to your computer and use it in GitHub Desktop.
Save tdeo/828787648320fa06fd657395d0ed4343 to your computer and use it in GitHub Desktop.
Ruby memoization made easy
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment