This post originated from an RSS feed registered with Ruby Buzz
by Eigen Class.
Original Post: Bounded space memoization, another new twist
Feed Title: Eigenclass
Feed URL: http://feeds.feedburner.com/eigenclass
Feed Description: Ruby stuff --- trying to stay away from triviality.
Everybody knows memoization by now; there's the old
Hash trick and a
"memoize" module in RAA.
But as old as it is, you can always add a new twist.
Like making it bounded-space.
You've most probably seen (or coded) "memoize" several times. Most
implementations use a hash to store the results that will grow very quickly if
lots of different argument values are given to the corresponding method.
A bounded-space "memoize", on the other hand, will not.
Classic
For the sake of comparison, here's a plain "memoize". It differs from the one in the RAA in that
it works at the Module level
the memoized method can accept a block
it doesn't use define_method, but rather an old-fashioned module_eval (for speed and block support in Ruby < 1.9)
class Moduledef memoize(method)# alias_method is faster than define_method + old.bind(self).callalias_method"__memoized__#{method}",methodmodule_eval<<-EOF
def #{method}(*a, &b)
# assumes the block won't change the result if the args are the same
(@__memoized_#{method}_cache ||= {})[a] ||= __memoized__#{method}(*a, &b)
end
EOFendend
Bounded-space implementation
The bounded-space memoize is built on top of a BoundedSpaceCache that uses
a clever heuristic to decide which value is to be kept in the cache.
This graph shows the execution time of fib(100) for different cache sizes:
As you can see, significant speed increases can be obtained using caches with
as few as 30 or 40 entries*1:
an unmemoized fib(30) takes over 2 seconds...