Thursday, August 16, 2007

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'
    @cache= "hello world"
10.times do
  puts 'result: ' + c.cached_method

Using memoization:

class Memoized
  def memoized_method
      #expensive computation goes here
      puts 'computing expensive value'
      cache="hello world"
      self.class.send(:define_method, :memoized_method, lambda{cache}).call
10.times do
  puts 'result: ' + m.memoized_method

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.

posted by Nick at 1:09 pm - filed in ruby