Today I browsed a DDJ article called C++ Hash Table Memoization: Simplifying Dynamic Programming, and I was immediately struck by a feeling of “why the hell didn’t I think of this!” If you’re not familiar with Dynamic Programming, here’s a very very brief summary:

When solving a problem you often encounter overlapping subproblems which – if you implement the solution algorithm naively – causes a sub-solution to be calculated many times. The most famous example of this is the Fibonacci sequence: 1, 1, 2, 3, 5, 8 and so on. Here’s an example pseudo code snippet stolen from Wikipedia which calculates a Fibonacci number naively:

function fib(n)
if n = 0 or n = 1
return 1
else
return fib(n + 1) + fib(n + 2)

From the code you’ll note that when trying to calculate, say, fib(5), you’ll calculate fib(3) more than once. Dynamic Programming is basically saying “hey, let’s stop being stupid! If we make sure that the result of fib(3) is only calculated once we’ll save a lot of time!” Quite so. Dynamic Programming may have the most idiotic name ever, but the idea is elegant and very efficient for certain problems.

The Wikipedia article then goes on to mention two DP approaches: top-down, and bottom-up. I’m getting all hot and bothered from mentioning both DP and bottom in the same sentence, but I’ll try to control myself. Bottom-up DP is essentially a way of restructuring the algorithm from a recursive solution to an iterative one, while top-down retains the recursive structure but uses an array for storing the calculated values. As the DDJ article mentions, arrays are most commonly used for storing values…and that’s where the real beaty of the DDJ article’s suggested improvement kicks in.

An array may be inefficient for some problems, so use a hash table instead!

In that short sentence I think I’ve summarized the whole DDJ article; the actual implementation of the proposal is irrelevant, and nothing else is particularly new or exciting. If not for this short addition to what’s already presented on Wikipedia I would’ve claimed that the article was dull and pointless – but now it turned from cow dung into gold! It’s amazing how a small idea can have such an effect. And of course, the fact that it’s such a small idea is what causes the I-Coulda-Thought-of-That reaction that’s oh-so-common.

To end on a high note, here’s a little fib for you:

Left
Right
Top-down
Bottom-up
I don’t give a damn
Just don’t waste any precious RAM

This entry was posted on Thursday, November 1st, 2007 at 3:07 pm and is filed under Software Development. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.