Optimierung von Algorithmen. - Seite 6

Neuer Kommentar
 
C-4:

Das ganze Problem liegt im zweiten Zyklus. Es behandelt gleichzeitig linke und rechte Abzweigungen vom potentiellen Extremum und geht daher nur durch (N - 1)/2 Balken, aber das ist nicht genug. Messungen zeigen, dass die Zeit, die für die Suche nach einem Extremum in einer arithmetischen Progression aufgewendet wird, von der Periode N abhängt, was sehr, sehr schlecht ist:

Es fehlt mindestens eine Pause:

//Перебираем все бары
for (int bar = 0; bar < MyQuotes.Count; bar++)
{
   //Подготовка данных
   ...
   int pperiod = (N - 1)/2;
   //Перебираем бары относительно потенциального экстремума
   for (int i = 1; i <= pperiod; i++)
   {
      if (MyQuotes.High[bar - i] > MyQuotes.High[bar] ||
         MyQuotes.High[bar + i] > MyQuotes.High[bar])
         up = false;
      if (MyQuotes.Low[bar - i] < MyQuotes.Low[bar] ||
         MyQuotes.Low[bar + i] < MyQuotes.Low[bar])
         down = false;

      if ( !up && !down ) break; // А зачем искать дальше?
   }
}

Noch besser ist es, wenn Sie den oberen und unteren Teil wirklich aufteilen und nach einer erfolglosen Prüfung sofort aufhören.

 
Mathemat:

Wenn alles andere fehlschlägt, versuchen Sie es mit OCL.

Es wird keinen großen Unterschied machen.
 
TheXpert:
Es wird keinen großen Unterschied machen.
Ja, das wird sie. Dies liegt daran, dass die Aufgabe nicht sequentiell ausgeführt werden muss. Der gesamte Balkenverlauf kann in k Segmente unterteilt werden, von denen jedes von einem anderen CPU-Kern verarbeitet wird. Ich kenne die Funktionsweise von OCL nicht, aber ich denke, das Prinzip ist hier dasselbe. Eine weitere Besonderheit des Zick-Zack-Kurses ist, dass er sequentiell ist, d. h. jede neue Zeile beginnt am Ende der vorherigen, was die Aufteilung in Teilaufgaben extrem schwierig oder sogar unmöglich macht.
 
komposter:

Es fehlt mindestens eine Pause:

Noch besser ist es, wenn Sie oben und unten wirklich trennen und nach einer erfolglosen Kontrolle sofort aufhören.

Auch hier führt die Trennung von oben und unten zu zwei Durchgängen für. Dadurch verdoppelt sich die Suchzeit. Die Trennung an sich bringt ohne Multithreading keinen Leistungsgewinn, insbesondere bei kleinen n.
 

Dennoch ist OCL (oder Parallelisierung im allgemeinen Sinne) keine algorithmische Optimierung, sondern eher eine technische.

Ich bezweifle, dass es in Ihrem Fall notwendig ist, die schnellste O(N)-Variante der Problemlösung zu parallelisieren.

 
C-4:
Das wird er.

Kein Blabla? Zeigen Sie es mir.

Also, viel Glück. Mit der Optimierung eines Algorithmus, dessen Komplexität linear vom Wert eines Parameters abhängt, haben Sie wahrscheinlich nichts zu tun.

 
TheXpert:

Kein Blabla? Zeigen Sie es mir.

Wie auch immer, viel Glück. Diskutieren Sie die Optimierung eines Algorithmus, dessen Komplexität linear vom Wert eines Parameters abhängt - Sie haben wirklich nichts zu tun.

OK, ich werde den Algorithmus vervollständigen und die Ergebnisse der Parallelisierung im Studio veröffentlichen.

hrenfx:

Dennoch ist OCL (oder Parallelisierung im allgemeinen Sinne) keine algorithmische Optimierung - es ist eher eine technische.

Ich bezweifle, dass es in Ihrem Fall notwendig ist, die schnellste O(N)-Variante zu parallelisieren.

Wie soll ich es sagen? Jede Parallelisierung ist immer eine ernsthafte Komplikation von Algorithmen. Und wenn man einen Algorithmus mit linearer Abhängigkeit von der Datenmenge nicht parallelisieren kann, was kann man dann noch parallelisieren?

Kurz gesagt, ich werde den Algorithmus neu schreiben und sehen, was er bringt.

 
C-4:
Auch hier führt die Trennung von Ober- und Unterseite zu zwei Durchgängen für. Dadurch verdoppelt sich die Suchzeit. Die Trennung an sich bringt ohne Multithreading keinen Leistungsgewinn, insbesondere bei kleinen n.

Wie können Sie so sicher sein?

Meine Überprüfung ergibt etwas anderes:

01:29:25 SpeedTest EURUSD,M15 inputs: Interations=10000; pperiod=10;

01:29:25 SpeedTest EURUSD,M15: Anzahl der Balken = 3780

01:30:46 SpeedTest EURUSD,M15: Originalfunktion: 81.558 sec, Extrema: 131 / 121

01:31:10 SpeedTest EURUSD,M15: Mit meiner Bearbeitung (Pause): 23.291 sec, Extrema: 131 / 121

01:31:27 SpeedTest EURUSD,M15: Mit meiner Pause (Pause): 17.565 sec, Extrema: 131 / 121

Im Anhang finden Sie ein mq4-Skript.

Dateien:
SpeedTest.mq4  4 kb
 

Ein weiterer Test, um das Bild zu vervollständigen:

01:38:56 SpeedTest EURUSD,M1 inputs: Interations=1000; pperiod=100;

01:38:56 SpeedTest EURUSD,M1: Anzahl der Balken = 33896

01:50:19 SpeedTest EURUSD,M1: Originalfunktion: 683.565 sec, Extrema: 121 / 127

01:50:54 SpeedTest EURUSD,M1: Mit meiner Bearbeitung (Pause): 34.383 sec, Extrema: 121 / 127

01:51:16 SpeedTest EURUSD,M1: Mit meiner Pause (Pause): 22.714 sec, Extrema: 121 / 127

 
komposter:
C.T.D. schrieb genau das in seinem ersten Beitrag.
12345678910
Neuer Kommentar