24

Project Euler の問題を扱うとき、私はしばしば大きな (> 10**7) ビット配列を必要とします。

私の通常のアプローチは次のいずれかです。

bool* sieve = new bool[N];

bool sieve[N];

N = 1,000,000 の場合、私のプログラムは 1 メガバイト (8 * 1,000,000 ビット) を使用します。

c++でboolよりもストアビット配列を使用する効率的な方法はありますか?

4

8 に答える 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 に答える