16

我找到了一篇包含此代码的文章：

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

你能解释一下吗？我在这里看不懂很多东西，但最奇怪的是缓存是本地的而不是静态的，但也许我错了......

4

5 回答 5

26

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

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

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

因此，每次调用memoize都会返回一个不同的函数和它自己的cache. 对返回的特定闭包的后续调用memoize将从该闭包的cache.

您可以认为这在某种程度上等同于更老式的 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];
    }
};
于 2011-03-18T14:20:28.643 回答
9

缓存嵌入到 lambda 本身中，并且是本地的。

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

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

于 2011-03-18T14:20:44.540 回答
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;
}
于 2012-11-13T23:30:14.343 回答
2

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

...等号[=]表示“通过值捕获周围范围内的局部变量”，这是必需的，因为我们正在返回 lambda 函数，并且局部变量将在那一刻消失。

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

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

于 2011-03-18T14:11:03.023 回答
0

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

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

于 2011-03-18T14:10:04.187 回答