Remembering a functor wrapper in C ++

Question

Here is a general memoization shell that I wrote for functions. He uses tuplehash .

template<typename R, typename... Args> class memofunc{ typedef R (*func)(Args...); func fun_; unordered_map<tuple<Args...>, R, tuplehash::hash<tuple<Args...> > > map_; public: memofunc(func fu):fun_(fu){} R operator()(Args&&... args){ auto key = make_tuple(std::forward<Args>(args)...); auto q = map_.find(key); if(q == map_.end()){ R res = fun_(std::forward<Args>(args)...); map_.insert({key,res}); return res; }else{ return q->second; } } }; 

example of using Fibonacci numbers.

 long long fibo(long long x){ static memofunc<long long, long long> memf(fibo); // try to replace fibo with this new fibo but doesn't work, why? // function<long long(long long)> fibo = memf; if(x <= 2) return 1; // this works but involves changing the original code. // how to write code such that I dont need to manually add this code in? return memf(x-1) + memf(x-2); // old code // return fibo(x-1) + fibo(x-2); } 

Question: Ideally, I could just add a few lines to the beginning of a recursive function and execute using memoization. But a simple replacement does not work, and this is where I am stuck.

Answer 1

It seems your problem is that you create a local copy of your memoizer every time you call the function, and then destroy it.

Here is a simple one-parameter version of your memoizer that seems to work:

 #include <iostream> #include <functional> #include <unordered_map> template<typename Sig, typename F=Sig* > struct memoize_t; template<typename R, typename Arg, typename F> struct memoize_t<R(Arg), F> { F f; mutable std::unordered_map< Arg, R > results; template<typename... Args> R operator()( Args&&... args ) const { Arg a{ std::forward<Args>(args)... }; // in tuple version, std::tuple<...> a auto it = results.find(a); if (it != results.end()) return it->second; R retval = f(a); // in tuple version, use a tuple-to-arg invoker results.emplace( std::forward<Arg>(a), retval ); // not sure what to do here in tuple version return retval; } }; template<typename F> memoize_t<F> memoize( F* func ) { return {func}; } int foo(int x) { static auto mem = memoize(foo); auto&& foo = mem; std::cout << "processing...\n"; if (x <= 0) return foo(x+2)-foo(x+1); // bwahaha if (x <= 2) return 1; return foo(x-1) + foo(x-2);; } int main() { std::cout << foo(10) << "\n"; } 

living example

Note that foo(10) only performs 10 invocations foo .

It also allows:

 #define CAT2(A,B,C) A##B##C #define CAT(A,B,C) CAT2(A,B,C) #define MEMOIZE(F) \ static auto CAT( memoize_static_, __LINE__, F ) = memoize(F); \ auto&& F = CAT( memoize_static_, __LINE__, F ) int foo(int x) { MEMOIZE(foo); std::cout << "processing...\n"; if (x <= 0) return 0; if (x <= 2) return 1; return foo(x-1) + foo(x-2);; } 

for people who like macros for this kind of thing.

Perhaps a 3-step version would be better.

First, a prelude with forward declaration of function and shell memoizer.

Secondly, inside the function, an alias for the function name, so recursive calls use the remember function.

Third, after declaring a function, an alias for the function name, so external calls also use the memoized version.

The above code only remembers recursive calls, not the initial call.