The Artima Developer Community
Sponsored Link

Ruby Buzz Forum
Bounded space memoization, another new twist

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
Eigen Class

Posts: 358
Nickname: eigenclass
Registered: Oct, 2005

Eigenclass is a hardcore Ruby blog.
Bounded space memoization, another new twist Posted: Feb 19, 2007 2:42 AM
Reply to this message Reply

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.
Latest Ruby Buzz Posts
Latest Ruby Buzz Posts by Eigen Class
Latest Posts From Eigenclass

Advertisement

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 Module
  def memoize(method)
    # alias_method is faster than define_method + old.bind(self).call
    alias_method "__memoized__#{method}", method
    module_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
    EOF
  end
end

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: memoization.png

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

Here's the code:


Read more...

Read: Bounded space memoization, another new twist

Topic: IntelliJ IDEA for Ruby Programming: First Look Previous Topic   Next Topic Topic: Ruby Day 3 in Krak��w

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use