C++记忆化理解 [英] C++ Memoization understanding

问题描述

我试图了解记忆在 C++ 中的工作原理，所以我查看了 Fib 中使用的记忆示例.序列.

I was trying to understand how memoization works in C++, so I looked at an example of memoization used in Fib. sequence.

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) = find fib(5) 和 fib(4)，已经存储并添加它们?

I was a little confused with how the fibHash[n] works. Does it just hold the individual values of each fib(#)? Also, the iterator traversess through the index to look for the correct value in the table and returns that? For example fib(6) = find fib(5) and fib(4), already stored and just add them?

推荐答案

代码确实将每个 fib_val 保存到 fibHash 映射中.在 fibHash 上调用的 find 方法搜索地图查看该值是否先前计算过.如果是这样，find 返回一个迭代器这个值，函数返回它(return *fibIter).

The code indeed save each fib_val into the fibHash map. The find method called on fibHash searches the map to see if the value was previously computed. If so, find returns an iterator on this value and the function returns it (return *fibIter).

fibHash[ n ] = fib_val; 在映射中添加一个新值.

fibHash[ n ] = fib_val; adds a new value in the map.

这篇关于C++记忆化理解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！