0

これが私の現在の問題です。マトリックスに構築したいブルームフィルターがいくつかあります。

[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
...
[1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0]

各列は BitSet から派生します。すべての行をループして各インデックスを比較する以外に、ビットが 1 に設定されているすべての列を見つけるより効率的な方法はありますか?

これに役立つデータ構造はありますか?

4

1 に答える 1

2

どの列に 1 が含まれているか、各列に何個含まれているかを探していると仮定すると、それらをループするのが最良のアイデアのように思えます。

いくつかの短絡ロジックを使用してループを実装すると、より良い平均実行時間が得られます。

何かのようなもの：

for (int column = 0; column < width; column++) {
    for (int row = 0; row < height; row++) {
        if (array[column][row] == 1) {
            list.append(column);
            break;  // move on to the next column because we don't care what's 
                    // left in this column as we already found our '1'

このコードを使用すると、最悪の場合(すべてbitがの場合0) の実行時間n (nの合計数bits) が得られます。これはかなり良好です。

しかし、極端に不運でない限り、短絡ロジックにより実行時間が大幅に短縮されます。

上記はビットの配列に対してBitSets機能しますが、独自の便利な機能がいくつかあります。

ABitSetには次の関数が含まれます。length()これは、セット ビット + 1 (または0セット ビットがない場合) で最高nextSetBit(index)のインデックスを返し、次のセット ビットのインデックスを返しますindex -> end。

したがって、コードは簡単に次のようになります。

int index = 0;

while (index < BitSet.length()) {
    index = BitSet.nextSetBit(index);
    list.append(index);
    index++;
}
于 2013-05-12T13:59:24.120 に答える