c++ - 支持递归函数的自动内存

Question

博文Automatic Memoization in c++0x提供用于生成现有函数的内存版本的函数。博客文章和相关代码之前已在 stackoverflow 上讨论过(例如 What does this C++11 code do? )，但是，这些解决方案都无法提供能够正确内存递归函数的完全通用的内存器。

当然，有一个通过使用类似这样的东西来改变递归调用的技巧(假设我们有一个 memoizer，比如博客文章中介绍的一个名为 memoize 的已经到位):

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));
}

但这感觉更像是一种变通方法而不是正确的解决方案，因为我们仍然需要访问我们想要内存的函数。一个合适的解决方案应该能够完全记住任何函数，包括在某些库中定义的函数。然而，产生这样的解决方案似乎超出了我的能力范围(假设它是可能的)，因此我要问:

Is a truly universal memoise function possible?
How can one achieve such a feat?

如果这不可能，是否至少有一种方法可以概括上述方法。类似的东西(不编译并且不是有效的 C++):

int fib(int n){
  if  (n < 2) return n;
  return this_func(n-1) + this_func(n-2);
}

在哪里this_func是类似于 this 的东西类的指针，但用于函数。 [编辑: 这可能仍然会遇到 this_func 的问题指针将指向 fib而不是 memoized fib ]

Answer 1

由于缓存需要在函数调用之间共享，您要么必须将其作为参数传递，要么以其他方式共享。一种共享它的方法是使用函数对象:

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 部分。

还有一个临时生命周期的技巧，可以将内存函数作为参数传递；像这样:

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)`
}

但是，这需要更改 memoize，因为 recurse const& 不能(也不应该)成为内部 map 的一部分.

_{注意那些 const& 也可以是 && 以延长生命周期，但是，由于移动语义，这可能会造成混淆}