Dynamic Programming in Ruby

Since the dawn of time (at least since computer science became a field), hiring teams have been asking interviewees about how to concoct code to create a Fibonacci sequence. They wanted to know if an engineer had access to the concepts utilized in Dynamic Programming, and whether or not they could write algorithms that scaled well. They wanted to separate the wheat from the chaff.

The Fibonacci sequence (for all you pieces of chaff out there) is a series of numbers in which each number (i.e. Fibonacci number) is the sum of the two preceding numbers. A tiny sample of this series 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 etc. This sequence is found in geometry all over the place, even in nature!

For the purposes of this blog posts, let’s say you are applying to a company that makes floor plans for houses shaped like pineapples. To make these houses you have to generate a number that helps them determine how many boxes of nails it will take to build a substructure of the building based on its height.

Benchmarking

So how do you know if you are using performant code? You benchmark it. For our purposes we will run the code for our solutions out to the: 10th, 20th, 30th, and 35th position in the Fibonacci sequence.

We will capture the amount of time it takes to process the method using Ruby’s Benchmark library.

  require 'benchmark'
  Benchmark.bm do |bm|
    bm.report { Fib.new(iterations).run }
  end

The Complex Way

The first way we will try to find solutions to this sequence is dirty, complex, and painful. To do it we will use a method that utilizes recursion.

class Fib
  attr_reader :max

  def initialize(max_count)
    @max = max_count
  end

  def run
    i = 0
    while i <= max do
      calculateFibAt(i)
      i += 1
    end
  end

  private

  def calculateFibAt(n)
    if n < 2
      n
    else
      calculateFibAt(n-2) + calculateFibAt(n-1)
    end
  end

end

This code works okay for 10 or less numbers in the sequence. But, if we go higher the Benchmark numbers start to look gnarly. Seems like our code might be getting to complex if we go much higher than 30…

Benchmark
seq.    user      system      total       real
10    0.000000   0.000000   0.000000   (0.000105)
20    0.010000   0.000000   0.010000   (0.006232)
30    0.500000   0.010000   0.510000   (0.505737)
35    5.670000   0.020000   5.690000   (5.738828)

Why is it so complex?

Man it takes a while to calculate out to the 35th position.

It has a complex Big O problem we would like to avoid, O(2^n).

You might be saying to yourself “Eeep, that boggles my tiny little chaff brain”, and “How will I ever get to be as smart as these computer science guys? Can we figure out how many times this method is being called so we can show how big of a problem it is?” Don’t worry we can figure it out, it only took me to about 30 years to find the time to sit down and do it. If I can, you can~!

The higher the number in the Fibonacci sequence, the more the method needs to run. Each step higher in the sequence requires the method to run many more times than the last. Because its recursive running Fibonacci to the 5th number in the sequence, you have to run fib(4), which needs to run fib(3) and fib(2)… and so on. To conceptualize O(n^2), if you increase n by 1, then you roughly added 2 * n units of time to the runtime of the code.

fib(5) =          fib(4)            +     fib(3)
                    |                        |
            fib(3)  +  fib(2)          fib(2) + fib(1)
              |          |               |        |
              |          1               1        1
            fib(2) + fib(1)
              |       |
              1       1

So how much of a problem is O^2n going to causes our application? How do I get the precise number of times calculateFibAt needs to run to get a given number in the Fibonacci sequence? I can add a Fibonacci counter to tabulate the number of times the method gets called!

class Fib
  attr_accessor :fib_count
  attr_reader :max

  def initialize(max_count)
    @fib_count = 0
    @max = max_count
  end

  def run
    i = 0
    while i <= max do
      calculateFibAt(i)
      i += 1
    end

    puts "The total number of times the calculateFibAt method was used was #{fib_count}."
  end

  private

  def calculateFibAt(n)
    self.fib_count += 1
    if n < 2
      n
    else
      calculateFibAt(n-2) + calculateFibAt(n-1)
    end
  end

end

