#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计算递归公式。 我知道这使用了记忆化，因为我编写了一个使用相同公式的纯递归函数，但是对于更大的 n 值，这个函数要快得多。 我以前从未使用过向量，但我做了一些研究并且理解了它们的概念。 我知道记忆应该存储每个计算值，这样它就可以简单地检索已经计算过的值，而不是再次执行相同的计算。
我的问题是：这种记忆是如何进行的？它是如何工作的？ 我似乎无法在代码中看到它在哪一点检查 n 的值是否已存在。 另外，我不明白 if(as[n]<=0) 的目的。 这个公式可以产生正值和负值，所以我不确定这个检查在寻找什么。
谢谢，我想我已经接近理解它是如何工作的了，它实际上比我想象的要简单一些。
我不认为序列中的值可以是 0，所以这应该对我有用，因为我认为 n 必须从 1 开始。
但是，如果零是我的序列中的可行数字，我可以解决的另一种方法是什么它？ 例如，如果五个永远不会出现怎么办？ 我只需要用五填充我的向量吗？
编辑：哇，在检查代码和输入这个时，我得到了很多其他回复。 谢谢大家的帮助，我想我现在明白了。
#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);
}
The above code sample using memoization to calculate a recursive formula based on some input n. I know that this uses memoization, because I have written a purely recursive function that uses the same formula, but this one much, much faster for much larger values of n. I've never used vectors before, but I've done some research and I understand the concept of them. I understand that memoization is supposed to store each calculated value, so that instead of performing the same calculations over again, it can simply retrieve ones that have already been calculated.
My question is: how is this memoization, and how does it work? I can't seem to see in the code at which point it checks to see if a value for n already exists. Also, I don't understand the purpose of the if(as[n]<=0). This formula can yield positive and negative values, so I'm not sure what this check is looking for.
Thank you, I think I'm close to understanding how this works, it's actually a bit more simple than I was thinking it was.
I do not think the values in the sequence can ever be 0, so this should work for me, as I think n has to start at 1.
However, if zero was a viable number in my sequence, what is another way I could solve it? For example, what if five could never appear? Would I just need to fill my vector with fives?
Edit: Wow, I got a lot of other responses while checking code and typing this one. Thanks for the help everyone, I think I understand it now.
发布评论
评论（5）
if (as[n] <= 0)是检查。 如果有效值可以像你说的那样为负数，那么你需要一个不同的哨兵来检查。 有效值可以为零吗？ 如果没有，则只需进行测试if (as[n] == 0)。 这使得您的代码更容易编写，因为默认情况下int向量用零填充。if (as[n] <= 0)is the check. If valid values can be negative like you say, then you need a different sentinel to check against. Can valid values ever be zero? If not, then just make the testif (as[n] == 0). This makes your code easier to write, because by default vectors ofints are filled with zeroes.该代码似乎错误地检查了 is (as[n] <= 0)，并重新计算了函数的负值（这似乎是大约所有其他值）。 这使得工作量与 n 成线性关系，而不是递归解决方案中的 2^n，因此运行速度更快。
不过，更好的检查是测试 if (as[n] == 0)，它在我的系统上运行速度似乎快了 3 倍。 即使函数可以返回 0，0 值也仅意味着计算时间会稍长一些（尽管如果 0 是频繁返回值，您可能需要考虑一个单独的向量来标记该值是否已计算，而不是使用单个向量来存储函数的值以及它是否已被计算）
The code appears to be incorrectly checking is (as[n] <= 0), and recalculates the negative values of the function(which appear to be approximately every other value). This makes the work scale linearly with n instead of 2^n with the recursive solution, so it runs a lot faster.
Still, a better check would be to test if (as[n] == 0), which appears to run 3x faster on my system. Even if the function can return 0, a 0 value just means it will take slightly longer to compute (although if 0 is a frequent return value, you might want to consider a separate vector that flags whether the value has been computed or not instead of using a single vector to store the function's value and whether it has been computed)
如果公式可以产生正值和负值，那么这个函数就有严重的错误。 检查
if(as[n]<=0)应该检查它是否已经缓存了该计算值。 但是，如果公式可以为负数，则该函数会大量重新计算该缓存值...它真正想要的可能是一个
vector 。 > ，其中布尔值表示该值是否已计算。If the formula can yield both positive and negative values then this function has a serious bug. The check
if(as[n]<=0)is supposed to be checking if it had already cached this value of computation. But if the formula can be negative this function recalculates this cached value alot...What it really probably wanted was a
vector<pair<bool, unsigned> >, where the bool says if the value has been calculated or not.正如所发布的，该代码仅在大约 40% 的时间内记住（恰好是当记住的值为正数时）。 正如 Chris Jester-Young 指出的那样，正确的实现应该检查
if(as[n]==0)。 或者，可以将记忆代码本身更改为as[n]=mod(-4*a(n-1)-4*a(n-2),65535);（甚至当记忆值为 0 时，
==0检查会花费精力。幸运的是，在您的情况下，这种情况永远不会发生！）The code, as posted, only memoizes about 40% of the time (precisely when the remembered value is positive). As Chris Jester-Young pointed out, a correct implementation would instead check
if(as[n]==0). Alternatively, one can change the memoization code itself to readas[n]=mod(-4*a(n-1)-4*a(n-2),65535);(Even the
==0check would spend effort when the memoized value was 0. Luckily, in your case, this never happens!)这段代码有一个错误。 当 as[n] <= 0 时，它将继续重新计算 as[n] 的值。它将记住结果为正的 a 值。 它的工作速度比没有记忆化的代码快得多，因为 as[] 有足够的正值，因此递归可以快速终止。 您可以通过使用大于 65535 的值作为标记来改进这一点。 当向量扩展时，向量的新值被初始化为零。
There's a bug in this code. It will continue to recalculate the values of as[n] for as[n] <= 0. It will memoize the values of a that turn out to be positive. It works a lot faster than code without the memoization because there are enough positive values of as[] so that the recursion is terminated quickly. You could improve this by using a value of greater than 65535 as a sentinal. The new values of the vector are initialized to zero when the vector expands.