Memoization in C++
Memoization is very useful technique for developing algorithms. Python3 has native support for memoization and here is how it is used.
from functools import lru_cache
@lru_cache #memoization
def fib(n):
if n < 2:
return 1
else:
return fib(n-1) + fib(n-2)
Similar feature can be implemeted in c++ . Here is an example on how to use.
MEMOIZATION(uint64_t, fib,(int n))
{
if(n < 2)
return 1;
return fib(n-1)+fib(n-2);
}
originaly defined uint64_t fib(int n)
has to be wrapped in macro that takes 3 parameters. return_type, func_name and arguments.
so it becomes MEMOIZATION(uint64_t, fib,(int n))
From user’s perspective it looks similar to python’s version.
Here is full implementation of macro MEMOIZATION, Memo class and helper function. This implementation is not same as lru_cache where old items in cache are discarded once limit is reached.
#include <map>
#include <tuple>
#define MEMOIZATION(ret,name,params) \
ret name##nonmemo params; \
auto name = memo_wrapper(name##nonmemo);\
ret name##nonmemo params
template<class...Arg> struct Memo;
template<class R, class...Arg>
struct Memo<R(*)(Arg...)>
{
using funcpoint_t = R(*)(Arg...a);
using tuple_t= std::tuple<Arg...>;
using map_t = std::map<tuple_t,R>;
Memo(funcpoint_t fp):mFp(fp){}
const R& operator()(Arg...arg)
{
tuple_t tup(arg...);
auto it = mMap.find(tup);
if(it != mMap.end())
return it->second;
else
return mMap.insert(std::make_pair(tup,mFp(arg...))).first->second;
}
private:
funcpoint_t mFp;
map_t mMap;
};
template <class R, class...Arg>
Memo< R(*)(Arg...)>
memo_wrapper( R(*f)(Arg...) )
{
return Memo< R(*)(Arg...)>(f);
}