4

私はビットマップを持っています

uint64_t bitmap[10000]

システムに割り当てられたリソースを追跡します。ここで問題となるのは、このビットマップの最初のunset（zero）ビットをどのように効率的に見つけるかです。

ffsll(unsigned long long)glibcには、最初のセットビットを見つけるための機能があることを認識しています。これは、ハードウェア命令を使用して行うと思います。

私の場合、この関数を使用するには、最初に配列を初期化してすべてのビットを1に設定する必要があります。次に、リソース割り当てを行うときに、配列で最初のゼロ以外の単語を線形に検索する必要があります。次に、ffsll（）を使用して最初のセットビットを見つけます。

どうすればもっと速くできますか？

更新：私はx86-64CPUを使用しています。

4

3 に答える 3

5

ビットマップのツリーを維持して、最も低いビット セットを効率的に見つけることができます。64 ビット CPU では、4096 個の 64 ビット要素を追跡するために必要なツリーの深さは 3 だけです。つまり、3 つのffsll呼び出しのみを使用することになります。

基本的に、これは配列を 64 ワードのチャンクに分割し、各チャンクに 1 つの 64 ビット インデックスを割り当てることで機能します。インデックス ワードのビットは、対応するビットセット ワードにすべてのビットが設定されている場合に設定されます。ビットセットのビットを変更すると、対応するインデックス ワードが調整されます。

次に、その上に別のインデックス配列を構築して、ツリーを形成できます。

ビットの変更ごとに少し余分な作業が必要ですが、空きビットが必要なときにビットセットを線形に検索する必要がないことから得られる節約と比較すると、余分な作業 (およびストレージ) の総量はごくわずかです。

于 2013-02-14T02:44:45.687 に答える
1

これよりもはるかに速くなる方法はわかりませんが、間違っていることが証明されても構いません。

uint64_t bitmap[10000];
unsigned int i;
for (i = 0; i < (sizeof(bitmap) / sizeof(*bitmap)) && 0xFFFFFFFFFFFFFFFF == bitmap[i]; ++i);
const int bitInWord = ffsll(bitmap[i]);
const unsigned int firstZeroBit = bitInWord ? i * sizeof(*bitmap) * CHAR_BIT + bitInWord : 0;
于 2013-02-14T02:33:30.440 に答える
0

32 ビットの CPU を使用している場合は、そうしたくないでしょう。代わりに、32 ビット整数の配列を使用してください。配列のループは高速になります。

また、1バイトのすべての値をエンコードしてから、バイトに設定された最初のビットを事前に保存することもできます。したがって、すべてが 0xFFFFFFFF ではない整数が見つかった場合は、単純にバイトを比較できます。最初のバイトが 0xFF でない場合、それはそのバイトにあり、以下同様です。

したがって、バイトが 0xFF でない場合、そのバイトの 255 の可能な値の 1 つであることを意味します。そして、各値には最初のビットが設定されています。

問題を調べるもう 1 つの方法は、可能であれば問題をチャンクに分割することです。あなたのリソースが何であるかわからないので、私は言えません。

また、セットされていないビットの前のスキャンで、前方にループしたことも考慮してください。前の結果のインデックスを保存すると、次の検索で同じインデックスから簡単に開始できます。このインデックスを pos と呼び、毎回使用します。

また、ビットをゼロに設定するたびに「空き」インデックスの小さな配列を作成することもできます。そのため、「pos」が配列の最後に達したときに、保存されたインデックスの 1 つから再び開始するだけです。

言い換えれば、毎回このような長いループを実行したくないということです。それはあなたの問題であり、ビットを取得するための最終的な指示ではありません。上記のインデックス トラッキングを使用すると、何百倍も速くなります。

于 2013-02-14T02:34:23.467 に答える