.net - いつBitVector32を使用する必要がありますか？

Question

私はある時点で、まだ利用可能な日を1か月間表示する必要があるプロジェクトに取り組んでいます。利用可能な日数を計算する機能があります。私の同僚は次のように述べています。「ああ、あなたは返す必要がありますBitVector32。これはブール値のリストを操作するときに最も効率的です。」私はList<bool>そのようなものを使用したでしょう。あなたが実際にビットを扱っているとき、 ABitVector32は低レベルのもののためのものであるように私には思えます。

だから、問題はです。BitVector3232アイテム未満のブール値のリストが必要な場合はいつでも使用する必要がありますか、それとも低レベルのものにのみ使用する必要がありますか？

score 5 · Accepted Answer

リストの使用は、他の期間に簡単に拡張できます。一度に2か月表示したいとします。ああ、それは32よりも大きいです。リターンタイプとそれが使用されるすべての場所を変更する必要があります。素晴らしい！そしてBitVector32、実装すらしていませんIEnumerable<T>。

そして、それがタイトなループの可読性と保守性の最高の効率でない限り。また、1秒間に100万回実行しない限り、リスト割り当てのオーバーヘッドはそれほど大きくありません。

したがって、低レベルのコードにはBitVector32のみを使用する必要があることに同意します。

score 3 · Accepted Answer

BitVector32は、c＃のビット演算のラッパー（または抽象化と呼ぶことができます）です。たとえば、次の2つのステートメントは同じ結果を返します。

1 << 1
BitVector32.CreateMask（1）

いくつかの重複した数値を含む整数配列があるとしましょう。すべての重複を見つけたい。もちろん、LinqでGroupBy関数を使用することもできますが、Linqがない場合を考えてみましょう。

最初のオプションは、各要素が指定された配列内のすべての要素と比較される強引なアプローチです。

foreach(int i in list) 
{
    foreach(int j in list)
    {
        if (i == j) 
        {
            // print this or store it in the result list
        }
    }
}

ブルートフォースアプローチではN平方の実行時間が発生し、これはかなり非効率的であるため、一定のルックアップ時間またはO（1）を提供するHashSetを利用することを考えることができます。
```
HashSet<int> hashSet = new HashSet<int>();

foreach(int i in list)
{    
    if (hashSet.Contains(i))
    {
        // print the duplicate or add it to the result list
    }
    else
    {
        hashSet.Add(i);
    }
}
```

このアプローチにより、実行時間またはO（n）が線形になります。ただし、n * 4バイトの追加メモリが必要です（32ビット整数について話していると仮定します）

3番目のアプローチは、ブール配列を使用することで必要なメモリが少ないことを除いて、ハッシュセットの使用に似ています。

bool[] masks = new bool[list.Length];

for (int i = 0; i < list.length; i++) 
{
    if (masks[list[i]])
    {
        // print or add to the result list
    }
    else
    {
        masks[list[i]] = true;
    }
}

HashSetの代わりにブール配列を使用します。実行時間はO（n）と同じですが、ブール型は1バイト（8ビット）を使用し、整数は4バイト（32ビット）を使用するため、メモリの1/4の量が必要です。

最後に、BitVector32クラスまたはネイティブビットシフト操作を使用してこの問題を解決できます。

int check = 0;
for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i];
    if (check & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        check = check | mask;
    }
}

また、合計32ビットのメモリで実行時間が線形になります。したがって、メモリ使用量はn/32です。もちろん、配列の最大値が32より大きい場合、これは機能しません。64ビットの符号なし整数を使用してマスクのスロット数を増やすことができますが、制限は非常に短いです。その場合、BitVectory32の配列を作成し、その配列の次のインデックスにあるBitVector32オブジェクトにビットをシフトできます。たとえば、コードは次のようになります

BitVector32[] bitVectorArray = new BitVector32[maxValue / 32];
bitVectorArray[list[i] / 32] = 1 << list[i] % 32;

このように、32ビットサイズの制限に制限する必要はありません。メモリ容量が許す限り、大きなマスクのサイズを無期限に拡大できます。だから、すべてをまとめます：

// This code assumes you know the range of the number in the array
BitVector32[] bitVectorArray = new BitVector32[maxValue / 32];

for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i] % 32;

    if (bitVectorArray[(list[i] - 1)/32][i] & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        bitVectorArray[(list[i] - 1)/32] = bitVectorArray[list[i] / 32] | mask;
    }
}

.net - いつBitVector32を使用する必要がありますか？

2 に答える 2

Related

Reference