这个C ++函数如何使用memoization？

Question

#include <vector>
std::vector<long int> as;

long int a(size_t n){
  if(n==1) return 1;
  if(n==2) return -2;
  if(as.size()<n+1)
    as.resize(n+1);
  if(as[n]<=0)
  {
    as[n]=-4*a(n-1)-4*a(n-2);
  }
  return mod(as[n], 65535);
}

上面的代码示例使用memoization来计算基于某些输入的递归公式n。我知道这使用了memoization，因为我编写了一个使用相同公式的纯递归函数，但对于更大的if(as[n]<=0)值，这个更快，更快。我之前从未使用过载体，但我做了一些研究，并且我理解它们的概念。我知道memoization应该存储每个计算值，因此它不是再次执行相同的计算，而是可以简单地检索已经计算过的值。

我的问题是：这个备忘录是怎么回事，它是如何运作的？我似乎无法在代码中看到它检查n的值是否已经存在。另外，我不明白<=>的目的。这个公式可以产生正值和负值，所以我不确定这个检查是在寻找什么。

---

谢谢，我想我已经接近理解它是如何工作的，它实际上比我想象的要简单得多。

我认为序列中的值不能为0，所以这应该对我有用，因为我认为n必须从1开始。

但是，如果在我的序列中零是可行的数字，那么我可以用另一种方法解决它？例如，如果五个永远不会出现怎么办？我只需要用五个填充载体吗？

编辑：哇，在检查代码并输入这个代码时，我收到了很多其他回复。感谢大家的帮助，我想我现在明白了。

Answer 1

if (as[n] <= 0)是检查。如果有效值可能是负面的，那么你需要一个不同的哨兵来检查。有效值是否可以为零？如果没有，那么只需进行测试if (as[n] == 0)。这使您的代码更容易编写，因为默认情况下int s的向量用零填充。

Answer 2

代码似乎是错误检查（如[n] <！> lt; = 0），并重新计算函数的负值（看起来几乎是所有其他值）。这使得使用递归解决方案使用n而不是2 ^ n线性地工作比例，因此它运行得更快。

但是，更好的检查是测试if（as [n] == 0），这似乎在我的系统上运行速度提高了3倍。即使该函数可以返回0，0值也只意味着计算需要稍长的时间（尽管如果0是一个频繁的返回值，您可能需要考虑一个单独的向量来标记该值是否已经计算而不是使用单个向量来存储函数的值以及是否已经计算了它）

Answer 3

如果公式可以产生正值和负值，则此函数存在严重错误。检查if(as[n]<=0)是假设检查它是否已经缓存了这个计算值。但是如果公式可以是负数，则此函数会重新计算此缓存值...

它真正想要的是一个vector<pair<bool, unsigned> >，如果值已经计算出来，那么bool会说。

Answer 4

发布的代码只会记忆大约40％的时间（恰恰是记住的值为正值时）。正如克里斯杰斯特 - 杨指出的那样，正确的实施将改为检查if(as[n]==0)。或者，可以将记忆代码本身更改为读取as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

（即使==0检查会在记忆值为0时花费精力。幸运的是，在您的情况下，这种情况永远不会发生！）

Answer 5

此代码中存在错误。它将继续重新计算as [n]的值为[n] <！> lt; = 0.它会记住结果为正的值。它比没有memoization的代码工作得快得多，因为有足够的正值as []，以便快速终止递归。您可以通过使用大于65535的值作为sentinal来改善这一点。当向量扩展时，向量的新值被初始化为零。