Intorduction to memoization. :: Articles :: Cinjection

JavaScript is not enabled on your browser and in order to properly use Coder Profile JavaScript is required.
To view instructions on how to enable JavaScript on your browser click here.

Cinjection � Articles � Intorduction to memoization.

Intorduction to memoization.
Programming

Memoization(not memorization) is a programming technique often used in dynamic programming. In essence, it just means having your program remember previous calculations and reuse those results in similar calculations later. It's a rather simple technique and yet it can make a huge difference in efficiency.

Let's the common task of calculating Fibonacci numbers. Say that I need to output the first n Fibonacci numbers. Well the simplest approach is to use tree recursion:

CODE:	Copy / Restore :: Remove Scroll Bars
double fibonacci(int n) { if (n < 2) { return n; } else { return fibonacci(n - 2) + fibonacci(n - 1); } }

Now although this solution is the easiest to formulate it is extremely inefficient. The reason why it is so inefficient, is because there is a huge amount of recalculation involved. Take fibonacci(6), which is to take the 6th term of Fibonacci. If we trace the recursive calls, we will see a structure similar to this:
f(6)
f(5) + f(4)
f(4) + f(3) + f(3) + f(2)
f(3) + f(2) + f(2) + f(1) + f(2) + f(1) + f(1) + f(0)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + 1 + f(1) + f(0) + 1 + 1 + 0
f(1) + f(0) + 1 + 1 + 0 + 1 +0 + 1 + 1 + 0 + 1 + 1 + 0
1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1 + 0
8

Therefore the 6th Fibonacci term is 8. But look at the process we took to get there, We calculate f(3) twice and f(2) is calculated five times. This is the reason why this version is so inefficient. But instead of recalculating f(n), why don't we calculate it once and then save the result. Then we can just look up the value when we need it again later.

We could rewrite the entire function and make it iterative, but that would complicate the code more than this simple recursive solution does. Adding memoization to this makes the code execute much faster, and the code is still very easy and clear to understand.

We will use a map (an associative array) to keep track of the results. Take a look at this code:

CODE:	Copy / Restore :: Remove Scroll Bars
#include <map> double fibonacci(int n) { static std::map<int,double> lookupTable; double &term = lookupTable[n]; if (term) { return term; } else if (n < 2) { return n; } else { term = fibonacci(n - 2) + fibonacci(n - 1); return term; } }

First, I make a map called lookupTable (and it's static so that it retains all the calculations in between function calls). I could have easily used a vector, or even an array, but I chose a map. An array would be a poor choice, because the the amount of calculations to remember is not known at runtime. This is why I choose a dynamically allocated data container, like a map.

The first thing I do in the function is return a reference to the term I'm looking for. The reason I return a reference is so that if it's not calculated, I can do so very easily.

If my reference, term, is 0, then that means that this map does know that term yet. If it is not zero, then that means that term contains the value of the Fibonacci term. For example, lookupTable[6] = 8, assuming that we calculated that 8 at least once before. Otherwise, lookupTable[6] = 0. So, if it is none zero, we can return that value right away. If it is zero, we must calculate it for the first time, and only time.

This is where the reference comes in. In the line:
term = fibonacci(n - 2) + fibonacci(n - 1);
We calculate the new term for Fibonacci, and it goes directly into our map for the next time we need to calculate that term.

Now calculating the first n terms of Fibonacci becomes a breeze. If we calculate the terms in order, each term calculation will involve no more than 2 function calls. The simple recursive version would require exponential amount of calls.

For some statistics on time and how everything compares, I did a little study on it, and it can be found at the link below:
http://www.coderprofile.com/source-code/206/contrasting-recursion-iteration...
[/url]
I hope that you guys got an idea of how memoization works and how it can be used to help make efficient and easy to read code. Please let me know what you think :)Please login to rate coding articles.

Click here to register a free account with us.

Comments

Please login to post comments.

Cinjection

Posted 150 Days Ago