Daniel B. 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 G. 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 G. 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 G. 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
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:
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 G. II
)