.Net BitArrayクラスを広範囲に使用していて、Java BitSet.Cardinality（）メソッドと同等のメソッド、つまり設定されたビット数を返すメソッドが必要なライブラリを実装しています。BitArrayクラスの拡張メソッドとして実装することを考えていました。簡単な実装は、ビットセットを繰り返してカウントすることです（以下のように）が、何千ものセット操作を実行して答えをカウントするので、より高速な実装が必要でした。以下の例よりも速い方法はありますか？
count = 0;
for (int i = 0; i < mybitarray.Length; i++)
{
if (mybitarray [i])
count++;
}
これは、http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallelの「最適なビット カウント法」に基づく私のソリューションです。
public static Int32 GetCardinality(BitArray bitArray)
{
Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];
bitArray.CopyTo(ints, 0);
Int32 count = 0;
// fix for not truncated bits in last integer that may have been set to true with SetAll()
ints[ints.Length - 1] &= ~(-1 << (bitArray.Count % 32));
for (Int32 i = 0; i < ints.Length; i++)
{
Int32 c = ints[i];
// magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
unchecked
{
c = c - ((c >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
count += c;
}
return count;
}
私のテストによると、これは単純な foreach ループよりも約 60 倍高速であり、1000 ビットの BitArray で約 50% のビットが true に設定された Kernighan アプローチよりもさらに 30 倍高速です。必要に応じて、これの VB バージョンもあります。
Linq を使用すると、これを非常に簡単に実現できます
BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
where m
select m).Count();
BitArray myBitArray = new BitArray(...
int
bits = myBitArray.Count,
size = ((bits - 1) >> 3) + 1,
counter = 0,
x,
c;
byte[] buffer = new byte[size];
myBitArray.CopyTo(buffer, 0);
for (x = 0; x < size; x++)
for (c = 0; buffer[x] > 0; buffer[x] >>= 1)
counter += buffer[x] & 1;
" Counting bits set, Brian Kernighan's way " から引用し、バイトに適合させました。1 000 000 以上のビットのビット配列に使用していますが、すばらしいです。
ビットが n*8 でない場合は、mod バイトを手動でカウントできます。
同じ問題がありましたが、変換するカーディナリティ メソッドが 1 つだけではありませんでした。そこで、BitSet クラス全体を移植することにしました。幸いなことに、それは自己完結型でした。
C# port の Gistは次のとおりです。
発見されたバグを報告していただければ幸いです。私は Java 開発者ではなく、ビット ロジックの経験が限られているため、一部を間違って翻訳した可能性があります。
System.Collections.BitArray のコードをプロジェクトにコピーして編集することを気にしない場合は、フェローとして書くことができます:それでも遅いです。）
public void Set(int index, bool value)
{
if ((index < 0) || (index >= this.m_length))
{
throw new ArgumentOutOfRangeException("index", "Index Out Of Range");
}
SetWithOutAuth(index,value);
}
//When in batch setting values,we need one method that won't auth the index range
private void SetWithOutAuth(int index, bool value)
{
int v = ((int)1) << (index % 0x20);
index = index / 0x20;
bool NotSet = (this.m_array[index] & v) == 0;
if (value && NotSet)
{
CountOfTrue++;//Count the True values
this.m_array[index] |= v;
}
else if (!value && !NotSet)
{
CountOfTrue--;//Count the True values
this.m_array[index] &= ~v;
}
else
return;
this._version++;
}
public int CountOfTrue { get; internal set; }
public void BatchSet(int start, int length, bool value)
{
if (start < 0 || start >= this.m_length || length <= 0)
return;
for (int i = start; i < length && i < this.m_length; i++)
{
SetWithOutAuth(i,value);
}
}
Linq を使用することもできますが、役に立たず遅くなります。
var sum = mybitarray.OfType<bool>().Count(p => p);
を使用するより速い方法はありませんBitArray-結局のところ、それらをカウントする必要があります-LINQを使用してそれを行うか、独自のループを実行できますが、によって提供されるメソッドはなくBitArray、基礎となるデータ構造はint[]配列です( Reflector で見られるように) - これは常に O(n) であり、n は配列内のビット数です。
高速化する唯一の方法は、リフレクションを使用して基になるm_arrayフィールドを取得することです。その後、すべての呼び出しで使用する境界チェックを回避できますGet()(以下を参照)。リフレクションはコストがかかるため、非常に大きな配列では価値があります。
public bool Get(int index)
{
if ((index < 0) || (index >= this.Length))
{
throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
}
return ((this.m_array[index / 0x20] & (((int) 1) << (index % 0x20))) != 0);
}
この最適化が本当に重要な場合は、ビット操作用に独自のクラスを作成する必要があります。これは、内部的に を使用できますBitArrayが、設定されたビット数を追跡し、適切なメソッドを提供します (ほとんどの場合、委譲しますBitArray が、ビット数を取得するメソッドを追加します)。現在設定されている) - もちろん、これは O(1) になります。
本当に速度を最大化したい場合は、カーディナリティを持つバイト値を指定してルックアップ テーブルを事前に計算できますが、リフレクションを使用してプルする必要があるため、BitArray はこれに最も理想的な構造ではありません。基礎となるストレージから整数型を操作します-その手法のより良い説明については、この質問を参照してください。
もう 1 つの、おそらくより有用な手法は、カーディナリティ m の n ビット値に対して O(m) であるカーニガンのトリック のようなものを使用することです。
static readonly ZERO = new BitArray (0);
static readonly NOT_ONE = new BitArray (1).Not ();
public static int GetCardinality (this BitArray bits)
{
int c = 0;
var tmp = new BitArray (myBitArray);
for (c; tmp != ZERO; c++)
tmp = tmp.And (tmp.And (NOT_ONE));
return c;
}
これも、整数型と BitArrays の間で定義された操作がないため、C で言うよりも少し面倒です (tmp &= tmp - 1たとえば、最下位セット ビットをクリアするための は に変換されていtmp &= (tmp & ~0x1)ます。
これが BCL BitArray の場合の単純な反復よりも高速になるかどうかはわかりませんが、アルゴリズム的に言えば優れているはずです。
編集：より詳細な説明とともに、カーニガンのトリックを発見した場所を引用
ルックアップ テーブルを使用するものを見つけられなかったので、私は のバージョンを書きました。
private int[] _bitCountLookup;
private void InitLookupTable()
{
_bitCountLookup = new int[256];
for (var byteValue = 0; byteValue < 256; byteValue++)
{
var count = 0;
for (var bitIndex = 0; bitIndex < 8; bitIndex++)
{
count += (byteValue >> bitIndex) & 1;
}
_bitCountLookup[byteValue] = count;
}
}
private int CountSetBits(BitArray bitArray)
{
var result = 0;
var numberOfFullBytes = bitArray.Length / 8;
var numberOfTailBits = bitArray.Length % 8;
var tailByte = numberOfTailBits > 0 ? 1 : 0;
var bitArrayInBytes = new byte[numberOfFullBytes + tailByte];
bitArray.CopyTo(bitArrayInBytes, 0);
for (var i = 0; i < numberOfFullBytes; i++)
{
result += _bitCountLookup[bitArrayInBytes[i]];
}
for (var i = (numberOfFullBytes * 8); i < bitArray.Length; i++)
{
if (bitArray[i])
{
result++;
}
}
return result;
}
問題は当然 O(n) であるため、ソリューションはおそらく最も効率的です。
ビットの任意のサブセットをカウントしようとしているため、ビットが設定されているときにビットをカウントすることはできません (ビットを頻繁に設定しないと、速度が向上します)。
使用しているプロセッサに、設定されたビット数を返すコマンドがあるかどうかを確認できます。たとえば、SSE4 を搭載したプロセッサは、この投稿に従ってPOPCNT を使用できます。.Net ではアセンブリが許可されていないため (プラットフォームに依存しないため)、これはおそらく機能しません。また、ARM プロセッサにはおそらく同等のものはありません。
おそらく最良の解決策は、ルックアップ テーブルです (または、スイッチが currentLocation + byteValue への単一のジャンプにコンパイルされることを保証できる場合はスイッチ)。これにより、バイト全体のカウントが得られます。もちろん、BitArray は基になるデータ型へのアクセスを提供しないため、独自の BitArray を作成する必要があります。また、バイト内のすべてのビットが常に交点の一部であることを保証する必要がありますが、これはありそうにありません。
もう 1 つのオプションは、BitArray の代わりにブール値の配列を使用することです。これには、バイト内の他のビットからビットを抽出する必要がないという利点があります。欠点は、配列がメモリ内の 8 倍のスペースを占有することです。つまり、スペースが無駄になるだけでなく、配列を反復処理してカウントを実行するときに、より多くのデータがプッシュされます。
標準の配列ルックアップと BitArray ルックアップの違いは次のとおりです。
配列:
ビット配列:
アレイの #2 と #3 を除いて、これらのコマンドのほとんどは、完了するのに 1 プロセッサ サイクルかかります。一部のコマンドは、x86/x64 プロセッサを使用して 1 つのコマンドに結合できますが、ARM では使用する命令セットが少ないため、おそらくそうではありません。
2 つ (アレイまたは BitArray) のどちらがより優れたパフォーマンスを発揮するかは、プラットフォーム (プロセッサ速度、プロセッサ命令、プロセッサ キャッシュ サイズ、プロセッサ キャッシュ速度、システム メモリの量 (Ram)、システム メモリの速度 (CAS)、速度) によって異なります。プロセッサと RAM の間の接続) と、カウントするインデックスの広がり (交点が最も頻繁にクラスター化されているか、ランダムに分散されているか)。
要約すると、おそらく高速化する方法を見つけることができますが、あなたのソリューションは、.NET のビットごとのブール モデルを使用してデータ セットを取得する最速のものです。
編集：順番に数えたいインデックスにアクセスしていることを確認してください。インデックス 200、5、150、151、311、6 の順にアクセスすると、キャッシュ ミスの量が増え、RAM から値が取得されるのを待つ時間が長くなります。