memoize

[horndude77]

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"
memoizefib)
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
memoizefunc)
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

 

[nobu.nokada]

Hi,

At Wed, 7 Sep 2005 14:41:28 +0900,

- Is there a way to do this without an eval to speed it up?
- Make this work on the class level.

module Kernel
def memoize(name)
m = method(name)
cache = {}
(class << self; self; end).class_eval do
define_method(name) do |*args|
cache[args] ||= m.call(*args)
end
end
end
end

 

[Trans]

From Nano Methods (thanks to Robert Feldt)

$MEMOIZE_CACHE = Hash.new

class Module

def memoize(*meths)
meths.each do |meth|
mc = $MEMOIZE_CACHE[meth] = Hash.new
old = instance_method(meth)
new = proc do |*args|
if mc.has_key? args
mc[args]
else
mc[args] = old.bind(self).call(*args)
end
end
senddefine_method, meth, &new)
end
end

end

(I'm doubtful of supporting an instance version.)

T.

 

[Florian Groß]

Is there any good memoize library out there? A quick look for one
didn't bring one up.

I've written one up as a sample for Python decorator like stuff in Ruby.
See the attachment. Used like this: (No disk storage or similar, though.)

class Foo
memoize private def foo(arg)
arg ** arg
end
end

You can probably consider this a hack.

 

[Daniel Berger]

Hi,

At Wed, 7 Sep 2005 14:41:28 +0900,

- Is there a way to do this without an eval to speed it up?
- Make this work on the class level.

module Kernel
def memoize(name)
m = method(name)
cache = {}
(class << self; self; end).class_eval do
define_method(name) do |*args|
cache[args] ||= m.call(*args)
end
end
end
end

I'm not sure I follow:

def fib(n)
return n if n < 2
fib(n-1) + fib(n-2)
end

memoize(fib)

fibonacci.rb:20:in `fib': wrong number of arguments (0 for 1)
(ArgumentError)
from fibonacci.rb:20

Regards,

Dan

 

[Daniel Berger]

Hi,

At Wed, 7 Sep 2005 14:41:28 +0900,

- Is there a way to do this without an eval to speed it up?
- Make this work on the class level.

module Kernel
def memoize(name)
m = method(name)
cache = {}
(class << self; self; end).class_eval do
define_method(name) do |*args|
cache[args] ||= m.call(*args)
end
end
end
end

I'm not sure I follow:

def fib(n)
return n if n < 2
fib(n-1) + fib(n-2)
end

memoize(fib)

Whoops. Should have been memoizefib). Nevermind.

Dan