vector <bool>与数组之间的性能差距
收藏

I was trying to solve a coding problem in C++ which counts the number of prime numbers less than a non-negative number n.

所以我首先想出了一些代码:

int countPrimes(int n) {
    vector<bool> flag(n+1,1);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要88毫秒,并使用8.6 MB的内存。然后,我将代码更改为:

int countPrimes(int n) {
    // vector<bool> flag(n+1,1);
    bool flag[n+1] ;
    fill(flag,flag+n+1,true);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要28毫秒和9.9 MB。我真的不明白为什么在运行时间和内存消耗上都存在这样的性能差距。我读过类似的问题,但我仍然很困惑。

EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing vector<bool> with vector<char>.

最佳答案

std::vector<bool> isn't like any other vector. The documentation says:

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

这就是为什么它可能比数组占用更少的内存的原因,因为它可能表示一个字节的多个布尔值,例如位集。它还解释了性能差异,因为访问它不再那么简单了。根据文档,它甚至不必将其存储为连续数组。

    公众号
    关注公众号订阅更多技术干货!