1

我试图了解记忆化在 C++ 中是如何工作的，所以我查看了 Fib 中使用的记忆化示例。顺序。

std::map<int, int> fibHash;

int memoized_fib (int n)
{
    std::map<int, int>::iterator fibIter = fibHash.find(n);
    if( fibIter != fibHash.end() ) return *fibIter;

    int fib_val;
    if( n <=1 )    fib_val = 1;
    else           fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 );

    fibHash[ n ] = fib_val;
    return fib_val;
}

我对 fibHash[n] 的工作原理有点困惑。它是否只保存每个 fib(#) 的单个值？此外，迭代器遍历索引以在表中查找正确的值并返回？例如 fib(6) = 找到 fib(5) 和 fib(4)，已经存储并添加它们？

4

3 回答 3

4

你说的基本正确。

“它 [fibHash] 是否只保存每个 fib(#) 的单独值？”

对，就是这样。这些值在计算时被填充（使用fibHash[ n ] = fib_val;）。较低的 fib 值用于计算较高的 fib 值。

该fibHash映射将 X 映射到 fib(X)，简单明了。

这样做的好处是，如果你计算 fib(20)，然后计算 fib(21) 和 fib(23)，然后也许是 fib(15)，你只需要计算一次中间值。

这种加速的成本是将值存储在fibHash.

于 2012-10-05T21:10:10.203 回答
2

代码确实将每个都保存fib_val到fibHash地图中。调用的findfibHash方法搜索地图以查看该值是否是先前计算的。如果是这样，find则返回此值的迭代器，并且函数将其返回 ( return *fibIter)。

fibHash[ n ] = fib_val;在地图中添加一个新值。

于 2012-10-05T21:10:39.920 回答
1

它是否只保存每个 fib(#) 的单个值？

是的。

此外，迭代器遍历索引以在表中查找正确的值并返回？

是的。

例如 fib(6) = 找到 fib(5) 和 fib(4)，已经存储并添加它们？

依靠。首先 fib(6) 搜索以查看之前是否调用过 fib(6)。如果有，则返回存储的答案。如果它从未被调用过，则调用 fib(5) 和 fib(4)。有趣的是，如果必须计算 fib(5)，它会在 fib(6) 之前调用 fib(4)*，然后当 fib(6) 也调用 fib(4) 时，可以保证在 fibHash 中找到结果，因为fib(5) 已经调用了 fib(4)。这就是导致 fib(n) 从指数时间坍缩成更像线性的东西的原因。

斐波那契的朴素递归实现归结为多次加 1。

fib(5) =
fib(4)                                     + fib(3) =
fib(3)                   + fib(2)          + fib(2)          + fib(1) =
fib(2)          + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) =
fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) = 
1      + 1      + 1      + 1      + 1      + 1      + 1      + 1 =
8

实际上，要计算 fib(n)，您最终需要进行 fib(n)-1 加法。但是如果在计算 fib(n) 的过程中您保存并使用之前计算的斐波那契数，那么您不再需要执行这么多的加法。以这种方式计算 fib(n) 只需要 n 次加法：

fib(5) =
fib(4)                            + fib(3) =
fib(3)                   + fib(2) + fib(3) =
fib(2)          + fib(1) + fib(2) + fib(3) =
fib(1) + fib(0) + fib(1) + fib(2) + fib(3) = 
1      + 1      + 1      + 2      + 3 =
8

* 虽然不能保证订单。fib(6) 可以先调用 fib(4)，然后当 fib(6) 调用 fib(5) 时，fib(5) 调用 fib(4) 现在保证返回一个存储的值。

于 2012-10-05T21:40:20.687 回答