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.

Thanks my friend for your code !!