C++ 记忆化理解

Question

我试图了解记忆化在 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)，已经存储并添加它们？

Answer 1

你说的基本上是正确的。

"Does it [fibHash] just hold the individual values of each fib(#)?"

是的，没错。这些值在计算时填入(使用 fibHash[ n ] = fib_val;)。较低的 fib 值用于计算较高的值。

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

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

此加速的成本是将值存储在 fibHash 中的内存。