问题描述
这里是一个通用的memoization封装我写的函数。它使用。
template< typename R，typename ... Args>
class memofunc {
typedef R（* func）（Args ...）;
func fun_;
unordered_map< tuple< Args ...>，R，tuplehash :: hash< tuple< Args ...> > >地图_;
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）;
//尝试用这个新的fibo替换fibo，但不工作，为什么？
// function< long long（long long）> fibo = memf;
if（x //这个工作原理，但涉及更改原始代码。
//如何编写代码，使我不需要手动添加这个代码？
return memf（x-1）+ memf（x-2）;
//旧代码
//返回fibo（x-1）+ fibo（x-2）;
}
问题是，理想情况下，我可以只添加几行到递归函数和完成与记忆。
你的问题似乎是你做了一个本地
这是一个简单的单参数版本的memoizer，似乎可以工作：
#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>结果;
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）; //不知道在tuple版本中做什么
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 ... \\\
;
if（x if（x< = 2）return 1;
return foo（x-1）+ foo（x-2）;;
}
int main（）{
std :: cout<< foo（10）<< \\\
;
}
请注意， foo（10） foo 。
这也承认：
#define CAT2（A，B，C）A ## B ## C
#define CAT（A，B，C）定义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 ... \\\
;
if（x< = 0）return 0;
if（x< = 2）return 1;
return foo（x-1）+ foo（x-2）;;
}
适用于喜欢这类事物的巨集。
一个3步版本可能会更好。
首先是一个前缀声明函数和memoizer包装器。 p>
其次，在函数中，函数名称的别名，因此递归调用使用记忆函数。
，在函数声明之后，函数名称的别名，因此外部调用也使用记忆版本。
记住递归调用，从未进行初始调用。
Here is a generic memoization wrapper I wrote for functions. It makes use of 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;
}
}
};
example of usage for Fibonacci numbers.
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);
}
Question is, ideally I could just add a few line to the beginning of the recursive function and done with memoization. But simple replacement doesn't work, and this is where I stuck.
Your problem seems to be that you make a local copy of your memoizer at each function call, then destroy it.
Here is a simple one-argument version of your memoizer that seems to work:
#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";
}
Note that foo(10) only does 10 invocations of foo.
This also admits:
#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);;
}
for people who like macros for this kind of thing.
A 3 step version might be better.
First, a prelude with a forward declaration of the function and memoizer wrapper.
Second, within the function, an alias for the function name, so recursive calls use the memorization function.
Third, after the declaration of the function, an alias for the function name, so external calls also use the memoized version.
The code above only memoizes recursive calls, never the initial call.
这篇关于Memoization函子封装在c ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！