CODEWITHSUNDEEP
rubymemoization
Eratosthenes
Eratosthenes

Reputation: 2360

How to generically memoize any function in Ruby?

I am trying to write a function to generically memoize any function in Ruby (as described in page 6 of this paper, which does the same thing in Python: http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf), but I am getting stuck. Here is my code, which doesn't work (the function is evaluated correctly, but not memoized). Can anyone tell me where I'm going wrong? 

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

def memoize(&f)
  memo = {}
  doit = ->(arg) do
    return memo[arg] if memo[arg] 
    memo[arg] = f.call(arg)
    memo[arg]
  end
  doit
end

fib = memoize{|x| fib(x)}
puts fib.call(50)

Upvotes: 2

Views: 575

Answers (4)

Anderson Saunders
Anderson Saunders

Reputation: 340

This can be useful if you landed here looking for a solution for lambdas:

fib = ->(memo, n) {
  return n if n < 2
  
  memo[n] ||= fib[n-1] + fib[n-2]
}.curry[Hash.new]

fib.(6)

a "debugging" version in case u want to visualize what is happening.

fib = ->(memo, n) {
  return n if n < 2
  
  memo[n] ||= begin
    puts 'calculating'
    fib[n-1] + fib[n-2]
  end
}.curry[Hash.new]

ps: requires ruby 2.5 or above https://apidock.com/ruby/Proc/curry

Upvotes: 1

Uri Agassi
Uri Agassi

Reputation: 37409

You could use a method decorator pattern, here is a sample implementation you can use as a library:

require "method_decorators/memoize"

class MyMath
  extend MethodDecorators

  +MethodDecorators::Memoize
  def self.fib(n)
    if n <= 1
      1
    else
      fib(n - 1) * fib(n - 2)
    end
  end
end

puts MyMath.fib(200)

Upvotes: 1

Sergio Tulentsev
Sergio Tulentsev

Reputation: 230346

fib calls itself recursively and, by doing this, bypasses your memoization logic completely. Whatever approach you choose, you must overwrite the original definition of fib, to wrap memoization around it.

@Aetherus gave a working answer. Here is a more dynamic solution:

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

def memoize(method_name)
  memo = {}
  old_fib = method(method_name)
  define_method(method_name) do |arg|
    return memo[arg] if memo[arg] 
    memo[arg] = old_fib.call(arg)
    memo[arg]
  end
end

memoize(:fib)

puts fib(50)

Upvotes: 6

Aetherus
Aetherus

Reputation: 8898

In python, functions are callable objects, and their names are just the names of the variables which store those objects, so you can just assign a new value to that variable to make the function functions totally different.

But in ruby, methods are not objects, their names are not variable names either. To override the original, you have to def it again.

Here is my solution:

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

alias _fib fib

def fib(n)
  $memo ||= {}
  $memo[n] ||= _fib(n)
end

fib(50)  #=> 12586269025

I used the old ruby trick: make an alias and override the original. It's nasty (because there is an extra _fib after the overriding), but it's the easiest way doing this.

Upvotes: 0

Related Questions