支持递归功能的自动记忆功能

博客文章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)); 
}

但这种感觉更像是一种解决方法，而不是一个合适的解决方案，因为我们仍然需要访问我们想要记忆的功能。一个合适的解决方案应该能够完全记忆任何功能，包括某些库中定义的功能。然而，生产这样的解决方案似乎超出了我的范围（假设它是可能的），因此我在问：

是否可以实现真正的通用记忆功能？
如何可以实现这样的壮举？

如果这是不可能的，是否至少有一种方法来推广上述方法。沿（不编译和无效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]

来源

2014-01-10 elemakil

我不认为今天有什么办法做到这一点，特别是预编译的库。我的第一个猜测是，在事实之后添加记忆的方法是使用链接器用memoized_fib（）包装函数替换fib（）的重定位。然而，我不知道编译和链接阶段的细节，以了解内部递归在链接阶段是否可用于替换。哦，我不知道有一个链接器可以做这种替换。 – Speed8ump

如果您希望递归调用使用相同的缓存，我认为您需要以某种方式在它们之间共享缓存。也就是说，要么使用'static'（更好，但更慢：'thread_local'）缓存或将缓存作为附加参数传递。无论哪种方式都需要修改'fib'。（[wikipedia]上的一个例子]（https://en.wikipedia.org/wiki/Fixed_point_combinator#Explanation_for_imperative_programmers），它使用后一种技术，通过函数的memoized版本将缓存作为参数传递。） – dyp

我的猜测是，这是不可能的，而定义的行为的范围内停留，因为有无法抽象出递归调用。事实上，我想不出比你提供的全局变量版本更好的东西。

一个明显的理念提供了一个抽象点更强大的比一个全局变量将是添加的功能改乘作为第一个参数：

int fib(std::function<int (int)> rec, int n) 
{ 
    if (n < 2) return n; 
    return rec(n - 1) + rec(n - 2); 
}

然后，你可以修改你的memoize的函数传递memoized版本到第一个参数，并且事情应该是正常的。这个技巧通常用于完成（统一/非类型化）功能语言（如方案）中的相同目标。

但是，这种技巧依赖于一种叫做"Y combinator"的东西，我认为它不能在C++中存在，因为它具有无限类型。

来源

2014-01-10 15:06:11 rmcclellan

现在，'' rec'和'fib'不共享相同的签名... – Jarod42

你是对的，我的答案是，它不起作用，因为没有超越标准就无法打字，因为C++有不支持递归类型 – rmcclellan

以下可能会有所帮助，但它仍然是一个黑客，这是丑陋的...：

int fib(void* f, int n) 
{ 
    if (n < 2) return n; 
    auto this_func = *reinterpret_cast<std::function<int (void*, int)>*>(f); 
    return this_func(f, n - 1) + this_func(f, n - 2); 
} 


int main(int argc, char *argv[]) 
{ 
    std::function<int (void*, int n)> fib1 = &fib; 
    std::cout << fib1(reinterpret_cast<void*>(&fib1), 5) << std::endl; 

    auto f = memoize(fib1); 
    std::cout << f(reinterpret_cast<void*>(&f), 5) << std::endl; 

    return 0; 
}

我用void*因为正确的签名是递归的： -/

来源

2014-01-10 15:21:32 Jarod42

'void *'在C中也是一个问题，其中使用了包含函数指针作为成员的IIRC'struct'。像'struct recursive_fun {using f = int（recursive_fun，int）; f * m; };'（当然你可以在C++中添加'operator（）'） – dyp

实际上，它可以通过使用缓存作为数据成员的函数对象来简化;） – dyp

由于高速缓存需求要通过函数调用进行共享，您必须将其作为参数传递，否则将共享它。分享它的方法是使用一个函数对象：

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函数的技巧;是这样的：

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

_{N.B.那些const&也可能是&&延长寿命，但是，这可能是由于移动语义造成的混淆}

来源

2014-01-10 16:37:33 dyp

支持递归功能的自动记忆功能

回答

相关问题