Daniel Berger and I have been having an off-list discussion about his memoize.rb library. You can find that library at:
http://raa.ruby-lang.org/project/memoize/
In the course of the discussion, I ended up building a library of my own, to show Daniel what I was talking about. Daniel thought it might be worth moving the discussion of my new library here, to get community feedback.
The primary difference between our two approaches is that Daniel's library is built to memoize individual objects, while mine is intended to link all instance method calls for a class of objects to a single cache.
I wanted this behavior because I felt it would increase cache hits and make memoizing methods that much more worthwhile. Daniel pointed out though that a finer grained control can be important, to avoid exhausting memory with the cache. Luckily, Ruby's syntax makes it trivial to use my library to alter a unique object as well.
Here's an example of using my library to memoize an instance method, the intended usage:
#!/usr/local/bin/ruby -w
# instance_methods.rb
···
#
# Created by James Edward Gray II on 2006-01-23.
# Copyright 2006 Gray Productions. All rights reserved.
require "memoizable"
class Fibonacci
extend Memoizable
def fib( num )
return num if num < 2
fib(num - 1) + fib(num - 2)
end
memoize :fib
end
puts "This method is memoized, and will run very fast..."
start = Time.now
puts "fib(100): #{Fibonacci.new.fib(100)}"
puts "Run time: #{Time.now - start} seconds"
puts
puts "All objects share a cache, so this call, is even faster..."
start = Time.now
puts "fib(100): #{Fibonacci.new.fib(100)}" # simple cache hit
puts "Run time: #{Time.now - start} seconds"
__END__
Also, here is how you would use the library to affect individual objects:
#!/usr/local/bin/ruby -w
# singleton_objects.rb
#
# Created by James Edward Gray II on 2006-01-23.
# Copyright 2006 Gray Productions. All rights reserved.
require "memoizable"
class Fibonacci
def fib( num )
return num if num < 2
fib(num - 1) + fib(num - 2)
end
end
slow = Fibonacci.new
puts "This method is not memoized and thus slow..."
start = Time.now
puts "slow.fib(30): #{slow.fib(30)}"
puts " Run time: #{Time.now - start} seconds"
fast = Fibonacci.new
class << fast # memoize just this object
extend Memoizable
memoize :fib
end
puts
puts "We can fix that for a unique object..."
start = Time.now
puts "fast.fib(30): #{fast.fib(30)}"
puts " Run time: #{Time.now - start} seconds"
puts
puts "But the original is still slow..."
start = Time.now
puts "slow.fib(30): #{slow.fib(30)}"
puts " Run time: #{Time.now - start} seconds"
__END__
My library also works for class/module methods and even top-level methods, though I will spare you those examples.
The other difference between our libraries is that Daniel's supports using a file for persistent caching, while my library supports using a custom cache object. That means that it's a little more work to cache to a file using mine, but you can do other kinds of caching as well. Here's a file cache example:
#!/usr/local/bin/ruby -w
# file_persistance.rb
#
# Created by James Edward Gray II on 2006-01-23.
# Copyright 2006 Gray Productions. All rights reserved.
require "memoizable"
#
# A trivial implementation of a custom cache. This cache uses disk storage,
# instead of a Hash in memory. Access is slower than using an in-memory cache,
# though still much faster than a non-memoized method, but persistant between
# program runs.
#
# *WARNING*: This implementation is not thread-safe!
#
class FileCache
def initialize( path )
@path = path
end
def []( key )
if File.exist? @path
File.foreach(@path) do |entry|
return entry.split(" ").last.to_i if entry =~ /\A#{key}: /
end
end
nil
end
def []=( key, value )
File.open(@path, "a") { |cache| cache.puts "#{key}: #{value}" }
end
end
class Fibonacci
extend Memoizable
def fib( num )
return num if num < 2
fib(num - 1) + fib(num - 2)
end
memoize :fib, FileCache.new("fib_cache.txt")
end
puts "This method is memoized using a file-based cache. See fib_cache.txt..."
start = Time.now
puts "fib(100): #{Fibonacci.new.fib(100)}"
puts "Run time: #{Time.now - start} seconds"
puts
puts "Run again to see the file cache at work."
__END__
You can find an example using weak references and the actual library code in the "Memoization" section of the following article from my blog:
http://blog.grayproductions.net/articles/2006/01/20/caching-and-memoization
The point of posting all this here is to give people a chance to express concerns over my implementation. Daniel was avoiding going down this road because of issues raised by this community. Raise away. 
If there is any interest, and we don't prove the library horribly broken, I would be happy to package it up.
Thanks.
James Edward Gray II
