Project Euler の問題を扱うとき、私はしばしば大きな (> 10**7) ビット配列を必要とします。
私の通常のアプローチは次のいずれかです。
bool* sieve = new bool[N];
bool sieve[N];
N = 1,000,000 の場合、私のプログラムは 1 メガバイト (8 * 1,000,000 ビット) を使用します。
c++でboolよりもストアビット配列を使用する効率的な方法はありますか?
58317 次
8 に答える
33
他の人が言及したように（定数の場合）使用std::bitsetします（ただし、Herb Sutterによるこの優れた記事を読むことを忘れないでください）Nstd::vector<bool>
ビットセットは、ビット (0 または 1、true または false などの 2 つの可能な値のみを持つ要素) を格納するように設計された特別なコンテナー クラスです。
このクラスは通常の配列に非常に似ていますが、スペースの割り当てを最適化します。各要素は 1 ビットしか占有しません (これは、C++ の最小の要素型である char の 8 分の 1 です)。
編集：
Herb Sutter (その記事の中で) は次のように述べています。
std::vector< bool > が不適合である理由は、スペースを最適化するために隠れたトリックを引き出すためです: bool[1] ごとに完全な char または int を格納する代わりに (少なくとも 8 倍のスペースを占有します) 、8 ビット char を使用するプラットフォームでは)、bool をパックし、内部表現で個々のビット (たとえば、char 内) として格納します。
std::vector < bool >は、すべてのユーザーに特定の最適化を標準に組み込むことで強制します。それは良い考えではありません。ユーザーごとに要件が異なり、ベクターのすべてのユーザーは、スペースの節約を望まない、または必要としない場合でも、パフォーマンスのペナルティを支払う必要があります。
編集2：
また、Boost を使用したことがある場合は、使用できますboost::dynamic_bitset(N実行時にわかっている場合)
于 2010-09-27T17:59:48.560 に答える
15
良くも悪くも、std::vector<bool>ブールの代わりにビットを使用してスペースを節約します。したがってstd::vector、そもそも本来あるべきだったように使用してください。
Nが定数の場合、 を使用できますstd::bitset。
于 2010-09-27T18:01:09.290 に答える
5
見上げることができstd::bitsetますstd::vector<bool>。後者はvector、名前にあるにもかかわらず、実際には他の種類のオブジェクトのベクトルのようには機能せず、実際には一般的なコンテナーの要件を満たしていないため、推奨されません。それにもかかわらず、それはかなり便利です。
OTOH、100万ビット未満で100万ブール値を（少なくとも確実に）保存するものは何もありません。それは、確実に行うことはできません。ビットセットにある程度の冗長性が含まれている場合、効果的な圧縮スキーム (LZ*、ハフマン、算術演算など) がいくつかありますが、内容に関する知識がなければ、それらが確実であるとは言えません。ただし、これらのいずれも、通常、各 bool/bit を 1 ビットのストレージにのみ格納します (さらに、ブックキーピングのオーバーヘッドが少しかかりますが、通常は定数であり、バイト数から最大で数十バイトのオーダーです)。
于 2010-09-27T18:01:54.787 に答える
4
「bool」型は 1 ビットだけでは格納されません。サイズに関するコメントから、ブールごとに 1 バイト全体を使用しているようです。
これを行うACのような方法は次のとおりです。
uint8_t sieve[N/8]; //array of N/8 bytes
次に、論理 OR バイトをまとめてすべてのビットを取得します。
sieve[0] = 0x01 | 0x02; //this would turn on the first two bits
この例では、0x01 と 0x02 はバイトを表す 16 進数です。
于 2010-09-27T18:04:07.793 に答える
1
バイト配列とそれにインデックスを使用できます。インデックスnは、バイト インデックスn/8、ビット # になりn%8ます。(何らかの理由で std::bitset が利用できない場合)。
于 2010-09-27T17:59:59.270 に答える
0
コンパイル時に N がわかっている場合はstd::bitsetを使用し、そうでない場合はboost::dynamic_bitsetを使用します。
于 2010-09-27T18:08:19.947 に答える