問題タブ [bitarray]

画像を扱う2つのシステムを統合しようとしています。1つのシステムはsbyte[]として画像を提供し、もう1つのシステムはBitArrayを使用します。sbyte []からデータを取得し、それをBitArrayに変換する必要があります。誰もがこれを行う方法を知っていますか？

ありがとう、ポール

VB.NET で 1 バイトから 4 ビットを格納する最良の方法は何ですか? 最良の意味は次のとおりです。

• Byte 型から格納する最も簡単な方法。
• ビット単位の操作を実行する際に最も簡単に操作できます。
• ビットを他の型に簡単に変換します。

コンストラクターを介して BitArray に格納すると、ビットの順序が逆になります。これは、最初のビットの値を取得しようとすると、BitArray の最後のエントリでその値を探す必要があることを意味します。それらをブール値の配列に格納しても、バイトから直接変換する方法はなく、他の型への変換が妨げられます。

私は過去に何度もこれをしなければならなかった、そして私は結果に決して満足しなかった。

ソースと宛先の両方が便利なプロセッサ境界で整列（右シフト）されない可能性があるソースから宛先に連続したビット配列をコピーする高速な方法を誰かが提案できますか？

ソースと宛先の両方が整列されていない場合、問題はすぐにどちらか一方だけが整列されていない問題に変更される可能性があります（最初のコピーが言った後）。

出発点として、私のコードは必然的に次のようになります（テストされていない、副作用を無視するこれは単なるカフの例ではありません）：

（実際、これは私が以前に行ったよりも優れています。それほど悪くはありません）

