在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 :)