代码之家 › 专栏 › 技术社区 › samsung gather

C++记忆-斐波那契函数-映射verus向量容器执行时间

memoization vector dictionary c++

-1

samsung gather · 技术社区 · 7 年前

我正在尝试学习C++中的记忆,并使用实现了两个斐波那契函数 map 和 vector 。我已经把它们提交给了Coursera数据结构课程。这个 矢量 由于花费太多时间和 地图 通过OK。由于两者都实现了记忆化,有谁能提出一个失败而另一个通过的原因吗?

#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;
}

2 回复 | 直到 7 年前

1

4

Slava 7 年前

在此代码中:

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

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

顺便说一句,此代码:

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;

2

0

Eduard Rostomyan 7 年前

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