memoize

Discussion in 'Ruby' started by horndude77@gmail.com, Sep 7, 2005.

  1. Guest

    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
    , Sep 7, 2005
    #1
    1. Advertising

  2. Guest

    Hi,

    At Wed, 7 Sep 2005 14:41:28 +0900,
    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
    , Sep 7, 2005
    #2
    1. Advertising

  3. Trans Guest

    >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.
    Trans, Sep 7, 2005
    #3
  4. 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. ;)
    Florian Groß, Sep 8, 2005
    #4
  5. wrote:
    > Hi,
    >
    > At Wed, 7 Sep 2005 14:41:28 +0900,
    > 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)

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

    Regards,

    Dan
    Daniel Berger, Sep 9, 2005
    #5
  6. Daniel Berger wrote:
    > wrote:
    >
    >> Hi,
    >>
    >> At Wed, 7 Sep 2005 14:41:28 +0900,
    >> 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
    Daniel Berger, Sep 9, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Reedy

    How to memoize functions?

    Chris Reedy, Jun 26, 2003, in forum: Python
    Replies:
    3
    Views:
    997
    Chris Reedy
    Jun 27, 2003
  2. Replies:
    0
    Views:
    657
  3. Replies:
    2
    Views:
    771
  4. Michael Hohn
    Replies:
    3
    Views:
    1,134
    Dima Dorfman
    Oct 31, 2004
  5. Replies:
    11
    Views:
    632
    Gabriel Genellina
    Aug 19, 2006
Loading...

Share This Page