ビット/ブール値の非常に大きな配列を作成する必要があります。 C/C ++でこれを行うにはどうすればよいですか?
質問
100000000を超える要素を備えたビットの配列を作成することさえ可能ですか?もしそうなら、私はこれをどのように行いますか?私はチャーアレイの場合、私はこれを行うことができることを知っています:
char* array;
array = (char*)malloc(100000000 * sizeof(char));
配列を宣言する場合 char array[100000000]
それから、私はセグメンテーション障害を取得します。なぜなら、要素の最大数が超えているので、私は使用する理由です malloc
.
一連のビットのために同様のことができることはありますか?
解決
C ++を使用している場合、 std::vector<bool>
要素を少しマップに詰めるように特化しています。もちろん、C ++を使用している場合、使用を停止する必要があります malloc
.
他のヒント
あなたは見てみることができます boost :: dynamic_bitset. 。次に、次のようなことをすることができます(Boostの例ページから取られます):
boost::dynamic_bitset<> x(100000000); // all 0's by default
x[0] = 1;
x[1] = 1;
x[4] = 1;
ビットセットは各要素に対して1つのビットを使用して、4バイトのスペースに32個のアイテムを保存でき、必要なメモリの量を大幅に減らすことができます。
CおよびC ++で、 char
最小タイプです。ビットの配列を直接宣言することはできません。ただし、基本的なタイプの配列は基本的にビットで作られているため、このようなもの(コードがテストされていない)をエミュレートできます。
unsigned *array;
array = (unsigned *) malloc(100000000 / sizeof(unsigned) + 1);
/* Retrieves the value in bit i */
#define GET_BIT(array, i) (array[i / sizeof(unsigned)] & (1 << (i % sizeof(unsigned))))
/* Sets bit i to true*/
#define SET_BIT(array, i) (array[i / sizeof(unsigned)] |= (1 << (i % sizeof(unsigned))))
/* Sets bit i to false */
#define CLEAR_BIT(array, i) (array[i / sizeof(unsigned)] &= ~(1 << (i % sizeof(unsigned))))
あなたが気づいたセグメンテーションの障害は、スタックスペースが不足しているためです。もちろん、サイズが12.5 MB(1億ビット)のローカル変数を宣言することはできません。〜4 MBのスタックを持つスレッドでは、サイズが100MB(1億バイト)は言うまでもありません。グローバル変数として機能する必要がありますが、12または100 MBの実行可能ファイルになってしまう可能性がありますが、それでも良い考えではありません。動的割り当ては間違いなくそのような大きなバッファーのために行うのが正しいことです。
STLの使用が許可されている場合は、使用します std::bitset
.
(100,000,000ビットの場合、100000000 /32を使用します unsigned int
その下には、それぞれが32ビットを保管しています。)
std::vector<bool>
, 、すでに述べた、もう1つの良い解決策です。
C ++でビットマップを作成するには、いくつかのアプローチがあります。
コンパイル時間のビットマップのサイズを既に知っている場合は、STLを使用できます。 std::bitset
テンプレート。
これがビットセットでそれを行う方法ですstd::bitset<100000000> array
それ以外の場合、ランタイム中にビットマップのサイズが動的に変更された場合、使用できます std::vector<bool>
また boost::dynamic_bitset
ここで推奨されているように http://en.cppreference.com/w/cpp/utility/bitset (下部のメモを参照)
はい、でももう少し複雑になるでしょう!
ビットを保管するより良い方法は、ビットをチャー自体に使用することです!
そのため、8ビットをチャーに保管できます!
どちらが "それだけ" 12'500'000オクテットが必要です!
これがバイナリに関するいくつかのドキュメントです。 http://www.somacon.com/p125.php
あなたはグーグルを見るべきです:)
その他の解決策:
unsigned char * array; array = (unsigned char *) malloc ( 100000000 / sizeof(unsigned char) + 1); bool MapBit ( unsigned char arraybit[], DWORD position, bool set) { //work for 0 at 4294967295 bit position //calc bit position DWORD bytepos = ( position / 8 ); // unsigned char bitpos = ( position % 8); unsigned char bit = 0x01; //get bit if ( bitpos ) { bit = bit << bitpos; } if ( set ) { arraybit [ bytepos ] |= bit; } else { //get if ( arraybit [ bytepos ] & bit ) return true; } return false; }
私はオープンソースFXTライブラリにあるビタレイが好きです http://www.jj.de/fxt/. 。シンプルで効率的で、いくつかのヘッダーに含まれているため、プロジェクトに簡単に追加できます。さらに、ビタレイで使用する多くの補完的な機能があります(参照 http://www.jj.de/bitwizardry/bitwizardrypage.html).