c++中的记忆函子包装器
c++中的记忆函子包装器
提问于 2014-07-08 17:00:39
这里是我为函数编写的通用回忆录包装器。它利用了管状散列。
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;
}
}
};Fibonacci数的用法示例。
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);
}问题是，理想情况下，我可以在递归函数的开头添加几行代码，然后完成回忆录。但是简单的替换不起作用，这就是我坚持的地方。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-07-08 21:16:16
您的问题似乎是，您在每次函数调用时都在本地复制回忆录，然后销毁它。
下面是你回忆录的一个简单的论证版本，似乎很有效：
#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步版本可能更好。
首先，是一个前奏，对函数和回忆器包装进行了前向声明。
第二，在函数内部，函数名的别名，因此递归调用使用记忆函数。
第三，函数声明后，别名为函数名，所以外部调用也使用回传版本。
上面的代码只回溯递归调用，而不是初始调用。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24637619
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号