Memoization in C++

The class of Dynamic Programming problems are very interesting. These problems all boil down to a class of optimization problems. Such problems are characterized by the distinctive reduction in their design. This reduction can lead to smaller sub-problems that are solved and the results bubbled up. In essence, dynamic programming problems are solved bottom-up, since the results of the sub-problems drive those above them.

The problem with such a technique lies in the fact that every solution requires you to solve every sub-problem to obtain an optimal solution. Memoization provides a simple and largely effective solution to alleviate this problem by storing results to these overlapping sub-problems for future use. Let’s look at an example using the evergreen fibonacci series:

Inside the guts of Memoization

The naive solution to recursive fibonacci series is :

int fib (int n)
{
    if( n <=1 )    return 1;
    else           return fib ( n-1 ) + fib ( n-2 );
}

Let’s look at what happens when we run it for a couple of values :

fib (5) ; // = fib(4)  + fib(3)
          // = (fib(3) + fib(2)) + (fib(2) + fib(1))
          // = ( (fib(2) + fib(1)) + (fib(1) + fib(0)) ) + 
          //               ( (fib(1) + fib(0)) + fib(1))
          // = ( ( (fib(1) + fib(0)) + fib(1)) + 
          //               (fib(1) + fib(0)) ) + ( (fib(1) + fib(0)) + fib(1))
          // 7 '+' operators.

fib (6) ; // 6 overlapping subproblems, 
          // results in '+' operator being run 11 times, 
          // extrapolating from above.

But we already calculated fib (5), didn’t we? And since

fib (6) = fib (5) + fib(4);
and
fib (5) = fib(4) + fib(3);

We’ve already calculated fib (4) too. So fib (6) needs to just add the 2 values, resulting in just a single ‘+’ operation.

To use this information in our solution, let’s use a global map that stores intermediate solutions. (we can use hash_maps for faster un-ordered  access when the TR1 specification and C++0x is standardized)

std::map<int, int> fibHash;

int memoized_fib (int n)
{
    std::map<int, int>::iterator fibIter = fibHash.find(n);
    if( fibIter != fibHash.end() ) return *fibIter;

    int fib_val;
    if( n <=1 )    fib_val = 1;
    else           fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 );
  
    fibHash[ n ] = fib_val;
    return fib_val;
}

This is a fairly one off solution, and requires modifications for using with multiple functions… but with C++0x we can do fully automatic memoization as described here : http://cpptruths.blogspot.in/2012/01/general-purpose-automatic-memoization.html

Coming up : my feeble attempt at auto-memoization in the current version of C++.