問題タブ [bitarray]

初心者向けマニュアルのビットアレイを使用して例を示しました。それらが何に使用できるのか、そしてそれらのいくつかの一般的なデータ構造が何であるのかを知りたいです（「配列」はかなり緩い用語であると仮定します）。

ありがとう。

Dipperstein の bitarray.cpp クラスを使用して、画像データが 1 ピクセル 1 ビットとしてネイティブに保存される 2 値 (白黒) 画像を処理しています。

次のような for ループを使用して、画像ごとに 4 ～ 9 メガピクセルのオーダーで、数百の画像にわたって、すべてのビットを反復処理する必要があります。

パフォーマンスは使用可能ですが、驚くほどではありません。gprof を使用してプログラムを実行すると、かなりの時間と、std::vectoriterator や begin などのメソッドへの数百万回の呼び出しがあることがわかりました。トップサンプル関数は次のとおりです。

私はC++のSTLにあまり詳しくありませんが、たとえば、 std::vector::begin() が数百万回呼び出されている理由を誰かが明らかにすることはできますか? そしてもちろん、それをスピードアップするために何かできることはありますか?

編集：代わりに検索機能（ループ）をあきらめて最適化しました。

C コードにいくつかの uint8_t 配列があり、任意のシーケンス ビットを別のビットと比較したいと考えています。たとえば、bitarray_1 と bitarray_2 があり、bitarray_1 のビット 13 ～ 47 を bitarray_2 のビット 5 ～ 39 と比較したいとします。これを行う最も効率的な方法は何ですか?

現在、ビットを新しい一時配列の先頭にコピーし、それらに memcmp を使用する単純な実装があるため、これは私のプログラムの大きなボトルネックです。

Java で高密度の可変長 bitarray を格納する非常にコンパクトな方法を探しています。現在、私は を使用していますが、サイズnBitSetのビット ベクトルに対して平均1.5*n ビットのストレージ スペースを使用しているようです。通常、これは問題にはなりませんが、この場合、格納されるビット配列はアプリケーションのメモリ フットプリントのかなりの部分を占めます。したがって、それらを少し小さくすることは本当に役立ちます。

BitSet が必要とするスペースは、データ構造をサポートするために使用される long の配列が、より多くのビットを保持するために拡張されるたびに 2 倍になる傾向があるという事実によるものと思われます。

バックエンドのデータ構造をより保守的にスケーリングする BitSet の独自の代替実装を作成できます。しかし、必要がなければ、標準クラス ライブラリに既にある機能を複製するのは本当に嫌です。

私が現在取り組んでいる課題では、ビットベクトルを操作する必要がありますが、Pythonでこれを行う方法がよくわかりません。それらは4ビットから20ビットまでである必要があります。私はこれまでビットベクトルを使用したことがありませんが、通常のAND / OR/XOR演算を使用して操作した符号なしバイトの配列を作成すると思います。

ここでの重要な制限は次のとおりです。標準のPythonで提供されているライブラリ以外のライブラリには依存できません。

8ビットの符号なしバイトの配列を使用してCでこれを行う方法を知っていると思います。たとえば、ゼロ化された配列の18番目のビットを1に変換するには、my_bit_array [3]＆= 1<<2のようにします。

しかし、Pythonは動的型付けされており、配列型が組み込まれていないため、Pythonの方法でこれを行うにはどうすればよいでしょうか。

そして、サイズ20のビットベクトルを表現することは（どのように？）可能ですか？私はおそらく24ビット/3バイトのベクトルを作成し、4ビットを無視することを考えています。

System.Collections.BitArrayアプリケーションのクラスよりも少し多くのものが必要です。具体的には、ビット配列が必要です。

• 不変であること
• 値のセマンティクスを使用して等価性を実装するには

実装structの内部を大部分コピーして、独自の を作成しました。BitArray(ありがとう、.Net Reflector !)

私は毎日ビット単位の演算を扱っているわけではないので、等価性の実装に自信がありません。（私が投げている単体テストに合格していますが、エッジケースが欠けている可能性があります。）以下の回答として提案されたソリューションがあります。より正確または効率的なものについて、他の人のフィードバックと回答をいただければ幸いです。

CLR と同様BitArrayに、lengthフィールドは構造体のビット数を参照し、arrayフィールド (またはArrayプロパティ) はビットを表す 32 ビット整数配列を参照します。

