One line Ruby memoization
Memoization is a functional programming technique used to cache the result of expensive method calls for later re-use; this allows us to avoid repeatedly performing an expensive calculation when the result has already been calculated once. Today I stumbled accross an interesting method of achieving memoization in Javascript for nullary functions (i.e. functions taking no arguments); the author was re-defining the method called to perform the calculation to return the computed result, meaning the repeated invocations of the method would return the computed value once the initial calculation had been performed. This seemed like an elegant way to achieve result caching; I was curious to see if the same could be achieved with Ruby.
The standard method of result caching in Ruby might be:
class Cached def cached_method return @cache unless @cache.nil? puts 'computing expensive value' sleep(2) @cache= "hello world" end end c=Cached.new 10.times do puts 'result: ' + c.cached_method end
Using memoization:
class Memoized def memoized_method #expensive computation goes here puts 'computing expensive value' sleep(2) cache="hello world" self.class.send(:define_method, :memoized_method, lambda{cache}).call end end m=Memoized.new 10.times do puts 'result: ' + m.memoized_method end
Here, we are re-defining memoized_method within the function itself so that it returns the computed value once it has been invoked. Disappointingly though, this isn’t much of an improvement line-count wise - the result is slightly less readable too, mainly because define_method is private (which is why we need to use the self.class.send hack above). What about performance (over 50000 iterations)?
nick@unintelligible:~/Desktop$ ruby perf.rb Rehearsal --------------------------------------------- cached: 0.120000 0.020000 0.140000 ( 2.135206) memoised: 0.110000 0.020000 0.130000 ( 2.139923) ------------------------------------ total: 0.270000sec user system total real cached: 0.100000 0.040000 0.140000 ( 0.134768) memoised: 0.130000 0.020000 0.150000 ( 0.144927)
Nope - it’s roughly equivalent (very slightly slower in fact, presumably due to the extra cost of routing the method through define_method). So, although memoization is definitely a useful technique, result caching yields is still more readable and slightly more performant for nullary functions in Ruby than this particular implementation.
It bears mentioning that the standard way of doing memoization in Ruby is using the ||= operator, and that seems to run much faster.
The code:
class Memoized
def memoized_method
@result ||= lambda { puts 'computing expensive value'; sleep 2; 'hello world' }.call
end
end
The timing:
Rehearsal ------------------------------------
0.040000 0.010000 0.050000 ( 2.055683)
--------------------------- total: 0.050000sec
user system total real
0.050000 0.010000 0.060000 ( 0.055465)
Comment by Shadowfiend — August 17, 2007 @ 6:27 pm
Much cleaner indeed. I think what I best liked about that technique was the idea of the method redefining itself, although it’s obviously in need of a better application…
Comment by Nick — August 17, 2007 @ 8:27 pm
@result ||= lambda{…}.call
WTF?!?!?
@result ||= begin; … ;end
is easier to read and a tiny bit faster.
Comment by rmxz — December 19, 2009 @ 6:02 pm
[...] is known to be slow and believed to be leaky (I have no proof of that!). Also check whether you can memoize expensive [...]
Pingback by ruby/ruby on rails memory leak detection | ASK AND ANSWER — December 18, 2015 @ 1:00 am