C++ memoization - Fibonacci 函数 - 映射 verus 向量容器执行时间

Question

我正在尝试学习 C++ 中的记忆，并使用 map 和 vector 实现了两个斐波那契函数。我已将它们提交给 Coursera 数据结构课程。 vector 实施由于花费太多时间而失败，map 通过正常。由于两者都实现了记忆化，因此有人可以提出为什么一个失败而另一个通过的原因吗？

#include <iostream>
#include <map>
#include <iterator>
#include <vector>

using namespace std;

int fibonacci_fast_vector(int n)
{
    vector <int> cache;

    if(n<=1) {
        return n;
    }
    else if ((unsigned)n >= cache.size()) {
            cache.resize(n+1);
        }

    if(cache[n] != 0) {
        return cache[n];
    }

    // otherwise
    int ret=fibonacci_fast_vector(n-1)+fibonacci_fast_vector(n-2);
    cache[n]=ret;
    return ret;
}


int fibonacci_fast_map(int n)
{
    static map<int,int>memo;

    if(n<=1)
        return n;

    if(memo.count(n)>0) { /*if it is in the map return the element*/
        return memo[n];
    }

    // otherwise
    int ret=fibonacci_fast_map(n-1)+fibonacci_fast_map(n-2);
    memo[n]=ret;
    return ret;
}

int main() {
    int n = 0;
    std::cin >> n;

    std::cout << fibonacci_fast_map(n) << '\n';
    std::cout << fibonacci_fast_vector(n) << '\n';
    return 0;
}

Answer 1

在此代码中：

int fibonacci_fast_vector(int n)
{
    vector <int> cache;

你的向量不是静态的，所以你在每次函数调用时都创建了一个新的向量，所以你的 "memoization" 不仅不能工作，而且实际上会使它变慢。

顺便说一下这段代码：

if(memo.count(n)>0) { /*if it is in the map return the element*/
    return memo[n];
}

不必要且效率低下 - 如果数据存在，您将进行 2 次查找；如果数据不存在，则进行 2 次查找，这在地图上是非常昂贵的操作。你应该使用这样的东西：

auto p = memo.emplace(n,0);
if( p.second ) // data was not there
    p.first->second = fibonacci_fast_map(n-1)+fibonacci_fast_map(n-2);

return p.first->second;

Answer 2

我想问题是你的向量不是静态的。放置一个静态关键字或在全局范围内声明它。这将减少大量的执行时间，因为您避免了许多 news 和 deletes。如果您出于相同的性能原因知道可能的大小，也可以使用一些初始大小向量创建。

C++ memoization - Fibonacci 函数 - 映射 verus 向量容器执行时间

C++ memoization - Fibonacci function - map verus vector container execution time

c++

dictionary

vector

memoization