Recently I’ve read an article Efficient Memoization using Partial Function Application. Author explains function memoization using partial application. When I was reading the article, I thought “Hmmm, can I come up with a more general solution?” And as suggested in comments, one can use variadic templates to achieve it. So here is my version.
First let’s do it in a more object-oriented way: we define a template class
Memoizator with 2 parameters: a return value type and a list of argument’s types. Also we incapsulate a lookup map and will use C++11’s std::tuple to represent an arguments set.
Good, but what about computing n-th Fibonacci number using memoization? It’s not possible with a current version of
Memoizator since it uses a separate map for each instance even if function is the same. It looks inefficient to store a separate lookup map for each instance of the same function. We’ll fix it by creating a static storage for maps accessed by a function address:
Now let’s compare the memoized version against the regular one. If we compute the 42th fibonacci number using simple recursive version (with exponential time complexity), we’d get
$ time ./a.out 267914296 real 0m5.314s user 0m5.220s sys 0m0.020sNow the memoized one (from the source above):
$ time ./a.out 267914296 real 0m0.005s user 0m0.004s sys 0m0.004s
Moreover, our memoization reduced time complexity from exponential to linear.
UPD: you can take a look at another implementation here: General-purpose Automatic Memoization for Recursive Functions in C++11