自动记忆支持递归功能 [英] 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屋！