Helfen Sie mir, dieses durchschnittliche Berechnungs-Snippet zu optimieren

Question

Ist es möglich, dieses Snippet zu beschleunigen?

firstSample und Letzteprobe ist der Teil des Arrays ich in dieser Iteration interessiert bin. Wenn dieses Intervall> 3000 erreicht, bekomme ich eine spürbare Verlangsamung. Das Array _average kann 6-60 Millionen int-Werte enthalten.

minY und maxY ist das Ergebnis, das ich verwende, nachdem diese Berechnung abgeschlossen ist.

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

Der Ausdruck _average [Beispiel] ist ein riesiger Engpass, da er eine Überprüfung impliziter Grenzen enthält jede Iteration. Verwenden Sie einen Zeiger auf das Array "_average" (und das unsichere Schlüsselwort). Vermeiden Sie dann den Aufruf von Funktionen, also entfernen Sie die Math.Min/Max-Aufrufe und überprüfen Sie dies selbst.

Ohne Compiler auf meine Hände jetzt, ich denke, das ist, wie es aussehen sollte:

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++; 
     } 
    } 
} 

Dann endlich, da „Probe“ ist eigentlich nicht in der Schleife verwendet, können Sie es zu einer Änderung Schleifenvariable, die bis auf Null zählt, sodass die Schleifenbeendigungsprüfung für eine Konstante (Null) anstelle einer Variablen ausgeführt wird.

Answer 2

Sie können für den Einsatz ist raschere als während oder Verwendung Parallel wenn Sie 3.5+ Rahmen

Answer 3

habe ich werde meinen Hals halten und sagen: Nein, ich glaube nicht, dass es eine Möglichkeit, um das wesentlich schneller zu machen (es sei denn, die Aufrufe von Min und Max würden helfen, aber ich erwarte, dass der Optimierer das erledigt).

Aber wenn Sie dies mehrfach mit denselben Daten tun, kann das Sortieren der Daten (oder der Datenblöcke, mit denen Sie jedes Mal arbeiten) den gesamten Prozess beschleunigen.

Es ist langsamer zu sortieren als das Minimum zu finden, aber es ist schneller zu sortieren, als das Minimum tausend Mal zu finden.

(Verzeih mir, wenn ich lehre Sie Eier hier zu saugen. 8-)

Answer 4

Für eine Sache, ich es als eine einfache for Schleife neu schreiben würde und vermeiden, dass ein Pascal-verrohrten lokale Variable verwenden, einschließlich mit mehr Umfang ein als es braucht:

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); 
} 

das ist nur ist es besser vertraut und konventionellen zu machen. Das JIT weiß über das Schleifen von Arrays in bestimmten Situationen, aber ich weiß nicht, ob es in diesem Fall helfen wird - es könnte nur überprüfen, firstSample >= -1 && lastSample < _average.length und dann Grenzen Checks zu beseitigen, aber ich weiß nicht, ob es tut. Nun Proben, die bereits in dem aktuellen Min-/Max-Bereich sind brauchen keine Nebenwirkungen haben, so lassen Sie sich von den Zuweisungen in diesem Fall loswerden:

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

ich nicht weiß, ob das nicht helfen - und ich vermute, dass es nicht, aber es kann ein Versuch wert sein ...

(Wie eine andere Antwort sagte, ist dies eine sehr einfache Operation zu parallelisieren - es sollte die Geschwindigkeit fast linear mit der CPU-Anzahl zu verbessern, dh 2 Prozessoren ~ = doppelt so schnell usw., abgesehen von den Cache-Fehlern usw.)

Answer 5

Sie könnten die for-Schleife versuchen, wie andere vorgeschlagen haben.

Es wird Profilierung benötigen, aber Sie könnten auch versuchen, Verfahren Anrufungen zu beseitigen und Verzweigung:

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

diese Änderungen vornehmen, nur wenn die Performance-Gewinn für Sie wirklich wichtig ist, da die Wartbarkeit des Codes nimmt mit ähnliche Konstrukte.

Answer 6

Unsicherer Code würde es Ihnen ermöglichen, Zeiger zu verwenden, um das Array zu indizieren, da der JIT-Compiler in diesem speziellen Fall die Überprüfung der Grenzen nicht entfernen kann. Schauen Sie sich here an, wie man das macht.

Sie könnten auch versuchen, die Min/Max-Anrufe selbst zu inlinen, aber es gibt gute Chancen, dass das JIT das bereits für Sie erledigt.

Schließlich ist es ziemlich einfach, dies mit den parallelen Erweiterungen von .NET 4 zu parallelisieren (Sie können das CTP für .NET 3.5 verwenden). Stellen Sie sicher, dass Sie nicht gleichzeitig von mehreren Threads auf die Min/Max-Werte schreiben. Sperren Sie es aber auch nicht, ich würde einen Min/Max-Wert pro Thread haben und einen finalen Vergleich zwischen den Min/Max-Werten jedes Threads/Tasks durchführen, wenn alle Threads erledigt sind.

Answer 7

Verwenden Sie eine for-Schleife, wie andere gesagt haben, aber richten Sie sie so aus, dass der Vergleich zu Null ist. Dies ist ein schneller Vergleich in den meisten Implementierungen.

Answer 8

Sie schrieb in einem Kommentar:

Ich Sortierung nicht. Nur das Finden der Max und Min eines Intervalls. Und das Intervall bewegt sich jedes 20ms

Es scheint, dass Sie tatsächlich ein bewegen Minimum und Maximum bewegt.

Ich glaube, dass dies effizienter durchgeführt werden kann, als jedes Mal das gesamte Intervall neu zu durchsuchen, unter der Annahme, dass sich das Intervall nur in eine Richtung bewegt und dass es signifikante Überlappungen zwischen aufeinander folgenden Intervallen gibt.

Eine Möglichkeit wäre, eine spezielle Warteschlange zu halten, wo jedes neue Element kopiert seinen Wert zu jedem Element in der Warteschlange, die größer ist (für die bewegliche Minimum), zB:

 
(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... 

Wenn Sie durch bewegen Mehr als 1 Element jedes Mal, können Sie zuerst das Minimum aller neuen Werte berechnen und das für das Überschreiben verwenden.

Der schlechteste Fall für diesen Algorithmus ist, wenn das Array absteigend sortiert wird, dann ist es O (nm), wobei m die Intervalllänge und n die Arraylänge ist. Am besten ist es, wenn es absteigend sortiert wird, dann ist es O (n). Für den Durchschnittsfall konstruiere ich O (n log (m)).

Answer 9

Sie können doppelte Vergleiche in Situationen, in denen Sie eine neue min finden, loswerden. Wenn Sie beide Min/Max auf den ersten Wert setzen, gibt es keinen Grund zu überprüfen, ob es auch ein neues Min ist. Dies ist im Grunde @ Skeets Code mit Initialisierung und einer zusätzlichen "else" -Anweisung.

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; 
     } 
    } 
}