4

ビットのフィルターを使用して非常に大きな検索マスクを保存しようとしています。

両方ともstd::vector<bool>、std::bitset<n>ブール表現をビットとして格納します。これは、通常はまたはのサイズである通常のブールとは異なりcharますint32_t。

問題は、これらのデータ構造の両方が1つの巨大なブロックのメモリに要素を格納することです。大きすぎるブロックを要求したことで、オペレーティングシステムが私に腹を立てています。1つstd::deque<bool>は、その要素をリンクリストのようなものに格納することです。

シフトせずに単一ビットへのポインタを使用することはできないことを私は知っています。リンクリストタイプの構造を使用すると、メモリ節約の目的が無効になります。しかし、の2ギガブロックのように格納しchar[]、シフトを使用して個々のビットを設定し、次に別の2ギガブロックへのリンクポインタを使用することはできますか？

それで、このタイプの構造がどこかに存在するか、あるいは可能でさえあるかどうか教えてください。

4

3 に答える 3

4

私はあなたの問題に対する直接的な解決策を知りませんが、カスタムコンテナによって簡単に解決することができます。

1つのソリューションwoudlは、単にstd::bitsetのstd::dequeを含みます。ビットセットのサイズが256などの2の累乗である場合。これを使用すると、インデックスを取得して、両端キューインデックスとビットセットインデックスを個別にマスクすることができます。

std::deque< std::bitset<256> > ;
unsigned long long = 1500;

bool val = bigBitset[ index>>8 ][ index & 0xFF ];

これは、便宜上、クラス内にカプセル化することもできます。

class DequeBitset : public std::deque< std::bitset<256> >
{
public:
    struct Index
    {
        unsigned long index;

        unsigned long dequeIndex() const { return index>>8; }       
        unsigned long bitsetIndex() const { return index&0xFF; }
        Index( unsigned long index ) : index(index) {}
    };
public:

    bool operator[]( const Index& index )
    { return std::deque< std::bitset<256> >::operator [](index.dequeIndex())[ index.bitsetIndex() ]; }
};

int _tmain(int argc, _TCHAR* argv[])
{
    DequeBitset test;
    test.resize(10);
    bool val = test[259];
    return 0;
}
于 2013-02-27T00:23:05.633 に答える
1

カスタム等式と対応するブロックを操作するビット単位の演算子を使用して、目的の「ブロック」クラス（unsigned char [N]、または便宜上ラッパークラス（ビットセットも含む）など）に特化した両端キュー/キューでこれを実現できます。

これらのカスタムビット単位の方法では、操作の各入力「グローバル」ビットインデックスを、変更操作に応じて一連の（ブロック番号、ブロックローカル）インデックスに変換することにより、操作するブロック/範囲を決定する必要があります。非変更操作/クエリは、すべてのブロックに対する単純なトラバーサルとして実装できます。

一般的な考え方は、ビットマスクをブロックに分割し、それらのブロックシーケンスを操作することです。これは、メモリの断片化によっては、実行時に2GB以上の連続したメモリを割り当てることができない場合があるためです。もちろん、ブロックサイズが小さいほど、処理のオーバーヘッド、キャッシュコヒーレンシの低下、メモリの断片化に悩まされますが、クライアントアプリケーションでは、メモリからより多くのメモリを絞り出すことができる場合があります。

@Crogが述べたように、これはすでに実装されているようです。boost::dynamic_bitset

于 2013-02-27T00:10:34.307 に答える
1

使用できる2GBブロックの数がわかりません。しかし、2048個の2GBブロックが必要だとしましょう。次に、2GBブロックへのポインターをベクターに格納します。つまり、std::vector<uint8_t*>構造を拡張する必要があるため、このベクターに新しい2GBブロックを追加します。

于 2013-02-27T00:11:23.147 に答える