Memoize

ruby-talk
1

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

2

Hi,

At Wed, 7 Sep 2005 14:41:28 +0900,
horndude77@gmail.com wrote in [ruby-talk:155156]:

- 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

···

--
Nobu Nakada

3

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
      send(:define_method, meth, &new)
    end
  end

end

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

T.

4

horndude77@gmail.com wrote:

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

5

Florian Groß wrote:

See the attachment.

Hah, here it is then.

decorators.rb (1.79 KB)

6

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

···

nobu.nokada@softhome.net wrote:

Hi,

At Wed, 7 Sep 2005 14:41:28 +0900,
horndude77@gmail.com wrote in [ruby-talk:155156]:

- 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

7

Daniel Berger wrote:

···

nobu.nokada@softhome.net wrote:

Hi,

At Wed, 7 Sep 2005 14:41:28 +0900,
horndude77@gmail.com wrote in [ruby-talk:155156]:

- 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 memoize(:fib). Nevermind.

Dan