[明確化]不要なビットがゼロであることに依存できないように、コンストラクターやその他のメソッドで簡単な方法を選択しました。例えば、

• Not()~整数配列要素のビットごとの否定 ( ) によって実装されます。
• すべてのビットを初期化するために長さとブール値を取るコンストラクターが利用可能です。初期化値が true の場合、int 配列のすべての要素を -1 に設定します (2 の補数で、すべて 1 で表されます)。
• 等。

したがって、比較でそれらを処理する (というか、むしろ無視する) 必要があります。これらのビットを常にゼロにしておくことも良い解決策ですが、私の状況では、より多くの作業が必要になります (コンピューターと私の両方に!)

xml にシリアル化する必要があるビジネス クラスがあります。BitArray プロパティがあります。

私はそれを飾った[XmlAttribute]が、連載は失敗している

XML シリアル化可能にするには、ICollection から継承する型に、継承階層のすべてのレベルで Add(System.Boolean) の実装が必要です。System.Collections.BitArray は Add(System.Boolean) を実装していません。

xml にシリアル化できるかどうかわかりません。

そうでない場合、BitArray をシリアル化する効率的な手段は何でしょうか

ご覧いただきありがとうございます

「0」と「1」を書き込む非常に大きな配列を作成したいと考えています。ランダムシーケンシャル吸着と呼ばれる物理プロセスをシミュレートしようとしています。このプロセスでは、長さ 2 のユニットである二量体が、互いに重なり合うことなく、ランダムな位置で n 次元格子に堆積します。格子上にさらに二量体を堆積する余地がなくなると、プロセスは停止します (格子が詰まります)。

最初にゼロのラティスから始めます。二量体は 1 のペアで表されます。各二量体が堆積すると、二量体が重ならないという事実により、二量体の左側のサイトがブロックされます。そこで、格子上に「1」のトリプルを配置することで、このプロセスをシミュレートします。シミュレーション全体を何度も繰り返してから、平均カバレッジ % を計算する必要があります。

1D および 2D ラティスの文字の配列を使用して、これを既に行っています。現時点では、3D の問題とより複雑な一般化に取り組む前に、コードをできるだけ効率的にしようとしています。

これは基本的にコードが 1D でどのように見えるかを簡略化したものです:

私が行っている実際のプロジェクトでは、二量体だけでなく、三量体、四量体、およびあらゆる種類の形状とサイズ (2D および 3D) が含まれます。

バイトではなく個々のビットで作業できることを望んでいましたが、読んでいる限り、一度に1バイトしか変更できないため、複雑なインデックス作成を行う必要がありますまたはそれを行う簡単な方法はありますか？

回答ありがとうございます

タイトルが示すように、大きな定数配列 N に存在する M の要素を見つけようとしています。ほとんどの場合、M の要素は N に存在しないため、M に対して行われる検索の大部分は無駄です。時間。

M の本格的な検索を行う前にチェックするインデックスを作成する方法を探しています。私のようなプロジェクトは、M のすべての要素の最初の数バイトからビット配列を作成し、私が理解していることから、高速に検索するためのビット レベルの並列処理。これがどのように機能するのか完全にはわかりません。

では、不必要に M を検索する可能性を減らすために、どのようなトリックを使用できますか?

これはほとんど言語に依存しない質問ですが、できるだけ完全にするために、私は C++ を使用しています。

I need to generate a fast hash code in GetHashCode for a BitArray. I have a Dictionary where the keys are BitArrays, and all the BitArrays are of the same length.

Does anyone know of a fast way to generate a good hash from a variable number of bits, as in this scenario?

UPDATE:

The approach I originally took was to access the internal array of ints directly through reflection (speed is more important than encapsulation in this case), then XOR those values. The XOR approach seems to work well i.e. my 'Equals' method isn't called excessively when searching in the Dictionary:

However, the approach suggested by Mark Byers and seen elsewhere on StackOverflow was slightly better (16570 Equals calls vs 16608 for the XOR for my test data). Note that this approach fixes a bug in the previous one where bits beyond the end of the bit array could affect the hash value. This could happen if the bit array was reduced in length.

The GetInternalValues extension method is implemented like this:

Any suggestions for improvement are welcome!