1

In JavaScript, it is fairly simple to memoize a function like Fibonacci:

// In JavaScript

var fibonacci = (function () {
  var cache = {}; // cache for future calculations

  return function (num) {
    if (num < 0)    throw new Error('Negative numbers not allowed');
    if (num === 0)  return 0;
    if (num === 1)  return 1;

    cache[num] = cache[num] || fibonacci(num - 1) + fibonacci(num - 2);
    return cache[num];
  };
})();

console.log( fibonacci(5) ); // results in 5
console.dir( fibonacci ); // you can inspect the closure scope and see that the cache object saves the values for future use

I'm trying to understand how to do something similar in Ruby and unfortunately, the only thing I can come up with is creating a class and storing the cache as a class variable:

# In Ruby
class Placeholder
  @@cache = {}

  def fibonacci(num)
    raise 'Negative numbers not allowed' if num < 0
    return 0 if num == 0
    return 1 if num == 1

    @@cache[num] ||= fibonacci(num - 1) + fibonacci(num - 2)
  end
end

example = Placeholder.new
puts example.fibonacci(5) # results in 5

What I don't like about this is the fact that I'm creating a class structure when I don't really intend to create instances of Placeholder. Instead, I'm only doing this because I want to save the state in a Ruby class variable. Ideally, if I were able to create a module and have a module variable, then that would at least solve my "problem" of instantiation with the class based solution. What are your best suggestions for doing this in Ruby?

Update based on @meagar's comment:

@meagar, are you suggesting something like this?

class Placeholder
  attr_reader :cache

  def initialize
    @cache = {}
  end

  def fibonacci(num)
    raise 'Negative numbers not allowed' if num  < 0
    return 0 if num == 0
    return 1 if num == 1

    @cache[num] ||= fibonacci(num - 1) + fibonacci(num - 2)
  end
end

FibonacciCalculator = Placeholder.new
puts FibonacciCalculator.fibonacci(5) # results in 5

I already like this better than my initial Ruby solution, although having the Placeholder class still rubs me the wrong way.

Improve this question
8
  • You're essentially asking for C's static when in a function, right? Commented Feb 10, 2015 at 21:10
  • This might be a valid use for a global variable. Commented Feb 10, 2015 at 21:11
  • @Linuxios No, it's really not Commented Feb 10, 2015 at 21:11
  • Sorry @Linuxios I'm not very familiar with C so I'm not sure if static addresses my question Commented Feb 10, 2015 at 21:11
  • 1
    No: pastebin.com/UYGTGQiu; Use real names, not Placeholder; use arrays, not objects; use ||= to memoize when possible; use <do something> if <condition>, never if <condition> then do something; end. Commented Feb 10, 2015 at 21:42

4 Answers 4

Reset to default
4

When you don't need instances, then you can use a Module with a singleton method:

module Fibonacci
  @cache = {}

  def self.series(num)
    if @cache[num] then return @cache[num]; end
    if num  < 0 then raise 'Negative numbers not allowed'; end
    if num == 0 then return 0; end
    if num == 1 then return 1; end

    @cache[num] = series(num - 1) + series(num - 2)
  end
end

puts Fibonacci.series(5) # results in 5

Note that for the cache, an instance variable on the Fibonacci module works just as well as a class variable (and for some extended uses, it could be better). It works because the module Fibonacci is an instance of Module - it is just the same as any other instance variable in that respect.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

. . . not too happy with the method name .series, but cannot think of anything better
Wow this is exactly what I was hoping to be able to do - although I didn't realize that you can create instance variables in a module. Conceptually though, what does instance variable mean here since you're not creating instances of the module?
The module is an instance of the Module class. It's turtles all the way down in Ruby.
Thanks for the explanation @Max - this is a slight aside but what happens to the @cache instance variable when you include the Fibonacci module into a class? Will the instances of the class be able to access @cache?
@wmock: No they will each have their own @cache variables. So if you are looking to do something more generic and sophisticated, you would probably consider having a dedicated caching/memoisation module/class, rather than this ad-hoc cache for a single method.
|
3

A literal translation of your ECMAScript version would be this:

fibonacci = -> {
  cache = {} # cache for future calculations

  -> num {
    raise ArgumentError, 'Negative numbers not allowed' if (num < 0)
    return 0 if num.zero?
    return 1 if num == 1

    cache[num] ||= fibonacci.(num - 1) + fibonacci.(num - 2)
  }
}.()

fibonacci.(5)
# => 5
fibonacci.binding.local_variable_get(:cache)
# => {2=>1, 3=>2, 4=>3, 5=>5}

By the way, there are a couple of simplifications we could do: instead of returning 0 if num is 0 and returning 1 if num is 1, we could just return num if num is either 0 or 1 (or num <= 1). And in fact, we can get rid of that whole condition altogether by simply pre-initializing the cache with the values for 0 and 1. Also, the cache can just be an Array, since the indices are just a contiguous range of Integers:

fibonacci = -> {
  cache = [0, 1] # cache for future calculations

  -> num {
    raise ArgumentError, 'Negative numbers not allowed' if (num < 0)
    cache[num] ||= fibonacci.(num - 1) + fibonacci.(num - 2)
  }
}.()

Interestingly, if we write that in modern ECMAScript, then the relationship becomes obvious:

const fibonacci = (() => {
    const cache = [0, 1, 1]; // cache for future calculations

    return num => {
        if (num < 0) throw new Error('Negative numbers not allowed');
        return cache[num] = cache[num] || fibonacci(num - 1) + fibonacci(num - 2);
    };
})();

console.log(fibonacci(5));

Which in old-school ECMAScript would be this:

var fibonacci = function () {
    var cache = [0, 1, 1]; // cache for future calculations

    return function (num) {
        if (num < 0) throw new Error('Negative numbers not allowed');
        return cache[num] = cache[num] || fibonacci(num - 1) + fibonacci(num - 2);
    };
}();

console.log(fibonacci(5));

Improve this answer

1 Comment

Thanks for showing me the cool stuff with the latest version of JavaScript! @Jörg W Mittag
2

... a class structure when I don't really intend to create instances of Placeholder

Well, there's your problem.

Ruby is an object-oriented language. You cannot have functions that do not belong to objects. Every method is invoked on an object.

You should simply create an instance of Placeholder (and give it an appropriate name like FibonacciCalculator) and make your cache a simple instance variable on that object.

Improve this answer

2 Comments

Thanks for the input @meagar, I've updated my question with an example. Can you confirm if this is what you mean?
"You cannot have functions that do not belong to objects." – Of course you can: -> x {x} is the identity function and doesn't belong to any object, in fact, it is an object itself.
2

You can also store the cache using a closure, which is similar to how javascript would do it.

def memoize func
  cache = {}
  proc do |*args|
    next cache[args] if cache[args]
    cache[args] = func[*args]
  end
end

def slow_double x
  sleep 2
  x * 2
end

memoized_double = memoize(method :slow_double)

memoized_double[4] # takes 2 seconds
memoized_double[4] # returns instantly
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.