自动记忆支持递归功能 [英] Automatic memoisation with support for recursive function
问题描述
博文 c ++ 0x中的自动记事功能提供用于产生现有功能的记忆版本的功能。博客文章和相关代码之前在stackoverflow(例如这是什么C + +11 code do?),但是,这些解决方案都没有能够提供一个完全通用的memoizer,它能够正确地记忆递归函数。
The blog post Automatic Memoization in c++0x provides an function for producing a memoized version of an existing function. The blog post and the associated code have been discussed previously on stackoverflow (e.g. What does this C++11 code do?), however, none of these solutions is able to provide a fully universal memoizer which is able to correctly memoize recursive functions as well.
当然,有一个窍门,通过使用这样的东西(假设我们有一个memoizer,如在博客文章中提出的 memoize
已经到位,改变递归调用):
Sure, there is the trick of changing the recursive call by using something like this (assuming we have a memoizer such as the one presented in the blog post called memoize
already in place):
std::function<int (int)> f;
int fib(int n) {
if (n < 2) return n;
return f(n-1) + f(n-2);
}
int main(void) {
f = memoize(std::function<int (int)>(fib));
}
但是,这种感觉更像是一个解决方案,而不是正确的解决方案,因为我们仍然需要访问到我们想要记忆的功能。一个合适的解决方案应该能够完全记忆任何函数,包括在一些库中定义的函数。但是,产生这样的解决方案,所以看起来是超出我的范围(假设是可能的),因此我问:
But this feels more like a workaround than a proper solution because we still need access to the function which we want to memoize. A proper solution should be able to fully memoize any function including the ones which are defined in some library. However, producing such a solution, so it seems, is beyond my reach (assuming it is possible), therefore I'm asking:
是真正的通用记忆功能吗?
如何可以实现这样的专长吗?
Is a truly universal memoise function possible?
How can one achieve such a feat?
如果这是不可能的,是否有至少一种方式推广上述方法。沿着(不编译并且不是有效的C ++)的行的一些:
And if this is not possible, is there at least a way to generalise the above approach. Something along the lines of (does not compile and is not valid C++):
int fib(int n){
if (n < 2) return n;
return this_func(n-1) + this_func(n-2);
}
其中 this_func
这类似于类的这个
指针,而是一个函数。 [修改:这可能仍然会受到 this_func
指针指向 fib
而不是记住的 fib
]
Where this_func
is something which is similar to the this
pointer of a class but for a function. [ This would probably still suffer from the problem that the this_func
pointer would point to fib
instead of the memoized fib
]
推荐答案
要在函数调用之间共享,你必须将它作为参数传递,否则分享它。一种共享方式是使用函数对象:
As the cache needs to be shared across function calls, you'd either have to pass it as an argument, or share it otherwise. One way to share it is using a function object:
struct fib
{
std::map<std::tuple<int>, int> cache;
int operator()(int n)
{
if(n < 2) return n;
auto memoize = [this](int p)
{
auto i = cache.find(p);
if(i == cache.end()) i = cache.insert({p, (*this)(p)}).first;
return i->second;
};
return memoize(n-1) + memoize(n-2);
}
};
您可以将 memoize
。
还有一个技巧,临时生命周期将memoized函数作为参数传递;类似这样:
There's also a trick with temporary lifetime to pass the memoized function as an argument; something like this:
struct recurse // possibly a class template
{
std::function<int(int, recurse const&)> f; // possibly `mutable`
template<class T>
recurse(T&& p) : f( memoize(decltype(f){p}) )
{}
int operator()(int x) const
{
return f(x, *this);
}
};
int fib(int n, recurse const& f);
int fib(int n, recurse const& f = {fib})
{
if(n < 2) return n;
return f(n-1) + f(n-2); // or `fib(n-1, f) + fib(n-2, f)`
}
b $ b
然而,这需要改变 memoize
,因为 recurse const&
't)是内部映射
的一部分。
Yet, this requires a change of memoize
, as the recurse const&
cannot (and shouldn't) be part of the internal map
.
那些 const&
也可以是生命周期扩展的&&
,但是,由于移动语义
N.B. those const&
could also be &&
for lifetime extension, yet, that might be confusing due to move semantics
这篇关于自动记忆支持递归功能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!