//original post: http://s...content-available-to-author-only...o.com/2011/03/17/automatic-memoization-in-cplusplus0x/
//a BOOST way of doing it: http://w...content-available-to-author-only...t.org/doc/libs/1_49_0/libs/flyweight/example/fibonacci.cpp
#include <iostream>
#include <functional>
#include <map>
#include <time.h>
//maahcros
#define TIME(__x) init=clock(); __x; final=clock()-init; std::cout << "time:"<<(double)final / ((double)CLOCKS_PER_SEC)<<std::endl;
#define TIME_INIT clock_t init, final;
//void sleep(unsigned int mseconds) { clock_t goal = mseconds + clock(); while (goal > clock()); }
//the original memoize
template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
{
std::map<std::tuple<Args...>, ReturnType> cache;
return ([=](Args... args) mutable {
std::tuple<Args...> t(args...);
if (cache.find(t) == cache.end()) {
cache[t] = func(args...);
}
return cache[t];
});
}
/// wrapped factorial
struct factorial_class {
/// the original factorial renamed into _factorial
int _factorial(int n) {
if (n==0) return 1;
else {
std::cout<<" calculating factorial("<<n<<"-1)*"<<n<<std::endl;
sleep(0.5);
return factorial(n-1)*n;
}
}
/// the trick function :)
int factorial(int n) {
if (memo) return (*memo)(n);
return _factorial(n);
}
/// we're not a function, but a function object
int operator()(int n) {
return _factorial(n);
}
/// the trick holder
std::function<int(int)>* memo;
factorial_class() { memo=0; }
};
int main()
{
TIME_INIT
auto fact=factorial_class(); //virgin wrapper
auto factorial = memoize( (std::function<int(int)>(fact) ) ); //memoize with the virgin wrapper copy
fact.memo=&factorial; //spoilt wrapper
factorial = memoize( (std::function<int(int)>(fact) ) ); //a new memoize with the spoilt wrapper copy
TIME ( std::cout<<"factorial(3)="<<factorial(3)<<std::endl; ) // 3 calculations
TIME ( std::cout<<"factorial(4)="<<factorial(4)<<std::endl; ) // 1 calculation
TIME ( std::cout<<"factorial(6)="<<factorial(6)<<std::endl; ) // 2 calculations
TIME ( std::cout<<"factorial(5)="<<factorial(5)<<std::endl; ) // 0 calculations
TIME ( std::cout<<"factorial(12)="<<factorial(12)<<std::endl; )
TIME ( std::cout<<"factorial(8)="<<factorial(8)<<std::endl; )
return 0;
}
//upd: gotta find a way to make it work with std::function<int(int)>* memo; instead of a pointer