This post originated from an RSS feed registered with Ruby Buzz by Michael Neumann. Original Post: Performance Quanten Sprung (Jump) Feed Title: Mike's Weblog Feed URL: http://www.ntecs.de/blog-old/index.rss?cat=ruby&count=7 Feed Description: Blogging about Ruby and other interesting stuff. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Michael Neumann Latest Posts From Mike's Weblog

Here is the "un-optimized" algorithm, the well known Fibonacci function:

  def fib(n)
    if (0..1).include? n
      1
    else
      fib(n-2) + fib(n-1)
    end
  end

Okay, it's fast enough for small numbers, but how long would it take to calculate fib of 10000? Well, it would take so much longer than the life of the whole universe that I can't even describe how much longer it would take (billions of billions of billions of ... times longer).

To make the algorithm above run 10^2086 times faster than before, we add the following two lines:

  # paste here the algorithm from above
  require 'memoize'
  memoize 'fib'

Now let's calculate fib(10_000):

  p fib(10_000)

And after approx. 3 seconds, the result is displayed on the screen:

  5443837311356528133873426099375038013538918455469596702624771584120858
  2865622349017083051547938960541173822675978026317384359584751116241439
  ... 26 lines snipped ...
  0765629245998136251652347093963049734046445106365304163630823669242257
  761468288461791843224793434406079917883360676846711185597501

Wow that's a bit longish number ;-)

For those who are interested about the performance characteristics, it's a change from O(Fib(n)) to O(n).

Implementing Memoize

As I couldn't find Robert Feldt's memoize module for Ruby anymore, I decided to write my own. It took me no more than 10 minutes:

  $MEMOIZE_CACHE = Hash.new

  def memoize(*methods)
    methods.each do |meth|
      mc = $MEMOIZE_CACHE[meth] = Hash.new
      old = method(meth)
      new = proc {|*args|
        if mc.has_key? args
          mc[args]
        else
          mc[args] = old.call(*args)
        end
      }
      self.class.send(:define_method, meth, new)
    end
  end