在C++中编写通用记忆函数11

Question

寻找一种方法来实现一个通用通用记忆函数，该函数将采用一个函数并返回相同的记忆版本？

在python中寻找像@memo（来自Norving's site）的装饰器。

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++中可能使用的C++ 11的新功能呢？

Answer 1

虽然@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 

编辑：示例用法：

Edit2：正如指出的，这不适用于递归函数。

#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"; 
    } 
} 

Answer 2

紧凑一个返回一个拉姆达：

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，可以使用广义返回类型推演避免通过返回std::function施加的额外的间接。

这是完全一般的，允许传递任意函数对象而不包含它们在std::function中首先作为读者的练习。

Answer 3

做记忆化C++中正确的方法是在混合的Y组合子。

您的基本功能需要修改。它不是直接调用它自己，而是将自身的模板化引用作为其第一个参数（或者，递归作为其第一个参数）。

我们从Y-combinator开始。然后，我们在operator()的缓存中添加并将其重命名为memoizer，并给它一个固定的签名（对于表）。

唯一剩下的就是编写一个tuple_hash<template<class...>class Hash>，它对元组进行哈希处理。

可以记忆的功能的类型是(((Args...)->R), Args...) -> R，它使((((Args...) -> R), Args...) -> R) -> ((Args...) -> R)类型的记忆器成为可能。使用Y组合器来生成“传统”递归实现也很有用。

请注意，如果memoized函数在调用期间修改了其参数，则记忆器会将结果缓存在错误的位置。

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)}; } 

live example与基于关闭this SO post硬编码的散列函数。

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); 
    } 
); 

Answer 4

我挣扎于同样的问题。我创建的宏也支持（在递归代码中进行小修改）递归。那就是：

#include <map> 
#include <tuple> 
#define MEMOIZATOR(N, R, ...)        \ 
R _ ## N (__VA_ARGS__);          \ 
std::map<std::tuple<__VA_ARGS__>, R> _memo_ ## N;   \ 
template <typename ... Args>        \ 
R N (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 :)