この平均計算スニペットを最適化するのに役立ちます

Question

このスニペットのスピードアップは可能ですか？

firstSampleとlastSample私はこの反復に興味があるアレイの一部です。この間隔が3000を超えると、私は目立って減速します。 _average配列には、6~600万のint値を含めることができます。

minYおよびmaxYは、この計算が完了した後に使用する結果です。あなたが使用することができます

int minY = Int32.MaxValue; 
int maxY = Int32.MinValue; 
int Y = 0; 
int sample = firstSample + 1; 

while (sample <= lastSample) 
{ 
     Y = _average[sample]; 
     minY = Math.Min(Y, minY); 
     maxY = Math.Max(Y, maxY); 
     sample++; 
} 

Answer 1

_average [サンプル]式は暗黙的な境界チェックを含んでいるため、大きなボトルネックになります各反復。 "_average"配列へのポインター（および安全でないキーワード）を使用します。それで、関数を呼び出すのは避けてください。Math.Min/Max呼び出しを取り除き、自分でチェックしてください。今私の手で任意のコンパイラなし

、私は、これは、それがどのように見えるべきかだと思う：

unsafe 
{ 
    fixed (int* paverage = _average) 
    { 
     int* p = paverage + firstSample + 1; 
     for (int sample = firstSample+1 ; sample <= lastSample ; sample++) 
     { 
      if (*p < minY) 
       minY = *p; 
      if (*p > maxY) 
       maxY = *p; 
      p++; 
     } 
    } 
} 

「サンプル」は、実際にループで使用されていないため、最終的に、あなたはそれを変更することができますloop変数はゼロまでカウントダウンするので、ループ終了チェックは変数ではなく定数（ゼロ）に対して行われます。

Answer 2

あなたは3.5+枠組み

Answer 3

を持っている場合、私は私の首を突き出すといいえ、私はどのような方法がないと思うと言うつもりですしばらくまたは使用パラレルよりもスピーディーです（MinとMaxへの呼び出しをインライン展開するのが助けになるのでなければ、オプティマイザがそれを処理すると思います）。

しかし、同じデータに対してこれを複数回実行している場合、データ（またはその都度処理しているデータのまとまり）を並べ替えることで、プロセス全体をより迅速に行うことができます。

最小値よりもソートが遅くなりますが、最小値を1000回以上見つけるのは一度ソートする方が速いです。

（私はここに卵を吸うためにあなたを教えています。8私を許して）

Answer 4

一つには、私はシンプルforループとしてそれを書き換え、パスカル・同棲ローカル変数の使用を避ける、などの思い必要な範囲を超えたもの：

int minY = int.MaxValue; 
int maxY = int.MinValue; 

for (int sample = firstSample + 1; sample <= lastSample; sample++) 
{ 
    int y = _average[sample]; 
    minY = Math.Min(y, minY); 
    maxY = Math.Max(y, maxY); 
} 

これは、それをもっと慣れ親しんで従来のものにするためのものです。 JITは特定の状況で配列をループすることを知っていますが、この場合に役立つかどうかは分かりません。にチェックして、firstSample >= -1 && lastSample < _average.lengthをチェックして境界チェックを削除します。さて、現在の最小/最大範囲内に既にあるサンプルは、任意の副作用を必要とし、その者は、その場合には割り当てを取り除くことはできません。私はそれが役立つかどうかわかりません

for (int sample = firstSample + 1; sample <= lastSample; sample++) 
{ 
    int y = _average[sample]; 
    if (y < minY) 
    { 
     minY = y; 
    } 
    if (y > maxY) 
    { 
     maxY = y; 
    } 
} 

- それはないと思うが、それは試してみる価値があるかもしれないが...。

（別の答えとして、これは並列化するのは非常に簡単な操作である。 2プロセッサ〜= 2倍の速さなど、キャッシュミスなどを除いて）

Answer 5

他の人が提案しているように、forループを試してみることもできます。

