From: horndude77@...
Date: 2005-09-07T14:41:28+09:00
Subject: memoize

Is there any good memoize library out there? A quick look for one
didn't bring one up. (I did find some old talk about one, but I
couldn't find the actual module. See
http://www.siaris.net/index.cgi/+Programming/LanguageBits/Ruby/HashProc.rdoc
search for memoize. If you have a good link let me know.) I made a
quick one:

#This is the memoize cache
$memoizeHash = {}

def memoize(name)
	$memoizeHash[name] = {}
	eval <<END
		alias original_fn_#{name} #{name}
		def #{name}(*args)
			$memoizeHash[:#{name}][args.join(',')] ||=
original_fn_#{name}(*args)
		end
END
end

And a quick test:

#Inefficient and simple on purpose
def fib(n)
	return n if(n<2)
	fib(n-1) + fib(n-2)
end

tests = [100, 200, 500, 800]
Benchmark.bm(5) do |b|
	b.report("20") { fib(20) }
	b.report("25") { fib(25) }
	puts "Memoizing"
	memoize(:fib)
	tests.each do |t|
		b.report("#{t}") { fib(t) }
	end
end

It works pretty well in this simple situation. There are a couple of
things that I'd like to do:

- Is there a way to do this without an eval to speed it up?
- Make this work on the class level.
eg.
class Test
	def func(n)
		return n if(n<3)
		func(n-1)+func(n-2)+func(n-3)
	end
	memoize(:func)
end

- In the perl memoize module there was a way to tie the cache to a file
for transparent disk storage. Is there a ruby equivalent already
created? (I guess it wouldn't be too bad to make my own class that
supports [] and []= but writes to a file instead.)
- Make the key creation function dynamic. Right now it's just a join,
but for some inputs this might not be acceptable.

I'd like to mess with these things anyways to help me keep learning
ruby even if the other module works fine. I'm most interested in a way
to do this without the eval right now if possible. Thanks for the help!

-----horndude77