这个C++函数如何使用记忆？

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

上面的代码示例使用记忆来计算基于一些输入n的递归公式。我知道这使用memoization，因为我已经写了一个纯粹的递归函数，它使用相同的公式，但是这对于更大的值n要快得多。我以前从未使用过载体，但我已经做了一些研究，并且了解它们的概念。我知道memoization应该存储每个计算的值，以便不再执行相同的计算，而是可以简单地检索已经计算的值。这个C++函数如何使用记忆？

我的问题是：这是怎么记忆化，以及它是如何工作的？我似乎无法在代码中看到它检查n的值是否已经存在。另外，我不明白if(as[n]<=0)的目的。这个公式可以产生正面和负面的价值，所以我不确定这张支票正在寻找什么。

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

我不认为序列中的值都不能为0，所以这应该为我工作，因为我认为n具有在1

但是开始，如果零在我的序列号可行，我能以另一种方式解决它？例如，如果五个永远不会出现？我只需要用五个人来填充我的矢量？

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

来源

2008-09-29 Zachary Wright

if (as[n] <= 0)是支票。如果有效值可以像你说的那样是负值，那么你需要一个不同的哨兵来检查。有效值可以为零吗？如果不是，那么只需进行测试if (as[n] == 0)。这使得您的代码更容易编写，因为默认向量int s被零填充。

来源

2008-09-29 03:08:31

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

它真的可能想要的是一个vector<pair<bool, unsigned> >，其中布尔说，如果该值已经计算或没有。

来源

2008-09-29 03:30:23

该代码似乎错误地检查是（如[n] < = 0），并重新计算该函数的负值（似乎是大约每隔一个值）。这使得工作的规模与递归解决方案中的n而不是2^n成线性关系，因此运行速度更快。

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

来源

2008-09-29 03:36:01 Plasmer

我认为当检查结果为[n] <= 0时，只需要较小的基数，它仍然需要指数时间。确实，计算一个（10000） - 它将永远不会完成，即使它没有花时间进行正确的检查。 – 2008-09-29 03:45:17

的代码，作为贴，仅memoizes的时间（精确地，当记忆值为正）约40％。正如Chris Jester-Young所指出的那样，正确的实施将会改为检查if(as[n]==0)。另外，可以改变记忆化代码本身读取as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

（即使是==0检查将花力气当memoized值为0。幸运的是，你的情况，这永远不会发生！）

来源

2008-09-29 03:38:18

有一个错误这段代码。它将继续重新计算as [n]的值，因为[n] < = 0。它将记忆一个结果为正值的值。它的工作速度比没有备忘录的代码快很多，因为as []有足够的正值，所以递归很快结束。你可以通过使用一个大于65535的值作为信号来改善这一点。当矢量展开时，矢量的新值被初始化为零。

来源

2008-09-29 04:20:16

这个C++函数如何使用记忆？

回答

相关问题