sugar 自动为DP 加cache (or打表)

// from http://www.csdn.net/article/2015-12-03/2826381

#include <iostream>
#include <tuple>
#include <memory>
#include <map>
#include <functional>
#include <unordered_map> template <class Function>
auto my_sugar(Function func) {
static std::unordered_map<int, int> m; return [&func](int key) { // why not auto key
if (m.find(key) == m.end()) {
m[key] = func(key);
} return m[key]; // overhead is O(1)
};
} //template <typename R, typename... Args>
//std::function<R(Args...)> cache(R(*func)(Args...)) {
// return func;
//} template <typename R, typename... Args>
std::function<R(Args...)> cache(R(*func) (Args...)) {
auto result_map = std::make_shared<std::map<std::tuple<Args...>, R>>(); // key: cache map is in heap return [=](Args... args) {
std::tuple<Args...> t(args...);
std::cout << "result_map size is " << result_map->size() << std::endl;
if (result_map->find(t) == result_map->end()) {
(*result_map)[t] = func(args...);
} return (*result_map)[t];
};
} template <typename R, typename... Args>
std::function<R(Args...)> sugar(R(*func)(Args...), bool needClear = false) {
using function_type = std::function<R(Args...)>;
static std::unordered_map<decltype(func), function_type> functor_map; // pointer => function if (needClear) {
return functor_map[func] = cache(func);
} if (functor_map.find(func) == functor_map.end()) {
functor_map[func] = cache(func);
} return functor_map[func];
} int f(int n) {
return n < ? n : f(n - ) + f(n - );
} int f_my_sugar(int n) {
return n < ? n : my_sugar(f_my_sugar)(n - ) + my_sugar(f_my_sugar)(n - );
} int f_sugar(int n) {
return n < ? n : sugar(f_sugar)(n - ) + sugar(f_sugar)(n - );
} template <class Function>
void test(Function f) {
int start = ;
int n = ;
for (int i = start; i <= n; ++i) {
std::cout << i << ": " << f(i) << std::endl;
}
} int main() {
std::cout << "f ---------------------" << std::endl;
test(f);
std::cout << "f_my_sugar ------------" << std::endl;
test(f_my_sugar);
std::cout << "f_sugar ---------------" << std::endl;
test(f_sugar); return ;
}
上一篇:MySql密码丢失


下一篇:List 转换 DataTable