在C ++ 11中编写通用记忆function
寻找一种方法来实现一个通用的通用memoization函数，将采取一个函数，并返回相同的memoized版本？
在Python中寻找像@memo（来自Norving的网站）的装饰器。
def memo(f): table = {} def fmemo(*args): if args not in table: table[args] = f(*args) return table[args] fmemo.memo = table return fmemo 更一般的是，有没有办法用C ++来expressiongenerics和可重用的装饰器，可能使用C ++ 11的新特性？
一个紧凑的返回一个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; } }; }
在C ++ 14中，可以使用广义的返回types演绎来避免由于返回std::function而产生的额外的间接std::function 。
做这个完全一般的，允许传递任意函数对象，而不是先把它们包装在std::function作为读者的练习。
在C ++中进行memoization的正确方法是将Y-combinator混合进来。
您的基本function需要修改。 它不是直接调用自己，而是将自身的模板化引用作为其第一个参数（或者， std::function<Same_Signature>recursion作为其第一个参数）。
我们从一个Y组合器开始 。 然后我们在operator()添加一个caching，并将其重命名为memoizer ，并给它一个固定的签名（对于表）。
剩下的唯一事情就是编写一个tuple_hash<template<class...>class Hash> ， tuple_hash<template<class...>class Hash>一个元组进行散列操作。
可以被记忆的函数的types是(((Args...)->R), Args...) -> R ，这使得types的记忆器( (((Args...) -> R), Args...) -> R ) -> ((Args...) -> R) 。 有一个Y-组合器来产生一个“传统的”recursion实现也是有用的。
请注意，如果memoized函数在调用期间修改了它的参数，记忆器会将结果caching在错误的地方。
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)}; }
基于这个SOpost的硬编码散列函数的实例 。
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); } );
尽pipe@KerrekSB发布了一个链接到另一个答案，我虽然也把我的答案扔在戒指（这可能稍微比联系答案复杂，虽然实质上是非常相似）：
#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
编辑：用法示例：
编辑2：正如指出的，这不适用于recursion函数。
#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"; } }
我也遇到了同样的问题。 我创build的macros也支持（recursion代码中的小修改）recursion。 这里是：
#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; \ } \ }
用法很简单：
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)
看到它的行动： http : //ideone.com/C3JEUT 🙂
