24

次のコードを実行すると、ベクトルがブール配列よりもはるかに遅いことに気付きました。 

int main() 
{
    int count = 0;
    int n = 1500000;
    // slower with c++ vector<bool>
    /*vector<bool> isPrime;
    isPrime.reserve(n);
    isPrime.assign(n, true);
    */
    // faster with bool array 
    bool* isPrime = new bool[n];

    for (int i = 0; i < n; ++i)
        isPrime[i] = true;


    for (int i = 2; i< n; ++i) {
        if (isPrime[i])
            count++;
        for (int j =2; i*j < n; ++j )
            isPrime[i*j] = false;
    }

    cout <<  count << endl;
    return 0;
}

vector<bool>より速くするためにできる方法はありますか？ところで、 と の両方std::vector::push_backはstd::vector::emplace_backよりもさらに遅いですstd::vector::assign。

4

3 に答える 3

7

vector<bool> 高パフォーマンスになる可能性がありますが、必須ではありません。vector<bool>効率的であるためには、一度に多くの bool を操作する必要があり (例: ) isPrime.assign(n, true)、実装者は細心の注意を払う必要がありました。a の個々の bool のインデックス作成vector<bool>は低速です。

これは、clang + libc++ を使用してしばらく前に書いた主要なファインダーvector<bool>です (libc++ の部分は重要です)。

#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>

std::vector<bool>
init_primes()
{
    std::vector<bool> primes(0x80000000, true);
    primes[0] = false;
    primes[1] = false;
    const auto pb = primes.begin();
    const auto pe = primes.end();
    const auto sz = primes.size();
    size_t i = 2;
    while (true)
    {
        size_t j = i*i;
        if (j >= sz)
            break;
        do
        {
            primes[j] = false;
            j += i;
        } while (j < sz);
        i = std::find(pb + (i+1), pe, true) - pb;
    }
    return primes;
}

int
main()
{
    using namespace std::chrono;
    using dsec = duration<double>;
    auto t0 = steady_clock::now();
    auto p = init_primes();
    auto t1 = steady_clock::now();
    std::cout << dsec(t1-t0).count() << "\n";
}

これは約 28 秒 (-O3) で実行されます。代わりにa を返すように変更するとvector<char>、実行時間は約 44 秒になります。

他の std::lib を使用してこれを実行すると、おそらくこの傾向は見られません。libc++ アルゴリズムstd::findでは、一度にビット単位ではなく、一度にビット単位の単語を検索するように最適化されています。

ベンダーが最適化できる std アルゴリズムの詳細については、http://howardhinnant.github.io/onvectorbool.htmlを参照してください。

于 2016-04-29T18:11:42.790 に答える