C ++ memoization的理解 [英] 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;
}

我的f​​ibHash [N]如何工作有点困惑。这是否只是抱着每个FIB（＃）的各个值？另外，通过索引迭代traversess查找表中，并返回了正确的值？例如FIB（6）=找到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?

推荐答案

在code确实保存每个 fib_val 到 fibHash 地图。该找到方法呼吁 fibHash 搜索地图，看看价值为previously计算。如果是这样，找到此值返回一个迭代器，函数返回它（返回* 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; 添加在地图上的新值

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