Unintelligible

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'
    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.

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

3 Comments »

  1. 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

  2. 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

  3. @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

RSS feed for comments on this post. TrackBack URI

Leave a comment