動的ビットセットより遅いブール値のベクトルを使用していますか?
ブーストの動的ビットセットについて聞いたばかりで、苦労する価値があるかどうか疑問に思っていました。代わりにブール値のベクトルを使用できますか?
15676 次
4 に答える
43
ここでの多くは、作業しているブール値の数によって異なります。
ビットセットと通常はどちらもvector<bool>、ブール値が単一のビットとしてのみ格納されるパック表現を使用します。
一方では、単一の値にアクセスするためのビット操作の形でオーバーヘッドが発生します。
一方、これは、より多くのブール値がキャッシュに収まることも意味します。
多くのブール値を使用している場合 (たとえば、Eratosthenes のふるいを実装している場合)、それらをキャッシュに追加すると、ほとんどの場合、純利益が得られます。メモリ使用量の削減は、ビット操作で失われるよりも多くのメリットをもたらします。
反対意見のほとんどは、std::vector<bool>それが標準のコンテナーではない (つまり、コンテナーの要件を満たしていない) という事実に帰着します。IMO、これは主に期待の問題です-vector多くの人がそれがコンテナであると予想しているため（他のタイプのベクトルはそうです）、vector<bool>コンテナではないという事実に否定的に反応することがよくあります。
ベクトルをコンテナーにする必要がある方法で使用している場合は、おそらく他の組み合わせを使用することをお勧めしdeque<bool>ますvector<char>。ただし、それを行う前に考えてみてください - 一般的に避けるべき (お粗末な、IMO) アドバイスがたくさんありますがvector<bool>、なぜそれを避けるべきなのか、またはどのような状況でそれがあなたに本当の違いをもたらすのかについての説明はほとんどまたはまったくありません.
はい、他の何かがうまく機能する状況があります。そのような状況のいずれかにいる場合は、他のものを使用することは明らかに良い考えです. ただし、最初に自分が実際にそのような状況にあることを確認してください。vector<char>関連するトレードオフについて多くの説明をせずに「ハーブはあなたが使うべきだと言っている」などとあなたに言う人は誰でも信頼されるべきではありません.
実際の例を挙げましょう。コメントで言及されたので、エラトステネスのふるいについて考えてみましょう。
#include <vector>
#include <iostream>
#include <iterator>
#include <chrono>
unsigned long primes = 0;
template <class bool_t>
unsigned long sieve(unsigned max) {
std::vector<bool_t> sieve(max, false);
sieve[0] = sieve[1] = true;
for (int i = 2; i < max; i++) {
if (!sieve[i]) {
++primes;
for (int temp = 2 * i; temp < max; temp += i)
sieve[temp] = true;
}
}
return primes;
}
// Warning: auto return type will fail with older compilers
// Fine with g++ 5.1 and VC++ 2015 though.
//
template <class F>
auto timer(F f, int max) {
auto start = std::chrono::high_resolution_clock::now();
primes += f(max);
auto stop = std::chrono::high_resolution_clock::now();
return stop - start;
}
int main() {
using namespace std::chrono;
unsigned number = 100000000;
auto using_bool = timer(sieve<bool>, number);
auto using_char = timer(sieve<char>, number);
std::cout << "ignore: " << primes << "\n";
std::cout << "Time using bool: " << duration_cast<milliseconds>(using_bool).count() << "\n";
std::cout << "Time using char: " << duration_cast<milliseconds>(using_char).count() << "\n";
}
配列の大部分がメイン メモリを占有することが予想される十分な大きさの配列を使用しました。また、ある呼び出しと別の呼び出しの間で変化するのは a vs.の使用だけであることを確認するために少し苦労しました。ここにいくつかの結果があります。まず VC++ 2015 で:vector<char>vector<bool>
ignore: 34568730
Time using bool: 2623
Time using char: 3108
...次に、g++ 5.1 を使用した時間:
ignore: 34568730
Time using bool: 2359
Time using char: 3116
明らかに、vector<bool>どちらの場合でも勝っています。VC++ で約 15%、gcc で 30% 以上です。vector<char>また、この場合、非常に有利な光で表示されるようにサイズを選択したことに注意してください. たとえば、 をnumberから100000000に減らす10000000と、時間差はさらに大きくなります。
ignore: 3987474
Time using bool: 72
Time using char: 249
確認するために多くの作業を行っていませんが、この場合、使用しているバージョンvector<bool>は、配列がキャッシュに完全に収まるのに十分なスペースを節約しているのに対し、vector<char>はキャッシュをオーバーフローするのに十分な大きさであり、大量のメイン メモリ アクセス。
于 2013-05-24T15:46:43.680 に答える
14
std::vector<bool>標準的なコンテナではないため、通常は避けるべきです。これはパックされたバージョンであるため、通常はvector. 有効な代替手段std::vector<char>は、Herb Sutter が推奨するものを使用することです。
詳細については、この件に関する彼のGotW を参照してください。
アップデート：
指摘されているvector<bool>ように、パック表現は大規模なデータセットの局所性を向上させるため、効果的に使用できます。状況によっては、これが最速の代替手段になる可能性があります。ただし、デフォルトではお勧めしません。これは、によって確立された約束の多くを破りstd::vector、パッキングは速度とメモリのトレードオフであり、速度とメモリの両方にメリットがある可能性があるためです。
あなたがそれを使用することを選択した場合、私はvector<char>あなたのアプリケーションに対してそれを測定した後にそうします. それでも、 aを使用typedefして、それが保持しない保証をしていないように見える名前で参照することをお勧めします。
于 2013-05-24T15:32:33.790 に答える
0
更新vector<bool>: OP がvsについて質問していたことに気付きました。bitset私の答えは質問に答えていませんが、そのままにしておくべきだと思います。c++ vector bool slowを検索すると、ここにたどり着きます。
vector<bool>はひどく遅いです。少なくとも私の Arch Linux システムでは (おそらくもっと良い実装か何かを手に入れることができるでしょう... しかし、私は本当に驚きました)。これが非常に遅い理由について何か提案があれば、私はすべて耳を傾けます! (ぶっきらぼうに始めて申し訳ありません。より専門的な部分は次のとおりです。)
私は SOE の 2 つの実装を書きましたが、「金属に近い」C 実装は 10 倍高速です。sievec.cは C 実装で、sievestl.cppは C++ 実装です。make(暗黙のルールのみ、makefile なし): でコンパイルしたところ、結果はC バージョンで1.4 秒、C++/STL バージョンで12 秒でした。
sievecmp % make -B sievec && time ./sievec 27
cc sievec.c -o sievec
aa 1056282
./sievec 27 1.44s user 0.01s system 100% cpu 1.455 total
と
sievecmp % make -B sievestl && time ./sievestl 27
g++ sievestl.cpp -o sievestl
1056282./sievestl 27 12.12s user 0.01s system 100% cpu 12.114 total
sievec.c以下のとおりであります：
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long prime_t;
typedef unsigned long word_t;
#define LOG_WORD_SIZE 6
#define INDEX(i) ((i)>>(LOG_WORD_SIZE))
#define MASK(i) ((word_t)(1) << ((i)&(((word_t)(1)<<LOG_WORD_SIZE)-1)))
#define GET(p,i) (p[INDEX(i)]&MASK(i))
#define SET(p,i) (p[INDEX(i)]|=MASK(i))
#define RESET(p,i) (p[INDEX(i)]&=~MASK(i))
#define p2i(p) ((p)>>1) // (((p-2)>>1))
#define i2p(i) (((i)<<1)+1) // ((i)*2+3)
unsigned long find_next_zero(unsigned long from,
unsigned long *v,
size_t N){
size_t i;
for (i = from+1; i < N; i++) {
if(GET(v,i)==0) return i;
}
return -1;
}
int main(int argc, char *argv[])
{
size_t N = atoi(argv[1]);
N = 1lu<<N;
// printf("%u\n",N);
unsigned long *v = malloc(N/8);
for(size_t i = 0; i < N/64; i++) v[i]=0;
unsigned long p = 3;
unsigned long pp = p2i(p * p);
while( pp <= N){
for(unsigned long q = pp; q < N; q += p ){
SET(v,q);
}
p = p2i(p);
p = find_next_zero(p,v,N);
p = i2p(p);
pp = p2i(p * p);
}
unsigned long sum = 0;
for(unsigned long i = 0; i+2 < N; i++)
if(GET(v,i)==0 && GET(v,i+1)==0) {
unsigned long p = i2p(i);
// cout << p << ", " << p+2 << endl;
sum++;
}
printf("aa %lu\n",sum);
// free(v);
return 0;
}
sievestl.cpp以下のとおりであります：
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
inline unsigned long i2p(unsigned long i){return (i<<1)+1; }
inline unsigned long p2i(unsigned long p){return (p>>1); }
inline unsigned long find_next_zero(unsigned long from, vector<bool> v){
size_t N = v.size();
for (size_t i = from+1; i < N; i++) {
if(v[i]==0) return i;
}
return -1;
}
int main(int argc, char *argv[])
{
stringstream ss;
ss << argv[1];
size_t N;
ss >> N;
N = 1lu<<N;
// cout << N << endl;
vector<bool> v(N);
unsigned long p = 3;
unsigned long pp = p2i(p * p);
while( pp <= N){
for(unsigned long q = pp; q < N; q += p ){
v[q] = 1;
}
p = p2i(p);
p = find_next_zero(p,v);
p = i2p(p);
pp = p2i(p * p);
}
unsigned sum = 0;
for(unsigned long i = 0; i+2 < N; i++)
if(v[i]==0 and v[i+1]==0) {
unsigned long p = i2p(i);
// cout << p << ", " << p+2 << endl;
sum++;
}
cout << sum;
return 0;
}
于 2016-02-09T21:51:26.920 に答える