Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

I'm coming from Java and this is my first attempt with Ruby reflection.

The idea is to take the common-known (and awfully bad performing) fibonacci(n) recursive method:

# recursively computate fibonacci(n)
def fib(n)
  n <= 2 ? 1 : fib(n-2) + fib(n-1) 
end

And to optimize it with some Ruby reflection:

require 'benchmark'

def fib(n)
    # if n<= 2 fib(n) = 1
    return 1 if n <= 2   
    # if @fib_n is defined it means that another instance of this method 
    # has already computed it, so I just return its value
    return instance_variable_get("@fib_#{n}") if instance_variable_get("@fib_#{n}")  
    # else I have to set fib_n and return its value
    instance_variable_set("@fib_#{n}", ( fib(n-2) + fib(n-1) ) )   
end 

Benchmark.bm(30) do |x|  
    x.report("fibonacci(#{ARGV[0]}) computation time:") {$fib = fib(ARGV[0].to_i)}
end

puts "fib(#{ARGV[0]}) = #{$fib}"

Since the execution time for fib(36) drops from about 4 sec to 0.000234 sec, I guess it's working!

But since I'm a Ruby novice (and since this is my first attempt with reflection) I'd still like to have my code peer-reviewed.

Is my choice to use '@fib_n' instance variables correct or there is a better choice?

Does anyone know a better ruby optimization for the recursive computation of fibonacci members? (I know, the most efficient computation for fibonacci is the iterative one, but here I'm strictly interested in the recursive one :))

UPDATE

This approach with memoization is about 5 times faster:

def fib_array(n)    
    @fib = [0, 1, 1] if !defined? @fib
    @fib[n] ||= fib_array(n-2) + fib_array(n-1)
end

And defining @fib array outside the method makes it even slightly faster:

@fib = [0, 1, 1]
def fib_array(n)    
    @fib[n] ||= fib_array(n-2) + fib_array(n-1)
end

Not bad for a 2 lines method, isn't it? Anyway the fastest approach remains the metaprogramming-based one posted by cat_baxter. What amazes me is that it's even about 60 times faster than the following iterative one (!!!).

def fib_iter(n) 
    curr_num, next_num = 0, 1
    (n).times do
        curr_num, next_num = next_num, curr_num + next_num
    end  
    curr_num
end
share|improve this question
1  
I would suggest using an array instead of instance variables – Victor Moroz May 31 '12 at 18:26
How and why? How about a comprehensive answer? I'm still waiting for one to accept. – Duccio Armenise May 31 '12 at 19:44
I gave your suggestion a try but I used... an instance array. See the update: it is 5 times faster, thank you. – Duccio Armenise Jun 1 '12 at 8:20

3 Answers

up vote 2 down vote

If you're interested, below is the fastest recursive fibonacci calculator in Ruby (1.000.000 in 85 ms).

class Integer
  FC = Hash.new do |hash, key|
    if hash.has_key?(key - 1) and hash.has_key?(key - 2)
      hash[key] = hash[key - 1] + hash[key - 2]
    elsif hash.has_key?(key + 1) and hash.has_key?(key + 2)
      hash[key] = hash[key + 2] - hash[key + 1]
    else
      subkey = key.div(2)
      case key.modulo(4)
        when 1
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) + 2
        when 3
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) - 2
        else
          hash[key] = hash[subkey] * (hash[subkey] + 2*hash[subkey - 1])
      end
    end
  end
  FC[0] = 0
  FC[1] = 1
  def fib
    return FC[self]
  end
end

start_time = Time.now
N = ARGV[0].to_i
f = N.fib
#puts f.to_s()
puts "Time (s): " + (Time.now - start_time).to_s
share|improve this answer
2  
Yeah, thank you! Where does this code come from? I'd also like to read an explanation about why it is so fast if available. – Duccio Armenise May 31 '12 at 16:46
2  
You can read the full story about 1 000 000 000 fibonacci challenge, differend approaches and algorithms here: weblogs.java.net/blog/kabutz/archive/2012/02/24/… and here: javaspecialists.eu/archive/Issue201.html – cat_baxter May 31 '12 at 17:24
1  
Your iterative solution has the complexety O(N), the fastest version has O(log(N)), based on Dijkstra's recurrence: F(2N-1) = F(N-1)^2 + F(N)^2, F(2N) = (2 F(N-1) + F(N)) F(N) See cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF – cat_baxter Jun 1 '12 at 8:35
up vote 1 down vote

One possible solution with lambda:

fibp =
  lambda do
    a = [0, 1]
    lambda do |n|
      if n > 1
        a[n] ||= fibp[n - 2] + fibp[n - 1]
      else
        n
      end
    end
  end \
    .call

p fibp[1000]

Still prone to stack overflow as any recursive method in Ruby.

UPDATE: In fact memoizing is not necessary if all you need is just one result:

fibp =
  lambda do |n|
    if n > 1
      p1, p2 = fibp[n - 1]
      [p2, p1 + p2]
    else
      [0, n]
    end
  end

p fibp[1000].last
share|improve this answer
You're right: using an array is faster than using single variables but I found this lambda solution being less convenient than the others. It is faster than my first one but slower than my second one (partially based on your suggestion), and overflows the stack a lot before the other approaches does. – Duccio Armenise Jun 1 '12 at 8:18
up vote 1 down vote

considering that this is Code Review, I have to say that you probably don't want to use an instance variable. You expose the internal data, and any user could destroy the workings of your method inadvertently. In Ruby 1.9, Ruby added a very interesting feature for just these types of situations that involve infinite sequences. It's called a Fiber.

It's true that Fibers aren't perfect for situations where you have to go backwards in the sequence in addition to forward.

Another option for this is to put the data in a module:

module Fibonacci
  @fib=[0,1,1]
  def self.fib_array(n)    
    @fib[n] ||= fib_array(n-2) + fib_array(n-1)
  end
end

And use it like so:

Fibonacci.fib_array(42)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.