Dynamic Programming and Specs

I was just reading up on the second part of algorithms course (fantastic by the way!) and jumped ahead to dynamic programming late one night. I thought about how dynamic programming could work with specs.

I ran a quick experiment and found that specs and dynamic programming are great together!

Dynamic Programming

Dynamic programming is:

A method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions - ideally, using a memory-based data structure.

– Source: Wikipedia

To me, this sounds like a higher level caching. Where the programmer’s insight can create huge efficiencies from understanding the algorithm and cache key results of the algorithm. (Doesn’t sound very dynamic to me, but I digress, well, wait, /u/shevegen clarifies Dynamic Progrmaming to me in this article

The main prerequisites for dynamic programming is an algorithm that solves the same sub(sub)problem over and over. To demonstrate, I will calculate a Fibonacci sequence.

How to go about it? How to incorporate specs with dynamic programming?

Let’s get the specs and code working first, then think about how to incorporate dynamic programming into the code and specs. I always follow this mantra when programming:

Slow accurate code trumps fast failing code.

Get slow code first!

• Get list of Fibonacci numbers from online encyclopedia integer sequences
  • The goal is to have another reference for checking output, not to implement a slow algorithm twice
• Having slow specs is painful!

Algorithm overview

n-th Fibonacci number is basically:

(n-1)-th Fibonacci number + (n-2)-th Fibonacci number

Where:

• the zeroth Fibonacci number is 0
• the first Fibonacci number is 1
• the second Fibonacci number is 1

Specs

The basic specs to get started will be:

1
2
3
4
5
6
7
8
9
let(:fib) { Fibonacci.new }

expect(fib.at(0)).to eq(0)
expect(fib.at(1)).to eq(1)
expect(fib.at(2)).to eq(1)
expect(fib.at(3)).to eq(2)
expect(fib.at(4)).to eq(3)
expect(fib.at(10)).to eq(55)
expect(fib.at(38)).to eq(39088169)

Code

The code to make those specs pass:

1
2
3
4
5
6
7
8
9
class Fibonacci
  def num(at)
    return 0 if at == 0
    return 1 if at == 1
    return 1 if at == 2

    num(at-1) + num(at-2)
  end
end

This implementation is so slow, the time to just calculate fib.at(38) is eight seconds (on a micro EC2 instance), which is horrendous for a single spec, but the code is very easy to understand, because it is basically implementing the definition of a

Using specs to measure dynamic programming improvement

Let’s introduce dynamic programming as a way to improve the algorithm’s performance.

1
2
expect(fib.num(38)).to eq(39088169)
expect(fib.num(38)).to eq(39088169)

Huh? This has been tested in implementation, so this will always be true, why test again?

Well, dynamic programming only works after the algorithm has been ‘warmed up’, so the first call is to warm it up, the second is for the speed up.

How will the spec know there’s a speed up?

Let’s add in a way to test that dynamic programming is working: a timer method!

1
2
3
4
5
6
def time_this
  start_time = Time.now
  yield
  end_time = Time.now
  end_time - start_time
end

This function will measure anything given to it as a block (thanks to the yield). So, to measure speed up, the spec will become:

1
2
3
4
cold_time = time_this { raise unless fib.num(last) == 39088169 }
hot_time = time_this { raise unless fib.num(last) == 39088169 }

expect(cold_time / hot_time).to be > 10**5

Note that it is expected dynamic programming will speed up the algorithm by at least a factor of ten.

Now all the code used to time the algorithm is within the spec, not the code, so the code can be kept clean.

Incorporating dynamic programming into code

To make the new specs pass:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Fibonacci
  def initialize
    @cache = {}
  end

  def num(at)
    return @cache[at] if @cache[at]

    return 0 if at == 0
    return 1 if at == 1
    return 1 if at == 2

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

Let’s walk-through the new parts added:

• Cache is created by: @cache = {} in the initialize method. A hash is used here for fast access.
• The cache is set with: @cache[at] = num(at-1) + num(at-2)
• The dynamic programming magic happens at: return @cache[at] if @cache[at]

Basically, if there is a @cache entry for the current Fibonacci number, use that. Otherwise, compute the number like before. As this algorithm is recursive, the improvements with dynamic programming is quite impressive.

Dynamic programming speed up

Time to calculate the 38th Fibonacci number:

| | first run (seconds) | second run (seconds) | |:— |:—:|:—:| | without dynamic programming | 5.694623465 | 5.731470989 | | with dynamic programming | 5.77616068 | 6.868e-06 |

• timed on micro.t2 EC2 instance. Results will vary!

The second run without dynamic programming does not see significant improvements over the first run and in some cases, even slower!

The first run with dynamic programming version is on par with the first run without dynamic programming. The second run with dynamic programming is over 10x faster, in this case a million times faster. (Thanks /u/odaba!)

In either case, dynamic programming adds a huge boost to a naive algorithm. Remember, this is just the 38th Fibonacci number. Imagine how long it would take for the 100th… or 1000th Fibonacci number without dynamic programming?

Overall

The great thing about dynamic programming, is that a naive algorithm can get a huge speed boost without significant changes to the algorithm. The algorithm is still easy to understand and it’s significantly faster. A win-win in my book.

Incorporating specs with dynamic programming was quite easy and a great way to ensure speed improvements and accuracy. Code stayed clean and specs did the timing.

Code

Code used for this article is here:

https://github.com/a-leung/dynamic_programming_and_specs

Update Sep 10,2016 - Updated article thanks to insightful reddit comments.