To get to the 3rd place in the Fibonacci sequence it takes 5 iterations of the mehod, to get to 10th 453 iterations of the method, to get to 32 it would be … 18,454,894…. ooh snap this isn’t scaling well…

If this were code in production you would have some explaining to do…

Better

Well lets say someone did push the code above to production… a year ago. You used to only build pineapples up to 50 feet which required 32 steps in the sequence. Now your boss just came to you. He is upset because everything was working fine until some smarty pants, probably named Chad, put 55 feet into the form that uses this code, and it took forever for the page to load the final value in the sequence.

Thanks Chad~!

How might we optimize this code so that its more performant?

We need to sort out this Big O problem and make it O(n). We want to be able to access a value from an array using its index is always O(1). You remember that blog post you read on using Dynamic Programming. This is possible if we can break the problem down into subproblems and then store there answer in an optimized substructure.

To do this we will want to store the value we calculate… We need to remember the solution to a subproblem (Fibonacci(1), Fibonacci(2), Fibonacci(3), Fibonacci(4), Fibonacci(5), etc.) so we don’t have to calculate it again and again recursively.

class FibFaster
  attr_reader :max

  def initialize(max_count)
    @max = max_count
  end

  def run
    fastercalculateFibAt(max)
  end

  def fastercalculateFibAt(n)
    sequence = [0, 1]
    position = 2

    while position <= n do
      sequence.push(sequence[position -2] + sequence[position -1] )
      position += 1
    end

    return sequence
  end

end

Woah, sweet memory store in FibFaster#fastercalculateFibAt. Now we don’t have to recursively calculate each number in the sequence, we can store it here once and move on!

Benchmark
seq.    user      system      total      real
10    0.000000   0.000000   0.000000  (0.000022)
20    0.000000   0.000000   0.000000  (0.000014)
30    0.000000   0.000000   0.000000  (0.000034)
35    0.000000   0.000000   0.000000  (0.000030)

Look at how much quicker those Benchmark numbers are! Especially as we get further up the sequence…

You might be thinking “hey wait a minute you have a loop variable in there too!” and yes, that’s true, but with Big-O you’re more concerned about the nature of algorithm. In this case it’s simply O(n) because of the addition of the storage variables.

Your boss is happy that you sorted this out, but he’s always looking for way to save money by minimizing the amount of the AWS resources your company uses.

You might also be thinking, why do we store all the number in the sequence, we only want to show the user the last number in the sequence?! Maybe we can optimize this some more…

The Greedy way

class FibGreedy
  attr_reader :max

  def initialize(max_count)
    @max = max_count
  end

  def run
    greedycalculateFibAt(max)
  end

  def greedycalculateFibAt(n)
    position_1 = 0
    position_2 = 1
    current = 0
    sequence = 2

    while sequence <= n
      position_1 = position_2
      position_2 = current
      current = position_1 + position_2
      sequence += 1
    end

    return current
  end


end

Woah its even faster now, than the last code. However, it doesn’t look like there is much of a difference in real time between the upper and lower end of the sequence. It still looks like you could save real computation resources by greedily grabbing the number you are you looking for, especially for the numbers higher up the sequence.

Benchmark
seq.    user      system      total       real
10    0.000000   0.000000   0.000000   (0.000012)
20    0.000000   0.000000   0.000000   (0.000013)
30    0.000000   0.000000   0.000000   (0.000012)
35    0.000000   0.000000   0.000000   (0.000013)

Wrapping Up

Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once. Now we can turn our attention to other problems, like shaving yaks.

Good job, we have separated the wheat from the chaff now. How does it feel be a golden kernel of wheat? Now you can grow into the solid software engineer you’ve always wanted to be.

Thanks Chad~!

The book ‘The Imposter’s Handbook’ by Rob Conery has also been a great help in understanding computer science fundamentals including unpacking concepts like “Big O” and “Dynamic Programming”.

Here is a great article that focuses on learning Dynamic Programming not by looking at the outcomes, or explaining the algorithm, but rather by using practical steps to find the algorithm. You can read it here: Demystifying Dynamic Programming: How to construct & code dynamic programming algorithms.