cplusplus.co.il

Memoization

Posted on: 07/01/2010

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.

Advertisements

10 Responses to "Memoization"

Very nice ! Thanks for the post.

A different approach to Memoization and fib

http://blogs.msdn.com/vcblog/archive/2008/11/18/stupid-lambda-tricks.aspx

🙂

By the way,
Why is cache_ mutable?

Ignore that I didn’t see that operator() is const

And that is done to allow less-restrictive usage.

I like the link to the Visual C++ Team blog, even more so since it deals with Lambda functions (and few other C++0x features). However, I think the implementation here is far more elegant, and can be adapted to work in their scenario as well. We could even make Memoizer inherit from std::unary_function. What do you think?

Thanks for dropping a line.

I think that the minute they named the lambda and made it recursive they lost the point behind lambda. 🙂
IMO lambda should stay small and simple (It becomes unreadable).
Besides, Their way is too intrusive.

In your way you can just apply the functor to any code, and you can apply other functors on top of it.

I see no actual reason to inherit from std::unary_function, maybe only for readability (showing other developers that this is a functor)
Do you see any benefits?

Lately I’m asking and replying too much 😉
It’ll be more STL compatible and you could use bind1st and etc…

That’s exactly what I was going to say. Chips? 🙂

Great post rmn. Maybe you should mention that Boost provides a “remove_reference” class together with other related goodies like “remove_const” or “remove_pointer”

It is true that Boost already contains utilities like the ones you have mentioned, thanks for bringing them up. The relevant boost::remove_reference utility can be found here.
A point worth noting though, is that there is much to be learned from small snippets like the RemoveRef class mentioned here. So it only benefits more readers that way.

Thanks again for the kind words.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: