C＃サブ配列から最大double値を見つけるより高速なメソッドが必要

Question

サブ配列から最大double値を見つけるには、より高速なメソッドが必要です。

これは、私は今それを行う方法です。

static double FindMax(double[] x, int startIndex, int endIndex) 
{ 
    int i = startIndex; 
    double max = x[i++]; 
    double value; 
    while(i <= endIndex) 
    { 
     value = x[i++]; 
     if (value > max) max = value; 
    } 
    return max; 
} 

しかし、それは少し遅いです。私はより速い方法が必要です。任意のヒント？

Answer 1

それはあなたが持っている要素の量によって異なりますが、あなたのアルゴリズムが他のものより速く実行されるシナリオがあります。たとえば、HeapSortを使用する場合、ソートの順序はO（n log n）であり、最大での選択はO（1）です。今度は2番目の最大値が必要です。最大値をブール値でマークし、同じコレクションに対してHeaportを実行して、マークされていない値だけを検索することもできます。順序は同じです。参考までにここに行くことができます https://en.wikipedia.org/wiki/Heapsort

Answer 2

コードを参照してくださいをご覧ください。私が知る限りでは、組み込み配列の境界チェックを超えることができます。何がより高速になるのでしょうか。

編集： This questionは面白いかもしれない答えがあります。

Answer 3

ローレルwhileまたはforは、C＃でシングルスレッドコードを使用することができる最も速いバージョンです（バウンドチェックを避けることによって、unsafeがパフォーマンスを向上させる可能性があります）。その上にあるLINQは物事を遅らせるだけです。

最大値はO（n）です。これより速く必要な場合は、情報を格納するために他のデータ構造を使用する必要があります。ソートされた配列は最も速くなります（最大/最小の場合はO（1））が、挿入、ヒープまたはソートのために多くのコストがかかります。

また、配列のすべての操作で配列の最大値を追跡することもできます。 "max"を常に最新の状態に保つために、配列をラップしてすべての操作に少しずつ支払う必要がありますが、最大でO（1）を得て、他のすべての操作を同じパフォーマンスで配列に保持して保存します注文。

Answer 4

私はソートされていない配列の計算上の複雑さはO（n）だと思います。

あなたは余分な複雑さとメモリ消費量を気にしない場合は配列（1ソート、ソートされていないもの）の2つのコピーを維持することができます。 （また、2番目の配列を作成するためのコストが「前に出ます」）。

他の人が示したように、これを並列化することもできます。計算の複雑さは変わらないが、パフォーマンスが向上する可能性がある。 "could"という言葉に注意してください - 並列化は通常、あまりにもオーバーヘッドを招きます。ここで

Answer 5

はより速く実行し、あなたのコードを少し変更したバージョンは、あなたがC＃で、安全でない/ポインタ演算を試すことができます...（これはより速く、安全でない/ポインタコードよりも）

static double FindMaxFastest(double[] x, int startIndex, int endIndex) 
{ 
    int i = startIndex; 
    double max = double.MinValue; 
    do 
    { 
     if (max < x[i]) 
      max = x[i]; 
    } while (i++ < endIndex); 
    return max; 
} 

ですが、それは勝ちましたあなたが期待するブーストを得ることはできません。 unsafeは、コンパイラとランタイムが内部最適化のいくつかを行うことができないため、パフォーマンスを低下させる可能性もあります。

static unsafe double FixMaxFixed(double[] doubles, int startIndex, int endIndex) 
{ 
    var i = startIndex; 
    double max = double.MinValue; 
    fixed (double* p = doubles) 
    { 
     do 
     { 
      if (max < *(p + i)) 
       max = *(p + i); 
     } while (i++ < endIndex); 
    } 
    return max; 
} 

...ここで私が使用したテストハーネスは...セットが降順である場合

static void Main() 
{ 
    var rnd = new Random(); 
    var set = Enumerable.Range(0, 10000000).Select(i => rnd.NextDouble() * 100).ToArray(); 
    var s = 50; 
    var e = 1000000; 

    var sw = new Stopwatch(); 
    var r = new[] { new List<long>(), new List<long>(), new List<long>() }; 

    for (var i = 0; i < 1000; i++) 
    { 
     sw.Restart(); 
     FixMaxFixed(set, s, e); 
     sw.Stop(); 
     r[0].Add(sw.ElapsedTicks); 

     sw.Restart(); 
     FindMax(set, s, e); 
     sw.Stop(); 
     r[1].Add(sw.ElapsedTicks); 

     sw.Restart(); 
     FindMaxFastest(set, s, e); 
     sw.Stop(); 
     r[2].Add(sw.ElapsedTicks); 
    } 

    //5721.785 6098.866 5432.225 
    Console.WriteLine(string.Join(" ", r.Select(i => i.Average()))); 
    Console.Read(); 
} 

... Duff's deviceを使用すると、実際の性能（unrolling your loop）を増やすことができます...

（これが私の最初の例の50％の時間で実行されます。あなただけのアイデアを探しているなら...、あなたはそれが昇順であれば、時間の75％）

static double FindMaxDuff(double[] x, int startIndex, int endIndex) 
{ 
    double max = x[startIndex]; 

    switch ((endIndex - startIndex) % 10) 
    { 
     case 0: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 9; 
     case 9: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 8; 
     case 8: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 7; 
     case 7: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 6; 
     case 6: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 5; 
     case 5: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 4; 
     case 4: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 3; 
     case 3: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 2; 
     case 2: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      goto case 1; 
     case 1: 
      if (max < x[startIndex++]) max = x[startIndex]; 
      break; 
    } 

    do 
    { 
     if (max < x[startIndex + 1]) max = x[startIndex + 1]; 
     if (max < x[startIndex + 2]) max = x[startIndex + 2]; 
     if (max < x[startIndex + 3]) max = x[startIndex + 3]; 
     if (max < x[startIndex + 4]) max = x[startIndex + 4]; 
     if (max < x[startIndex + 5]) max = x[startIndex + 5]; 
     if (max < x[startIndex + 6]) max = x[startIndex + 6]; 
     if (max < x[startIndex + 7]) max = x[startIndex + 7]; 
     if (max < x[startIndex + 8]) max = x[startIndex + 8]; 
     if (max < x[startIndex + 9]) max = x[startIndex + 9]; 
     if (max < x[startIndex + 10]) max = x[startIndex + 10]; 
    } while ((startIndex += 10) < endIndex); 

    return max; 
}