3

ブール値の配列を作成する必要があります。これは、100,000または数百万のエントリのスケールになる可能性があります。また、超高速である必要があるため、反復ごとに1ミリ秒ごとにカウントされます。

ループを開始する時点で、配列にいくつのエントリがあるかはすでにわかっています。問題は、事前にブール配列を作成してインデックスで値を入力する方が速いのでしょうか（ランダムアクセスですが、遅い可能性がありますか？）、またはを作成List<bool>してリストにエントリを追加し続ける必要があります。エンドリターン.ToArray()？

言い換えると：

オプション1

var array = new bool[size];
for (var n=0; n<size; n++)
  array[n] = GetValue(n);
return array;

オプション2

var list = new List<bool>();
for (var n=0; n<size; n++)
  list.Add(GetValue(n));
return list.ToArray();

それとも、さらに高速な3番目の方法がありますか？

4

4 に答える 4

5

を使用し、System.Collections.BitArray速度について心配する必要はありません。

あなたが上で提案していることはあなたの記憶を無駄にするだけです。これは速度とサイズの両方を最適化し、bool値を適切にパックします（神が意図したように、バイトあたり8つ:)。

以下のコメントへの返信：を使用するBitArrayと、最初はすべてがゼロになります。持っているビットのみを設定しますGetValue == true。

于 2012-07-23T08:39:29.650 に答える
2

最初に行きます。それがそうであるかもしれない唯一の理由。「遅い」とは、プロセッサキャッシュの外部からデータをページングし続ける場合です。

リストには、いくつかのメモリ割り当てとコピーを実行する必要があることを除いて、まったく同じ問題があります。

于 2012-07-23T08:43:02.570 に答える
2

次のコードは、（少なくとも私には）このページで説明されているメソッドの中でbool[]、ループを使用するための単純な割り当てが最も速いことを示しているようです。

コードはまたGetValue(n)、計算上些細なことでない限り、バイトを割り当てるオーバーヘッドは、私が最適化したいと思っているプロセスの一部ではないことを示しているようです。

これが何らかの形で役立つことを願っています。

編集:(私のマシンで）実行からの結果を追加しました

--  187ms    BitArray
--  171ms    List<bool>().ToArray 
--  168ms    bool[] set only if true
--  130ms    bool[] always set
--11460ms    bool[] always set with 'complex' GetValue()

class Program
{
    static void Main(string[] args)
    {
        BitArray bitArray = new BitArray(10000000);
        bool[] boolArray = new bool[10000000];

        Stopwatch sw1 = new Stopwatch();

        sw1.Start();

        for (int i = 0; i < 10000000; i++)
        {
            bitArray[i] = GetMod2(i);
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();

        var list = new List<bool>();
        for (int i = 0; i < 10000000; i++)
            list.Add(GetMod2(i));
        var boolArray2 = list.ToArray();

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();

        for (int i = 0; i < 10000000; i++)
        {
            bool nextVal = GetMod2(i);

            if (nextVal)
                bitArray[i] = true;
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();


        for (int i = 0; i < 10000000; i++)
        {
            boolArray[i] = GetMod2(i);
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();

        for (int i = 0; i < 10000000; i++)
        {
            boolArray[i] = GetRand(i);
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        Console.ReadLine();
    }

    static bool GetMod2(int i)
    {
        return (i % 2) == 1;
    }

    static bool GetRand(int i)
    {
        return new Random().Next(2) == 1;
    }
}
于 2012-07-23T09:18:37.153 に答える
0

今ここに面白い古いものがあります。@paulに触発されて、私はこれらのベンチマークテストを10,000,000ブール値で自分で実行しました。この質問へのコメントでの議論を考えると、結果（ミリ秒単位）は非常に驚くべきものです。

BitArray：517

BitArray + CopyTo（array）：536

リスト+ToArray（）：455

ブール配列：483

そして、本のためのなんとにぎわい！List<Bool>は毎回新しいレコードを挿入しているにもかかわらず、bool[]とBitArrayはすべてのレコードで初期化さfalseれており、値が必要な場所でのみ更新しましたがtrue、呼び出しList<bool>を含めても、一貫してトップになり.ToArray()ます。

実用的なアプリケーションが教科書の知識よりも優れているさらに別のケース、それはそうです... :)

于 2012-07-23T09:42:25.790 に答える