在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 🙂