System.Collections.BitArray 配列 (~3000 アイテム) があり、すべてのビットを 1 だけ左にシフトしたいと考えています。ただし、コレクションはその操作をサポートしていないようです (つまり、bitArray << 1 が機能せず、そこに方法はありません）。それを行う方法について何か考えはありますか？

ありがとう！

iOS / Objective-C：ブール値の配列がたくさんあります。

これは、これらの値を格納するための非効率的な方法です。1つだけが必要な場合、各要素に少なくとも8ビットが使用されます。

どうすれば最適化できますか？

私たちのOS教授は、プロセスIDを新しいプロセスに割り当てるために、カーネルはプロセスの最大数（デフォルトでは〜32,768）に相当するサイズの配列の最初のゼロビットを段階的に検索すると述べました。ここで、割り当てられたプロセスIDは1です。その中に保存されます。

私の知る限り、Cにはビットデータ型はありません。明らかに、ここで欠けているものがあります。

ビット配列を構築できるような特別な構造はありますか？これは正確にどのように行われますか？

さらに重要なことに、そのようなアレイで実行できる操作は何ですか？

私は、Active Directory を含むプロジェクトで System.DirectoryServices をしばらく使用してきました。特定のアカウントの属性を制御する UserAccountControl プロパティの実装に興味があります。x または y 設定の状態を判断するためにバイトの組み合わせを使用して自分のアプリケーションに設定を実装したい場合、C# でこれを行うにはどうすればよいでしょうか? 自分のクラスに useraccountcontrol プロパティを実装し、バイトの組み合わせを使用してアカウントに必要なアクセス許可を決定したいとします。

Active Directory での変更方法は次のとおりです: http://support.microsoft.com/kb/305144

ここにオブジェクト定義のある場所があります: http://msdn.microsoft.com/en-us/library/ms680832%28VS.85%29.aspx

編集：

独自の User クラスがあり、Active Directory で UserAccountControl を実装するのと同様の方法でプロパティを実装したいとします。設定を保存する 4 バイトのセットが必要だとしましょう。

最後のバイトを使用して、アカウントのステータスを判断したいと考えています。

次に、左側の次のバイトにアカウントの種類を含めたい: 16=管理者アカウント、32=通常のアカウント、64=ゲスト アカウント、128=その他のアカウント。

次に、左側の次のバイトを使用して、256 = 何か、512 = 何か他のもの、1024 = 何か他のものなどのように、他の設定を設定します。

これを組み合わせて、ビットごとの組み合わせを使用してアカウントのプロパティを設定したいと思います。アイデアは頭の中にありますが、それを実装する方法がわかりません。また、自分がやろうとしていることを理解できるかどうかさえわかりません。

編集：答えを受け取ってさらに掘り下げた後、フラグの設定について詳しく説明しているこのリンクを見つけました：http://msdn.microsoft.com/en-us/library/ms229062.aspx

私には特別なニーズがあり、最も重要な懸念事項は次のとおりです。

• インメモリ
• 非常に低いメモリフットプリント
• 速度

これが私の「問題」です。メモリ内に、非常にまばらなビット配列を大量に格納する必要があります。これらのビットセットは「追加のみ」であり、主に交差に使用されます。巨大とは、200 000 ビット配列という意味です。

各ビットセットの範囲は [0...16 000 000] です。

取得した実際のデータを含む「のみ」10 673 ビット配列を使用して事前テストを実行したところ、次の結果が得られました。

関連する数値を見ると、明らかに圧縮されたビット配列を使用する必要がありますが、それは問題ではありません。ビット配列が「追加のみ」であることを考えると、扱いやすいままです。

オンになっているビット配列のビットは、グループ化されていますが、完全ではありません。そのため、同じ領域でいくつかのビットがオンになる傾向があります (ただし、通常は連続してオンになるわけではないため、オンになっているビットには RLE が適していません)。

私の質問は、どのような圧縮を使用するのですか?

最初のアプローチをここに置くべきか、それとも自分の質問への回答に置くべきかはわかりません。

基本的に、非常に愚かなエンコーディングを使用した「最悪のケース」のシナリオを想像しました。

• 1 ビット: オンの場合、次の 5 ビットは「スキップ」を計算するために必要なビット数を決定します。オフの場合、最適化: 次の 5 ビットは、文字どおり (つまり、「オン」または「オフ」) に取りすぎるビット数を決定します。 '、スキップなし) [これは、他の表現よりも効率的であると判断された場合にのみ切り替えられるため、開始時には常に最適化されます (サイズに関して)]

• 5 ビット: 次のビットがオンになる前にスキップできるビット数

• x ビット: スキップ

例を次に示します。ビット配列には 3 ビット セットがあり、最初のビットは 3 098 137、2 番目のビットは 3 098 141、3 番目のビットは 3 098 143 です。

最初のビットは、ビットをスキップすることを示しています。次の 5 ビット (常に 5) は、スキップするビット数を伝えるために必要なビット数を示します。 22 ビットは、3 098 137 にスキップするように指示します。1 ビットオフは、ビットをスキップしないことを伝えます。次の 5 ビット (常に 5) は、伝えます。 「そのまま」読み取るビット数 6 ビット: オフ、オフ、オフ、オン、オフ、オン 3 098 141 および 3 098 143 がオンなどを意味します。

これらのビット配列の驚くべきスパース性を見ると、これは非常にサイズ効率が良いようです。

そのため、そのエンコーディングを使用して、サンプル データを取得し、「最悪の場合」のシナリオを計算しました (まだアルゴリズムを書いていないので、最初にここからいくつかの入力を取得したいと思います)。また、5 ビットが常に最大値 (24 ビット) に設定されますが、これはもちろん起こりません。

私は、「最悪の最悪」のケースが何であるかについて、非常に大まかな概算を得るためにそれを行いました.

とても嬉しい驚きでした：

データは実際のデータであり、すべてのデータが類似しているため、さらに悪いことに、200,000 ビットの配列を約 240 MB に格納できることがわかっています。これは問題ありません。

実際のエンコーディングはそれよりもはるかに少ないと確信していますが、まだ実際に書いていないので、（非常に簡単に）「最悪のケース」しか計算できないため、そのケースのみを示します。

これをよりサイズ効率的にする方法に関するヒント/アイデア（これらは非常にまばらなビット配列であり、数十万個あり、メモリ内にある必要があり、「追加のみ」になることを覚えておいてください） ?

「追加のみ」のケースについて

基本的に、私は1つの成長する「広がり」（範囲ですが、「広がり」は私が理解している実際の用語です）と、いくつかのビットセットを持つ多くのビット配列を持っています。範囲がたとえば 0 から 1 000 000 になると、すべてのビット配列は 0 から 1 000 000 になります。範囲が 1 000 001 まで大きくなると、すべてのビット配列も 1 ビットずつ大きくなります。ただし、これらのビット配列のほとんどは末尾に「0」が追加され、ビット配列の約 4 ～ 8 には末尾に「1」が追加されます。ただし、どのビット配列に 0 または 1 が追加されるかを事前に予測することはできません。

したがって、すべて同じサイズで、すべて非常にまばらで (ビットセットの < 0.5%)、範囲の拡大に伴ってすべて「成長」しているビット配列がたくさんあります (したがって、それらはすべて常に成長しています)。同じレートで）。

ジュディの配列は素晴らしいです。しかし、私は数年前にそれらについて読みましたが、そのことは「私の頭の上」にありました。Judy 配列は C のみの 20KLOC ライブラリであり、私はそれを再実装するつもりはありません。しかし、彼らは素晴らしいです。

したがって、これらすべてを比較的単純なままにしておきたいと思いますが、これは、非常にまばらなビット配列の特別な「追加のみ」のプロパティを見てそれほど大げさではありません。

.NET Micro Frameworkの代わりにBitArrayはありますか？単純にbool[]を使用することを考えていましたが、どうすればそれをbyte []に​​戻すことができますか？

完全なフレームワークでは、「ビット」がBitArrayであると考えると、次のように機能します。

しかし、マイクロフレームワークでBitArrayクラスが見つからないようです

タグを含む stackoverflow の投稿をできるだけ効率的に (バイナリで) シリアライズおよびデシリアライズしたいと想像してみてください。そのようなシナリオに適したデータ構造はありますか?

Stackoverflow には約 28532 の異なるタグがあり、すべてのタグを含むテーブルを作成して整数を割り当てることができます。さらに、最も一般的なタグの番号が最小になるように頻度で並べ替えることができます。「1 32 45」の形式の文字列のように単純にそれらを保存することは、検索と保存の観点からは少し効率が悪いようです

もう 1 つのアイデアは、タグを変数 bitarray として保存することです。これは、ルックアップとシリアル化の観点から魅力的です。最も一般的なタグが最初にあるため、タグを少量のメモリに収めることができる可能性があります。

もちろん、問題は、一般的ではないタグが巨大なビット配列を生成することです。大きな範囲の 0 のビット配列を「圧縮」するための標準はありますか? それとも、他の構造を完全に使用する必要がありますか?

編集

DB ソリューションやテーブル全体をメモリに保持する必要があるソリューションを探しているのではなく、個々のアイテムをフィルタリングするための構造を探しています