Memoization is essentially a fancy name for caching results for future use. A generalization of dynamic programming, if you will.

While I am certain most of us use it one way or another, in many occasions, it is usually through an Ad hoc implementation.. One that is only suitable for the specific, current, use case. Why don’t we generalize it further, and supply a generic, reusable, solution for Memoization?

A generic implementation approach to Memoization can be a little like that of the standard ptr_fun and mem_fun adaptors: we could wrap the needed free function/member function with a Memoizer object of our own, which will cache the results and only invoke the function within if no proper result is already present.

In this post we will discuss the implementation of Memoizer for free functions taking exactly 1 argument. It is possible to extend the given solution to functions taking well over 1 parameter, as well as to member functions and what not, through overloading and using tuple type as cache key type.

Let us have a first go at implementing our desired Memoizer:

// --- memoization.hpp ---

#include <map>

template <typename Arg, typename Result>
class Memoizer {
        typedef Arg key_type;
        typedef Result val_type;
        typedef Result (*fun_type) (Arg);

        typedef std::map<key_type, val_type> cache_type;
        typedef typename cache_type::iterator iter_type;

        const fun_type fun_;
        mutable cache_type cache_;

    public:    
        Memoizer (fun_type fun) :fun_(fun) {}

        Result operator() (Arg arg) const {
            iter_type it = cache_.find(arg);
            if (it != cache_.end())
                return it->second;
            return cache_[arg] = fun_(arg);
        }
};

template <typename Arg, typename Result>
Memoizer<Arg, Result> memoize (Result (*f) (Arg)) {
    return Memoizer<Arg, Result>(f);
}

Logically enough, we’re using a map as our underlying cache type (although it is certainly conceivable to use a different data structure). The memoize template function it supplied to make the creation of Memoizer objects significantly easier, since the compiler is now able to deduce the Result and Arg types from the given function, saving the user from having to supply them explicitly.

I am sure that the careful readers have already noticed that we may have a little problem on our hands. It has to do with the Arg type; Many functions tend to pass their arguments using a const reference (especially if it’s a custom, heavy, object that is passed), which makes the map key type a reference – which is hardly good for us. To solve this problem we can employ the following meta programming trick to remove reference:

template <typename T>
struct RemoveRef { // general case
    typedef T result;
};

template <typename T>
struct RemoveRef<T&> { // specialization for reference types
    typedef T result;
};

Then, the only thing left to do is change the key_type typdef (line 07) to:

        typedef typename RemoveRef<Arg>::result key_type;

There might be more little issues like this one with the types (consider const qualifier for example), but they can be handled in the same manner.

Below is a test case illustrating just how efficient the Memoization technique can sometimes be:

#include <functional>
#include <algorithm>
#include <vector>

#include "timer.hpp"
#include "memoization.hpp"

// change num type to 'const unsigned &' to verify fix
unsigned fib (unsigned num) {
    unsigned prev = 1, curr = 1;
    for (unsigned n=2;n<num;++n) {
        unsigned tmp = curr;
        curr += prev;
        prev = tmp;
    }
    return curr;
}

int main () {
    std::vector<unsigned> data(100000, 10000);
    std::vector<unsigned> out(data.size());

    {
        Timer t("memoized");
        std::transform(data.begin(), data.end(),
            out.begin(), memoize(fib));
    }

    {
        Timer t("normal");
        std::transform(data.begin(), data.end(), 
            out.begin(), std::ptr_fun(fib));
    }
}

Header timer.hpp containts the Timer class discussed here.

And this is how the output looks like (take note of the runtime differences):

antrikot:~/work/sandbox/memo> g++ -Wall -pedantic main.cc
antrikot:~/work/sandbox/memo> ./a.out
memoized: 0.04secs.
normal: 5.78secs.

Comments greatly encouraged.