C ++中的记忆函子包装器

用户名

这是我为函数编写的通用备忘录包装器。它利用tuplehash

template<typename R, typename... Args>
class memofunc{
    typedef R (*func)(Args...);
    func fun_;
    unordered_map<tuple<Args...>, R, tuplehash::hash<tuple<Args...> > > map_;
public:
    memofunc(func fu):fun_(fu){}
    R operator()(Args&&... args){
    auto key = make_tuple(std::forward<Args>(args)...);
    auto q = map_.find(key);
    if(q == map_.end()){
        R res = fun_(std::forward<Args>(args)...);
        map_.insert({key,res});
        return res;
    }else{
        return q->second;
    }
    }
};

斐波纳契数的用法示例。

long long fibo(long long x){
    static memofunc<long long, long long> memf(fibo);
    // try to replace fibo with this new fibo but doesn't work, why?
    // function<long long(long long)> fibo = memf; 

    if(x <= 2) return 1;
    // this works but involves changing the original code.
    // how to write code such that I dont need to manually add this code in?
    return memf(x-1) + memf(x-2); 
    // old code
    // return fibo(x-1) + fibo(x-2);
}

问题是,理想情况下,我可以在递归函数的开头添加几行,并进行记忆化。但是简单的替换不起作用,这就是我坚持的地方。

Yakk-亚当·内夫罗蒙特

您的问题似乎是在每个函数调用时都制作了本地化的副本,然后销毁了它。

这是您的备忘录的一个简单的单参数版本,似乎可以正常工作:

#include <iostream>
#include <functional>
#include <unordered_map>

template<typename Sig, typename F=Sig* >
struct memoize_t;
template<typename R, typename Arg, typename F>
struct memoize_t<R(Arg), F> {
  F f;
  mutable std::unordered_map< Arg, R > results;
  template<typename... Args>
  R operator()( Args&&... args ) const {
    Arg a{ std::forward<Args>(args)... }; // in tuple version, std::tuple<...> a
    auto it = results.find(a);
    if (it != results.end())
      return it->second;
    R retval = f(a); // in tuple version, use a tuple-to-arg invoker
    results.emplace( std::forward<Arg>(a), retval ); // not sure what to do here in tuple version
    return retval;
  }
};

template<typename F>
memoize_t<F> memoize( F* func ) {
  return {func};
}

int foo(int x) {
  static auto mem = memoize(foo);
  auto&& foo = mem;
  std::cout << "processing...\n";
  if (x <= 0) return foo(x+2)-foo(x+1); // bwahaha
  if (x <= 2) return 1;
  return foo(x-1) + foo(x-2);;
}
int main() {
  std::cout << foo(10) << "\n";
}

现场例子

请注意,foo(10)只有的10次调用foo

这也承认:

#define CAT2(A,B,C) A##B##C
#define CAT(A,B,C) CAT2(A,B,C)
#define MEMOIZE(F) \
  static auto CAT( memoize_static_, __LINE__, F ) = memoize(F); \
  auto&& F = CAT( memoize_static_, __LINE__, F )

int foo(int x) {
  MEMOIZE(foo);
  std::cout << "processing...\n";
  if (x <= 0) return 0;
  if (x <= 2) return 1;
  return foo(x-1) + foo(x-2);;
}

对于喜欢宏的人。

3步骤版本可能更好。

首先,前奏带有对函数和备忘录包装器的正向声明。

其次,在函数内,函数名是别名,因此递归调用使用记忆功能。

第三,在函数声明之后,函数名称是一个别名,因此外部调用使用记忆版本。

上面的代码仅记录递归调用,而不记录初始调用。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章