これは、プロファイリングをする必要がありますが、あなたはまた、メソッド呼び出しと分岐を排除することを試みることができる：コードの保守がして低下するので、パフォーマンスの向上は、あなたのために本当に重要である場合にのみ、これらの変更を行い

Y = _average[sample]; 
    minY = minY + ((Y-minY) & (Y-minY)>>31); 
    maxY = maxX - ((X-maxX) & (X-maxX)>>31); 
    sample++; 

類似の構築物。

Answer 6

安全でないコードでは、この特定のケースでJITコンパイラが境界チェックを削除できないため、ポインタを使用して配列のインデックスを作成できます。それを行うにはhereを見てください。

また、Min/Max呼び出しをインライン展開することもできますが、JITが既にそれを実行している可能性があります。

最後に、これを.NET 4のParallel Extensions（CTP for .NET 3.5を使用できます）と並列化するのはかなり簡単です。同時に複数のスレッドからmin/max値に書き込まないようにしてください。スレッドをロックしないでください。スレッドごとに最小値/最大値があり、すべてのスレッドが完了したときに各スレッド/タスクの最小値/最大値の最終比較を行います。

Answer 7

他の人が言っているようにforループを使用しますが、比較がゼロになるように設定してください。これは、ほとんどの実装で、より高速な比較です。

Answer 8

あなたはコメントで次のように書いた：

私は並べ替えていませんよ。区間の最大値と最小値を見つけるだけです。間隔は20msごと

を移動し、あなたが実際にが最大を動かす最小とを動かしたいようです。

これは、インターバルが一方向にのみ移動し、後続のインターバルが重複していると仮定すると、毎回インターバル全体を再探索するよりも効率的に行うことができると思います。

一つの方法は、例えば、（移動最小のための）大きい、キュー内のすべての要素にすべての新しい要素をコピーし、その値の特別なキューを、維持するために、次のようになります。

 
(5 8 4 7 7 0 7 0 4 4 3 4 0 9 7 9 5 4 2 0) ; this is the array 
(4 4 4 4) ; the interval is 4 elements long, and initialized to the minimum 
      ; of the first 4 elements 
    (4 4 4 7) ; next step, note that the current minimum is always the first element 
    (4 7 7 0) ; now something happens, as 0 is smaller than the value before 
    (4 7 0 0) ; there are still smaller values ... 
    (4 0 0 0) ; and still ... 
    (0 0 0 0) ; done for this iteration 
     (0 0 0 7) 
     (0 0 0 0) ; the 0 again overwrites the fatties before 
      (0 0 0 4) 
      (0 0 4 4) 
       (0 3 3 3) ; the 3 is smaller than the 4s before, 
         ; note that overwriting can be cut short as soon as a 
         ; value not bigger than the new is found 
       (3 3 3 4) 
        (0 0 0 0) ; and so on... 

あなたがで移動した場合毎回1つ以上の要素がある場合は、最初にすべての新しい値の最小値を計算し、それをバックオーバラップに使用することができます。

このアルゴリズムの最悪のケースは、配列が降順でソートされている場合です。次に、O（nm）です（mは間隔の長さ、nは配列の長さです）。最良のケースは、降順でソートされたとき、それはO（n）です。平均の場合、私はO（n log（m））を求める。

Answer 9

新しい分が見つかった場合は、重複した比較を取り除くことができます。最小値/最大値の両方を最初の値に設定した場合、新しい最小値が見つかった場合は、それが新しい最大値でもあるかどうかを確認する必要はありません。これは基本的に初期化を伴う@ Skeetのコードと追加の 'else'ステートメントです。

int firstIndex = firstSample + 1; 
if (firstIndex <= lastSample) 
{ 
    minY = _average[firstIndex]; 
    maxY = minY; 

    for (int sample = firstIndex + 1; sample <= lastSample; sample++) 
    { 
     int y = _average[sample]; 
     if (y < minY) 
     { 
      minY = y; 
     } 
     else if (y > maxY) 
     { 
      maxY = y; 
     } 
    } 
}