Memoizer, in C++

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.