3

我正在尝试使用 C++ 以及 boost 和 C++11 规范来学习记忆。但是，我遇到了一个问题，我无法绕开我的头。我在这里关注一个教程：Memoization in C并且教程说您可以使用模板和 lambda 函数来概括递归函数的记忆。本教程还列出了与模板一起使用的递归阶乘和斐波那契函数。但是，该指南仅使用斐波那契函数。

我编写了一个测试程序来看看这一切是如何工作的，并在同一次运行中创建了一个记忆斐波那契和阶乘函数。事情是，记忆模板使用静态映射来存储缓存的值，看起来映射并不是记忆函数的每个实例都是唯一的。这是预期的吗？我应该怎么做才能使地图对每个模板实例都是唯一的？在我开始使用 C++11 特性之前，我曾尝试创建一个模板类，它接受一个 boost 函数来封装这个过程。静态地图会在模板类中是唯一的吗？

创建记忆函数的主要逻辑

// Template function to create memoized versions of recursive lambda functions
template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   return [foo](inType n) {
      static std::map<inType, outType> memo;

      outType ret;
      if (memo.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = memo[n];
         return ret;
      }
      ret = foo(n);
      memo[n] = ret;
      return ret;
   };
}

// Recursive lambda fibonacci function
std::function<int(int) > fibonacci_r = [](int n) {
   if (n <= 1) {
      return n;
   } else {
      return fibonacci_r(n - 1) + fibonacci_r(n - 2);
   }
};

// Recursive lambda factorial function
std::function<int(int) > factorial_r = [](int n) {
   if (n == 0) {
      return 1;
   } else {
      return n * factorial_r(n - 1);
   }
};

测试记忆函数的逻辑

int position = 7;
cout << "Fibonacci:" << endl;
cout << "Non Memo Fibonacci" << endl;
cout << position << "-> " << fibonacci_r(position) << endl;
cout << "Memo Fibonacci" << endl;
fibonacci_r = memoize(fibonacci_r);
cout << position << " -> " << fibonacci_r(position) << endl;

cout << endl;

cout << "Non Memo Factorial" << endl;
cout << position << " -> " << factorial_r(position) << endl;
cout << "Memo Factorial" << endl;
factorial_r = memoize(factorial_r);
cout << position << " -> " << factorial_r(position) << endl;

输出

Fibonacci:
Non Memo Fibonacci
7-> 13
Memo Fibonacci
Cache Hit
Cache Hit
Cache Hit
Cache Hit
Cache Hit
7 -> 13

Non Memo Factorial
7 -> 5040
Memo Factorial
Cache Hit
7 -> 13

在输出的末尾，您可以看到 Memo 阶乘有缓存命中。但是，我认为它不应该只有 1 个缓存命中。无论哪种方式，7!不是 13 和 13是斐波那契备忘录 lambda 下 7 的缓存值。

4

1 回答 1

2

当你写

...似乎地图对于记忆函数的每个实例都不是唯一的。这是预期的吗？

您似乎忘记了变量的实例是static基于类型的，而不是基于参数的值的。两种情况下的类型std::function<outType(inType)>相同。显然，当只有一个实例时，您也只有一个 static map。

部分解决方案可能是这样的：

template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   static int i = 0;
   ++i;
   return [foo](inType n) {
      static std::map<int, std::map<inType, outType>> memo;
      auto& m = memo[i];
      outType ret;
      if (m.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = m[n];
         return ret;
      }
      ret = foo(n);
      m[n] = ret;
      return ret;
   };
}

但请注意，现在每个调用都会生成自己独立的map. 如果你这样做：

auto f1 = memoize(factorial_r);
auto f2 = memoize(factorial_r);

那么f1和f2不会共享一样map。这也意味着如果您经常这样做，您最终可能会使用大量内存。

于 2013-10-22T20:33:17.010 回答