25

があり、vector<bool>それをゼロにしたいと思います。変わらない大きさが必要です。

通常のアプローチは、すべての要素を繰り返し処理してリセットすることです。ただし、実装によっては、要素ごとに 1 ビットしか格納できない特別に最適化されたコンテナーvector<bool>です。これを利用して全体を効率的にクリアする方法はありますか?

bitset、固定長バリアントには、set機能があります。vector<bool>似たようなものはありますか？

4

8 に答える 8

22

これまでに投稿された回答には多くの推測がありますが、事実はほとんどないように思われるため、少しテストする価値があるかもしれません.

#include <vector>
#include <iostream>
#include <time.h>

int seed(std::vector<bool> &b) {
    srand(1);
    for (int i = 0; i < b.size(); i++)
        b[i] = ((rand() & 1) != 0);
    int count = 0;
    for (int i = 0; i < b.size(); i++)
    if (b[i])
        ++count;
    return count;
}

int main() {
    std::vector<bool> bools(1024 * 1024 * 32);

    int count1= seed(bools);
    clock_t start = clock();
    bools.assign(bools.size(), false);
    double using_assign = double(clock() - start) / CLOCKS_PER_SEC;

    int count2 = seed(bools);
    start = clock();
    for (int i = 0; i < bools.size(); i++)
        bools[i] = false;
    double using_loop = double(clock() - start) / CLOCKS_PER_SEC;

    int count3 = seed(bools);
    start = clock();
    size_t size = bools.size();
    bools.clear();
    bools.resize(size); 
    double using_clear = double(clock() - start) / CLOCKS_PER_SEC;

    int count4 = seed(bools);
    start = clock();
    std::fill(bools.begin(), bools.end(), false);
    double using_fill = double(clock() - start) / CLOCKS_PER_SEC;


    std::cout << "Time using assign: " << using_assign << "\n";
    std::cout << "Time using loop: " << using_loop << "\n";
    std::cout << "Time using clear: " << using_clear << "\n";
    std::cout << "Time using fill: " << using_fill << "\n";
    std::cout << "Ignore: " << count1 << "\t" << count2 << "\t" << count3 << "\t" << count4 << "\n";
}

したがって、これによりベクトルが作成され、ランダムに選択されたビットが設定され、カウントされ、クリアされます (そして繰り返されます)。設定/カウント/印刷は、積極的な最適化を行っても、コンパイラーがコードを最適化してベクトルをクリアできない/しないようにするために行われます。

控えめに言っても、結果は興味深いものでした。最初に VC++ での結果:

Time using assign: 0.141
Time using loop: 0.068
Time using clear: 0.141
Time using fill: 0.087
Ignore: 16777216        16777216        16777216        16777216

したがって、VC++ では、最も単純な方法として最初に考えられる方法が最速の方法です。つまり、個々の項目に割り当てるループです。ただし、g++ を使用すると、結果は少し異なります。

Time using assign: 0.002
Time using loop: 0.08
Time using clear: 0.002
Time using fill: 0.001
Ignore: 16777216        16777216        16777216        16777216

ここで、ループは (断然) 最も遅い方法です (そして、他の方法は基本的に同点です。速度の 1 ミリ秒の違いは、実際には再現可能ではありません)。

テストのこの部分はg++ の方がはるかに高速であるにもかかわらず、全体の時間は互いに 1% 以内でした (VC++ で 4.944 秒、g++ で 4.915 秒)。

于 2013-10-24T10:45:08.213 に答える
10

あなたは運が悪いです。 std::vector<bool>は、少なくとも cppreference の私の読み取りに基づいて、連続したメモリまたはランダム アクセス イテレータ (またはフォワード?!) さえ保証しないように見える特殊化です。標準のデコードが次のステップになります。

したがって、実装固有のコードを記述し、標準的なゼロ化手法を使用するか、型を使用しないでください。私は3に投票します。

受け取った知恵は、それは間違いであり、非推奨になる可能性があるということです. 可能であれば、別の容器を使用してください。また、内部の内臓をいじったり、そのパッキンに頼ったりしないでください。ライブラリに動的ビットセットがあるかどうかを確認するかstd、独自のラッパーを巻き込んでくださいstd::vector<unsigned char>。

于 2013-10-24T10:17:01.857 に答える
7

最近、パフォーマンスの問題としてこれに遭遇しました。私はウェブで答えを探していませんでしたが、コンストラクターで割り当てを使用すると、g++ O3 (Debian 4.7.2-5) 4.7.2 を使用すると 10 倍高速であることがわかりました。追加を避けたいと思っていたので、この質問を見つけましたmalloc。割り当てはコンストラクターと同様に最適化されており、私のベンチマークでは約 2 倍優れているようです。

unsigned sz = v.size(); for (unsigned ii = 0; ii != sz; ++ii) v[ii] = false;
v = std::vector(sz, false); // 10x faster
v.assign(sz, false); >      // 20x faster

vector<bool>したがって、 ;の特殊化の使用をためらうとは言いません。ビットベクトル表現を十分に認識してください。

于 2016-04-07T17:00:15.627 に答える
7

std::vector<bool>::assignこの目的のために提供されているメソッドを使用します。実装が に固有のものである場合bool、assignも適切に実装されている可能性が高いです。

于 2013-10-24T10:46:10.473 に答える
5

カスタムのビット ベクトル表現に切り替えることができる場合はvector<bool>、高速なクリア操作用に特別に設計された表現を使用して、大幅な速度向上を実現できます (ただし、トレードオフがないわけではありません)。

秘訣は、ビット ベクトル エントリごとに整数を使用し、どのエントリが実際に true と評価されるかを決定する単一の「ローリングしきい値」値を使用することです。

その後、(しきい値がオーバーフローするまで) 残りのデータに触れることなく、単一のしきい値を増やすだけでビット ベクトルをクリアできます。

これに関するより完全な説明といくつかのサンプル コードは、こちらにあります。

于 2014-07-01T13:50:43.330 に答える
4

1 つの優れたオプションがまだ言及されていないようです。

auto size = v.size();
v.resize(0);
v.resize(size);

STL の実装者は、最も効率的なゼロ化の手段を選択したと思われるため、どの特定の方法であるかを知る必要さえありません。std::vector<bool>そして、これは怪物だけでなく、実際のベクトルでも機能します (テンプレートを考えてください) 。

元のサイズではなく、現在のラウンドに必要なものにサイズを変更するだけで、ループ内で再利用されるバッファー (ふるいなど) にはわずかな利点が追加される可能性があります。

于 2016-05-13T14:11:41.727 に答える