7

大きなビットマップ (数メガバイト) で連続する 0 または 1 のビットをすばやく検索するのに役立つかなり高速なコードはありますか?

「かなり速い」とは、マシンのワードサイズを利用して、恐ろしく遅いビットごとの分析を行う代わりに、ワード全体を一度に比較できることを意味します（ で行うようなvector<bool>）。

たとえば、ボリュームのビットマップで空き領域を検索する場合 (デフラグなど) に非常に便利です。

4

3 に答える 3

1

Windows には、RTL_BITMAPその API と共に使用できるデータ構造があります。

しかし、私はいつか前にこのコードが必要だったので、ここに書きました (警告、少し醜いです):
https://gist.github.com/3206128

部分的にしかテストしていないため、まだバグがある可能性があります (特にreverse)。しかし、最近のバージョン (これと少しだけ違うだけ) は私にとっては使えるように思えたので、試してみる価値はあります。

全体の基本的な操作は、一連のビットの長さをすばやく検出できるようにすることです。

long long GetRunLength(
    const void *const pBitmap, unsigned long long nBitmapBits,
    long long startInclusive, long long endExclusive,
    const bool reverse, /*out*/ bool *pBit);

その汎用性を考えると、他のすべてはこれに基づいて簡単に構築できるはずです。

いくつかの SSE コードを含めようとしましたが、パフォーマンスが著しく向上することはありませんでした。ただし、一般的に、コードはビットごとの分析を行うよりも何倍も高速であるため、役立つ可能性があると思います。

何らかの方法で のバッファを取得できるかどうかをテストするのは簡単なはずvector<bool>です。また、Visual C++ を使用している場合は、それを行う関数が含まれています。バグを見つけたら、遠慮なくお知らせください。

于 2012-07-30T11:01:32.507 に答える
0

このように聞こえるかもしれません：

http://www.aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29 および http://www.aggregate.org/MAGIC/#Leading%20Zero%20Count

ある種のRLEを実行したいのか、単にバイト単位の0と1ビットをカウントしたいのかはわかりません（0b1001は1x1 2x0 1x1を返す必要があります）。

ルックアップテーブルと高速チェック用のSWARアルゴリズムにより、その情報が簡単に得られる場合があります。このようなビット：

byte lut[0x10000] = { /* see below */ };
for (uint * word = words; word < words + bitmapSize; word++) {
   if (word == 0 || word == (uint)-1) // Fast bailout
   {
       // Do what you want if all 0 or all 1
   }
   byte hiVal = lut[*word >> 16], loVal = lut[*word & 0xFFFF];
   // Do what you want with hiVal and loVal

LUTは、目的のアルゴリズムに応じて構築する必要があります。単語内の連続する0と1の数を数えたい場合は、次のように作成します。

  for (int i = 0; i < sizeof(lut); i++) 
     lut[i] = countContiguousZero(i); // Or countContiguousOne(i)
  // The implementation of countContiguousZero can be slow, you don't care
  // The result of the function should return the largest number of contiguous zero (0 to 15, using the 4 low bits of the byte, and might return the position of the run in the 4 high bits of the byte
  // Since you've already dismissed word = 0, you don't need the 16 contiguous zero case.
于 2012-08-01T10:27:33.313 に答える
0

メモリワードを直接うまく処理する方法がわからないので、バイトで機能する簡単なソリューションを作成しました。便宜上、連続するものを数えるアルゴリズムをスケッチしましょう。

サイズ 256 の 2 つのテーブルを作成します。ここに、0 から 255 までの各数値 (バイトの先頭と末尾にある末尾の 1 の数) を書き込みます。たとえば、数値 167 (2 進数で 10100111) の場合、最初のテーブルに 1 を、2 番目のテーブルに 3 を入力します。最初のテーブルを BBeg、2 番目のテーブルを BEnd と呼びましょう。次に、各バイト b について、2 つのケースがあります。255 の場合、現在の連続する 1 のセットの現在の合計に 8 を追加すると、1 の領域になります。それ以外の場合は、BBeg[b] ビットで領域を終了し、BEnd[b] ビットで新しい領域を開始します。必要な情報に応じて、このアルゴリズムを適応させることができます (これが、ここにコードを入れない理由です。どのような出力が必要かわかりません)。

欠陥は、1 バイト内の (小さい) 連続する 1 のセットをカウントしないことです ...

このアルゴリズムのほかに、ディスク圧縮の場合は、0 (空のディスク領域) と 255 (完全なディスク領域) 以外のバイトを探すだけだと友人が教えてくれました。どのブロックを圧縮する必要があるかのマップを作成するのは、迅速なヒューリスティックです。多分それはこのトピックの範囲を超えています...

于 2012-07-30T13:46:42.517 に答える