Part of what I’m trying to do here is record experiments, little bits of code demonstrating software techniques. This is a revisit of a recent one.

As a refresher, memoization is a dynamic programming technique used to optimize the time to solve problems where partial problems overlap frequently. For example, in the recursive definition of the Fibonacci sequence, F(x) = { 1 : x < 2, F(x-1)+F(x-2) : x>=2 }, at each stage, you compute the solution by taking the results from two separate computations.

So, walking briefly through, get the C++ bootstrapping out of the way. To start, we include the standard module’s we’ll be using:

#include <iostream>
#include <iomanip>
#include <map>

Next up, the memoizer — this is a helper class that will record the results for us.

template <
class Result,
class Arg,
class ResultStore = std::map<Arg, Result>
>
class memoizer1{
public:
// accelerate 'f' by remembering partial results
template <class F>
const Result& operator()(F f, const Arg& a){
typename ResultStore::const_iterator it = memo_.find(a);
if(it == memo_.end()) {
it = memo_.insert(make_pair(a, f(a))).first;
}
return it->second;
}
private:
ResultStore memo_;
};

We’ll separate the definition of fibonacci function from the public surface so that the memoizer can be applied later

int fib(int);
namespace {
// instrumentation, track number of uses
int total_ops = 0;
// implementation
int fib_(int n){
++total_ops;
if(n == 0 || n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
}

Lastly the driver function will decorate the implementation with a memoizer, and a prompt loop. You should be able to copy-paste the code into a cpp file, comple, then run.

// driver function
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
using namespace std;
int main(){
cout << "fibonacci numbers, memoized, ctrl+z to quitn";
for(;;) {
cout << "enter integer: ";
int x;
if(!(cin >> x))
break;
total_ops = 0;
int y = fib(x);
cout << "fib(" << x << ") == " << y << endl;
cout << "cost was " << total_ops << endl;
}
}

And that’s the complete program. Trying it with a few inputs, you’ll see few number of operations. To see the non-memoized results, you need only comment out the code for ‘fib()’ and have it invoke ‘fib_’ directly — the results will slow to a halt around x=30 to 35.

By using a look up table, each time ‘fib’ is invoked with a given value of ‘x’, the result is stored so it doesn’t need to recurse again. A hash table, or even a dynamically sizing array (std::vector) could have also been used in this case, but may not be appropriate for other problem spaces.