What is memoization? The Wikipedia article says that Memoization in computing is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation for previously-processed inputs.
My personal explanation of memoization is a technique that is used to temporarily cache data during the processing of it used to reduce the repeated calls and processing of the same data over and over again.
Let me explain in more detail what memoization is using a Fibonacci example. Just to clarify who and what fibonacci is for anyone who does not know.
In mathematics fibonacci means (according to Google’s define: search): a series of numbers created by adding the last two numbers in the series to product the next number in the series. For example: 1, 1, 2, 3, 5, 8, …
So who was Fibonacci? According to Google once again (since it is one of my best friends), Leonardo Fibonacci was a thirteenth century mathematician from Italy who discovered the significance and unique properties of a simple number series.
So further more, let’s get onto the memoization technique in optimization of computer programming. I will be using C++ to demonstrate this technique and we will only solve fibonacci numbers greater then 1.
We will start off by writing our simple CLI program using C++ to demonstrate the solving fibonacci of n using recursion.
#include <iostream>
int fib(int n)
{
/*
Check the base cases.
Example:
fib of 2: (2 - 1) + (2 - 2) = 1
*/
if( n < 3 )
{
return 1;
}
return fib(n - 1) + fib(n - 2);
}
int main( void )
{
std::cout << fib(46) << std::endl; /* This will output the value 75025 */
return 0;
}
Alright, so the above code example does not use the memoization technique. The result of this will lead to the repeated calls of the fib() function numerous times throughout process to solve a previously solved n value.
Now let's solve for n using memoization. For this example, we will also keep in mind that the n will not be greater then integer value 46 and will not be less then 2. We will use a global integer array for temporary caching to solve for fib(n) using memoization named gFibs. What we do is that at offset n - 1 in gFibs array will contain the fibonacci number for n if previously solved else we will solve it once and set the gFibs[n-1] value to the solved fibonacci number of n. So therefore we solve for n only once throughout the series.
#include <iostream>
static int gFibs[46];
int fib(int n)
{
/*
Check the base cases.
Example:
fib of 2: (2 - 1) + (2 - 2) = 1
*/
if( n < 3 )
{
return 1;
}
if( gFibs[n - 1] < 1 )
{
gFibs[n - 1] = fib(n - 1) + fib(n - 2);
}
return gFibs[n - 1];
}
int main( void )
{
/* Let's set gFibs[0] and gFibs[1] equal to one.
These are base cases and do not require to be solved. */
gFibs[0] = 1;
gFibs[1] = 1;
std::cout << fib(46) << std::endl;
return 0;
}
So now we have a working solution of solving fibonacci for n using memoization. As you can see the increase in performance when solving for 46 compared to solving for 46 when not using a memoization implementation.
When I personally tested both ways to solving fibonacci for n, here are some elapsed times:
- Without memoization: Approx. 7.2833 minutes
- With memoization: Less then 1 second.
Note that I did not use a high performance timer for receiving these elapsed times and since C/C++ do not have a high performance timer (microsecond timing) standard library I did not (but will later on in the future) develop a specific timer. Also remember that their are other OS processing that was done throughout the time both of these calls were made and timed against.
Also please keep in mind that with this example I have used an array for "temporarily" caching the previously solved results. This may not be necessary and or required for other implementations of memoization as other containers or ways of storage could be used.
I hope that I have explained this technique used for optimization. If you have any questions, concerns and or suggestions feel free to comment!
