true に設定されているビット数で線形である (おそらく巨大な) を反復処理する方法はありstd::bitsetますか? ビットセット内のすべての位置をチェックする必要がないようにしたい。反復は、true に設定された各ビットのインデックスを連続して返す必要があります。
10985 次
6 に答える
18
標準のビットベクトルは、真のビットに対する効率的な反復をサポートしていません。実行時間は常に O(n) です。ここで、n は合計ビット数であり、k に依存しません。ただし、van Emde Boas ツリーやy-fast 試行などの特殊なデータ構造があり、時間 O(k lg lg n) でのビットの反復をサポートします。ここで、n はビット数、k は真のビット数です。
于 2011-01-17T01:14:17.660 に答える
4
それが線形であるためには、リンクされたリスト/配列/セットのインデックスがtrueに設定されている必要があります。このようなセカンダリ インデックスを保持することは、std::bitset が必要とするパフォーマンスとストレージのトレードオフの一部ではありません。特定の要件がなければ、すべての人に不利になるため、実装でこれを提供する方法はありません。このようなコンテナーを自分でビットセットに追加するか、boost のマルチインデックス コンテナー ライブラリを使用することを検討できます。
于 2011-01-17T01:01:36.093 に答える
1
合計ビット数でO（N）よりもはるかに優れているオプションは2つだけです。
- x86のBSFなどの特定のアーキテクチャで利用可能な特殊なビットスキャン命令を使用します。
- ワードに設定された最下位ビットを見つけるためのO（log2（N））アルゴリズムがあります。もちろん、これは、ビットセットがスパースではなく密である場合、適切にスケーリングされません。私の霧の記憶を復活させて、私はFXTライブラリのソースを見つけました。詳細はFXTブック（pdf）のセクション1.3.2にあります。
于 2012-05-22T22:19:06.350 に答える
1
u64アキュムレータと次のような32エントリテーブルを使用して、一度に最大32ビットをチェックできます
u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};
32ビットをu64アキュムレータに読み込み、オフセットに応じてシフトダウンし、ビットをテーブルと照合します。これをバイナリ形式で実行して、比較回数を最大 5 にすることができます。これは、形式が「線形」ではないデータの場合は遅くなります。これがログ時間になります。
于 2011-01-17T01:05:06.613 に答える
0
時々 、そのようなものにランレングス エンコーディングを使用することがあります。入力ビットセットをラン長の配列にエンコードすると、最終的にランの数がセット ビットとクリア ビットの間の遷移数を超えることはありません。これは最大で2*kです。さらに、多くのアプリケーションでは、遷移の数が よりもはるかに少ないためk、線形の最悪の場合のパフォーマンスに加えて、優れた平均時間パフォーマンスが得られます。
nさらに、 「配列内の th 位置から始まる次のセット ビット」などを効率的に検索できるようにするデータ構造を追加するのは簡単です。ランレングスのスキャンを作成するだけです。
于 2016-04-20T21:45:47.223 に答える
-1
ビットセット全体をループし、単純に値をチェックし、true の場合はインデックスを格納します。IS 線形です。ルックアップ テーブルを使用すると、高速化できます。このコードを参照してください：
于 2011-01-17T01:02:17.877 に答える