这个 C++11 代码（memoize）有什么作用？

Question

我发现一篇文章包含此代码：

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(std::function<ReturnType (Args...)> func)
{
    std::map<std::tuple<Args...>, ReturnType> cache;
    return ([=](Args... args) mutable {
            std::tuple<Args...> t(args...);
            if (cache.find(t) == cache.end())                
                cache[t] = func(args...);
            return cache[t];
    });
}

你能解释一下吗请问这个？我在这里无法理解很多事情，但最奇怪的是缓存是本地的而不是静态的，但也许我错了......

Answer 1

这是 memoization 的简单 C++1x 实现。

memoize 函数返回一个闭包。返回值是一个函数，其状态不同于通过参数传递的状态（在本例中为 cache 变量）。

匿名函数中的 [=] 位指示返回的函数应获取所有局部变量的副本。 cache 变量不是静态的，因为它应该在返回函数的调用之间共享。

因此，每次调用 memoize 都会返回一个不同的函数及其自己的缓存。对 memoize 返回的特定闭包的后续调用将从该闭包的缓存中插入/获取值。

您可以将其视为在某种程度上等同于更老式的 OOP 版本：

template <typename ReturnType, typename... Args>
class Memoize
{
    std::map<std::tuple<Args...>, ReturnType> cache;
public:
    ReturnType operator() (Args... args)
    {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end())                
            cache[t] = func(args...);
        return cache[t];
    }
};

Answer 2

缓存嵌入到 lambda 本身中，并且位于其本地。

因此，如果您创建两个 lambda，每个都将拥有自己的缓存。

这是实现简单缓存的好方法，因为这样一旦 lambda 超出范围，所使用的内存就会被清除，并且不会出现内存爆炸的情况。

Answer 3

只要正确调用，“这段简单的代码”也可以记忆递归函数。这里我举一个完整的例子：

#include <functional>
#include <iostream>
#include <tuple>
#include <map>

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func) {
  std::map<std::tuple<Args...>, ReturnType> cache;
  return ([=](Args... args) mutable {
          std::tuple<Args...> t(args...);
          if (cache.find(t) == cache.end())
             cache[t] = func(args...);
          return cache[t];
  });
}

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

std::function<int (int, int)> b;
int binomial(int n, int k) {
  if (k == 0 || n == k) return 1;
  return b(n-1, k) + b(n-1, k-1);
}

int main(void) {
  f = memoize(std::function<int (int)>(fib));
  std::cout << f(20) << std::endl;
  b = memoize(std::function<int (int, int)>(binomial));
  std::cout << b(34,15) << std::endl;
}

Answer 4

引用您找到此内容的博客，就在代码下方：

...[=] 中的等号表示“捕获
周围的局部变量
按价值范围”，这是需要的
因为我们要返回 lambda
函数，局部变量将
那一刻就消失了。

因此，cache 被复制到返回的函数对象中，就像它是一个成员一样。

（请注意，这段简单的代码将无法记忆递归函数。实现定点C++0x 中的组合器 留给读者作为练习。）

Answer 5

欢迎来到词法作用域的奇妙世界。它可用于创建具有公共和私有成员的整个类型。在函数式语言中，这通常是做到这一点的唯一方法。

我建议您阅读 http://mark-story .com/posts/view/picking-up-javascript-closures-and-lexical-scoping，这是关于 Javascript 的，但 C++0x 向 C++ 添加了相同的概念和（几乎相同）的行为。