Writing a generic memoization function in C ++ 11

Question

Looking for a way to implement a universal generic memoization function that takes a function and returns a memoized version of the same?

Looking for something like the @memo (from the Norving site) decorator in python.

def memo(f): table = {} def fmemo(*args): if args not in table: table[args] = f(*args) return table[args] fmemo.memo = table return fmemo 

There is more general, is there a way to express universal and reusable decorators in C ++, perhaps using the new features of C ++ 11?

Answer 1

Compact returning lambda:

 template <typename R, typename... Args> std::function<R (Args...)> memo(R (*fn)(Args...)) { std::map<std::tuple<Args...>, R> table; return [fn, table](Args... args) mutable -> R { auto argt = std::make_tuple(args...); auto memoized = table.find(argt); if(memoized == table.end()) { auto result = fn(args...); table[argt] = result; return result; } else { return memoized->second; } }; } 

In C ++ 14, you can use generic return type inference to avoid the additional indirectness imposed by returning std::function .

To make this completely general, allowing you to pass objects to an arbitrary function without wrapping them in std::function , first remains as an exercise for the reader.

Answer 2

The proper way to do memoization in C ++ is to mix Y-combinator in.

Your basic function needs to be modified. Instead of calling itself directly, it takes a template reference to itself as its first argument (or recursion std::function<Same_Signature> as its first argument).

Let's start with the Y-combinator . Then add the cache to operator() and rename it to memoizer and give it a fixed signature (for the table).

It remains only to write tuple_hash<template<class...>class Hash> , which makes a hash on the tuple.

The type of function that can be memoized, (((Args...)->R), Args...) -> R , which makes a memoizer of type ( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R) . It is also useful to use Y-combinator to create a "traditional" recursive implementation.

Note that if the memoized function changes its arguments during a call, memoizer caches the results in the wrong place.

 struct wrap {}; template<class Sig, class F, template<class...>class Hash=std::hash> struct memoizer; template<class R, class...Args, class F, template<class...>class Hash> struct memoizer<R(Args...), F, Hash> { using base_type = F; private: F base; std::unordered_map< std::tuple<std::decay_t<Args>...>, R, tuple_hash<Hash> > cache; public: template<class... Ts> R operator()(Ts&&... ts) const { auto args = std::make_tuple(ts...); auto it = cache.find( args ); if (it != cache.end()) return it->second; auto&& retval = base(*this, std::forward<Ts>(ts)...); cache.emplace( std::move(args), retval ); return decltype(retval)(retval); } template<class... Ts> R operator()(Ts&&... ts) { auto args = std::tie(ts...); auto it = cache.find( args ); if (it != cache.end()) return it->second; auto&& retval = base(*this, std::forward<Ts>(ts)...); cache.emplace( std::move(args), retval ); return decltype(retval)(retval); } memoizer(memoizer const&)=default; memoizer(memoizer&&)=default; memoizer& operator=(memoizer const&)=default; memoizer& operator=(memoizer&&)=default; memoizer() = delete; template<typename L> memoizer( wrap, L&& f ): base( std::forward<L>(f) ) {} }; template<class Sig, class F> memoizer<Sig, std::decay_t<F>> memoize( F&& f ) { return {wrap{}, std::forward<F>(f)}; } 

live example with a hard-coded hash function based on this SO post .

 auto fib = memoize<size_t(size_t)>( [](auto&& fib, size_t i)->size_t{ if (i<=1) return 1; return fib(i-1)+fib(i-2); } ); 

Answer 3

Despite the fact that @KerrekSB posted a link to another answer, I would even drop my answer to the ring (it is probably a little less complicated than the related answer, although in fact it is very similar):

 #include <functional> #include <map> #include <tuple> #include <utility> /*! \brief A template functor class that can be utilized to memoize any * given function taking any number of arguments. */ template <typename R, typename... Args> struct memoize_wrapper { private: std::map<std::tuple<Args...>, R> memo_; std::function<R(Args...)> func_; public: /*! \brief Auto memoization constructor. * * \param func an the std::function to be memoized. */ memoize_wrapper(std::function<R(Args...)> func) : func_(func) { } /*! \brief Memoization functor implementation. * * \param a Argument values that match the argument types for the * (previously) supplied function. * \return A value of return type R equivalent to calling func(a...). * If this function has been called with these parameters * previously, this will take O(log n) time. */ R operator()(Args&&... a) { auto tup = std::make_tuple(std::forward<Args>(a)...); auto it = memo_.find(tup); if(it != memo_.end()) { return it->second; } R val = func_(a...); memo_.insert(std::make_pair(std::move(tup), val)); return val; } }; //end struct memoize_wrapper 

Edit: usage example:

Edit2: As indicated, this does not work with recursive functions.

 #include "utility/memoize_wrapper.hpp" #include <memory> #include <vector> #include <algorithm> #include <iostream> long factorial(long i) { long result = 1; long current = 2; while(current <= i) { result *= current; ++current; } return result; } int main() { std::vector<int> arg {10, 9, 8, 7, 6, 10, 9, 8, 7, 6}; std::transform(arg.begin(), arg.end(), arg.begin(), memoize_wrapper<long, long>(factorial)); for(long i : arg) { std::cout << i << "\n"; } } 

Answer 4

I struggled with the same problem. I created a macro that also supports recursion (with a little modification in the recursive code). There he is:

 #include <map> #include <tuple> #define MEMOIZATOR(N, R, ...) \ R _ ## N (__VA_ARGS__); \ std::map<std::tuple<__VA_ARGS__>, R> _memo_ ## N; \ template <typename ... Args> \ RN (Args ... args) { \ auto& _memo = _memo_ ## N; \ auto result = _memo.find(std::make_tuple(args...)); \ if (result != _memo.end()) { \ return result->second; \ } \ else { \ auto result = _ ## N (args...); \ _memo[std::make_tuple(args...)] = result; \ return result; \ } \ } 

Using is very simple:

 MEMOIZATOR(fibonacci, long int, int); long int _fibonacci(int n) { // note the leading underscore // this makes recursive function to go through wrapper if (n == 1 or n == 2) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); } fibonacci(40) // uses memoizator so it works in linear time // (try it with and without memoizator) 

See in action: http://ideone.com/C3JEUT :)