1)。var bitValue = (byteValue & (1 << bitNumber)) != 0;
2)。メソッドで使用System.Collections.BitArrayするGet(int index)
- 何が速いですか？
- .NET プロジェクトでBitArrayがビットごとのシフトとの単純な組み合わせよりも役立つのはどのような状況ですか?
31658 次
4 に答える
26
BitArrayは任意の数のブール値を処理できるようになりますが、abyteは 8、32 のみなどを保持intします。これが 2 つの間の最大の違いになります。
また、整数型が明らかにBitArray実装IEnumerableしていない を実装します。したがって、それはすべてプロジェクトの要件に依存します。IEnumerableまたは配列のようなインターフェイスが必要な場合は、 BitArray.
追跡しているデータの種類がbool[]より明確であるため、実際にはどちらのソリューションよりも使用します。T
BitArrayorは、 8 つのブール値を 1 バイトに「パック」するためbitfield、a の約 1/8 のスペースを使用しますが、a自体は 8 ビット バイト全体を占有します。ビットフィールド or を使用するスペースの利点は、大量の. (数学は読者に任せます:-)) bool[]boolBitArraybools
基準
結果: 私の原始的なテスト環境では、それBitArrayは少し速いように見えますが、整数型で自分でそれを行うのと同じ大きさです。もテストされましたがbool[]、これは当然のことながら最速でした。メモリ内の単一バイトへのアクセスは、異なるバイト内の個々のビットへのアクセスよりも複雑ではありません。
Testing with 10000000 operations:
A UInt32 bitfield took 808 ms.
A BitArray (32) took 574 ms.
A List<bool>(32) took 436 ms.
コード：
class Program
{
static void Main(string[] args)
{
Random r = new Random();
r.Next(1000);
const int N = 10000000;
Console.WriteLine("Testing with {0} operations:", N);
Console.WriteLine(" A UInt32 bitfield took {0} ms.", TestBitField(r, N));
Console.WriteLine(" A BitArray (32) took {0} ms.", TestBitArray(r, N));
Console.WriteLine(" A List<bool>(32) took {0} ms.", TestBoolArray(r, N));
Console.Read();
}
static long TestBitField(Random r, int n)
{
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++) {
SetBit(ref bitfield, r.Next(32), true);
bool b = GetBit(bitfield, r.Next(32));
SetBit(ref bitfield, r.Next(32), b);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static bool GetBit(UInt32 x, int bitnum) {
if (bitnum < 0 || bitnum > 31)
throw new ArgumentOutOfRangeException("Invalid bit number");
return (x & (1 << bitnum)) != 0;
}
static void SetBit(ref UInt32 x, int bitnum, bool val)
{
if (bitnum < 0 || bitnum > 31)
throw new ArgumentOutOfRangeException("Invalid bit number");
if (val)
x |= (UInt32)(1 << bitnum);
else
x &= ~(UInt32)(1 << bitnum);
}
static long TestBitArray(Random r, int n)
{
BitArray b = new BitArray(32, false); // 40 bytes
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++) {
b.Set(r.Next(32), true);
bool v = b.Get(r.Next(32));
b.Set(r.Next(32), v);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static long TestBoolArray(Random r, int n)
{
bool[] ba = new bool[32];
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++) {
ba[r.Next(32)] = true;
bool v = ba[r.Next(32)];
ba[r.Next(32)] = v;
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
}
于 2013-05-09T21:54:27.707 に答える
0
十分に高速な別のソリューションをまだ探している場合は、GetBit メソッドと SetBit メソッドで積極的なインライン展開 [MethodImpl(256)] を使用することをお勧めします。また、ビット位置の OR および XOR 値のルックアップ テーブルも備えています。System.IndexOutOfRangeException はビット位置のエラーを示すのに十分であるため、ビット位置チェックを削除します。追加のチェックのために CPU を消費する必要はありません。また、多数の要素でこれを実行してデバッグする場合は、[DebuggerHidden] 属性の使用を強くお勧めします。DebuggerHidden 属性は、デバッガーがこの属性でマークされたメソッドのデバッグをスキップし、デバッグ プロセスを高速化するのに役立ちます。
Jonathon Reinhartの回答のコードを使用し、このメソッドと TestBitFieldOpt および TestBitFieldOpt2 のテストを追加します。
static readonly uint[] BITMASK = new uint[]
{
0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000
};
static readonly uint[] BITMASK_XOR = new uint[]
{
0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF,
0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF, 0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF,
0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF, 0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF
};
static long TestBitFieldOpt(Random r, int n)
{
bool value;
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
{
SetBitOpt(ref bitfield, r.Next(32), true);
value = GetBitOpt(bitfield, r.Next(32));
SetBitOpt(ref bitfield, r.Next(32), value);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
static long TestBitFieldOpt2(Random r, int n)
{
bool value;
UInt32 bitfield = 0;
var sw = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
{
bitfield = SetBitOpt2(bitfield, r.Next(32), true);
value = GetBitOpt(bitfield, r.Next(32));
bitfield = SetBitOpt2(bitfield, r.Next(32), value);
}
sw.Stop();
return sw.ElapsedMilliseconds;
}
[MethodImpl(256)]
static bool GetBitOpt(UInt32 bitfield, int bitindex)
{
return (bitfield & BITMASK[bitindex]) != 0;
}
[MethodImpl(256)]
static void SetBitOpt(ref UInt32 bitfield, int bitindex, bool value)
{
if (value)
bitfield |= BITMASK[bitindex];
else
bitfield &= BITMASK_XOR[bitindex];
}
[MethodImpl(256)]
static UInt32 SetBitOpt2(UInt32 bitfield, int bitindex, bool value)
{
if (value)
return (bitfield | BITMASK[bitindex]);
return (bitfield & BITMASK_XOR[bitindex]);
}
テストの数を 10 の累乗で増やしました (より現実的な結果を得るために)。最適化されたコードの結果は、最速の方法にかなり近いものです。
Testing with 100000000 operations:
A BitArray (32) took : 4947 ms.
A UInt32 bitfield took : 4399 ms.
A UInt32 bitfieldopt : 3583 ms.
A UInt32 bitfieldopt2 : 3583 ms.
A List<bool>(32) took : 3491 ms.
一般に、ローカル スタック上の変数が少なく、ブランチが少なく、事前に計算された値がほとんどの場合に勝ちます。したがって、本と鉛筆を入手して、数学を短くしてそれらを少なくします...関数内の真のインライン化は非常に役立ちますが、上記のように、ソースコードの読みやすさ/維持のためにメソッドで [MethodImpl(256)] 属性を使用することをお勧めします.
これが誰かが彼の問題の解決策を見つけるのに役立つことを願っています.
于 2021-07-21T09:10:23.080 に答える