Optimierung von Algorithmen. - Seite 5

Neuer Kommentar
 
Mathemat:
Im Prinzip ja. Aber immer noch nicht mehr als O(n).
Nicht weniger :) mit einer guten Vorstellungskraft kann man eine exponentielle Abhängigkeit herstellen :)
 
Mathemat:

Es handelt sich nicht um ein Optimierungsproblem.

Die Suche nach einem Extremum ist immer ein Problem der Ordnung O(n), wobei n die Anzahl der Daten ist. Wie man das asymptotisch verschlimmern kann - ich habe keine Ahnung.

Der einfachste Algorithmus ist ArraySort(), der schnell genug eingebaut ist, aber für dieses Problem wahrscheinlich überflüssig ist.

Sie könnten sich etwas Rekursives einfallen lassen, das schneller wäre.

Wie lange dauert es, das Minimum zu finden und für wie viele Takte?

Ich habe die Statistiken in meinem ersten Beitrag genannt. Die Berechnung für 1.000.000 Takte steigt arithmetisch mit zunehmender Dauer. Für den Zeitraum 3 dauert die Berechnung also 0,54 Sekunden, für den Zeitraum 51 0,94 Sekunden und für den Zeitraum 99 1,59 Sekunden.

Dies ist schlimmer, weil die Schleife in der Schleife verwendet wird, was ein Fehler ist. Für die Periode 3 beträgt die Anzahl der Iterationen also 1 000 000 * (3-1/2) = 1 000 000, während sie für die Periode 99 1 000 000 * (99-1)/2 = 49 000 000 beträgt! Daher müssen wir den Algorithmus so umschreiben, dass die Anzahl der Iterationen nicht mit zunehmender Periode qualitativ ansteigt - dies ist ein reines Optimierungsproblem. Das ist es, was ich jetzt tue. Bislang habe ich dies geschrieben:

static void Up(Bars MyQuotes)
        {
            BitArray bits = new BitArray(MyQuotes.Count);
            double max = double.MinValue;
            int pperiod = (23 - 1) / 2;
            int bar = pperiod;
            int count = MyQuotes.Count - pperiod;
            //последняя позиция второго перебора.
            int pos = bar;
            while (bar < count)
            {
                for (int i = 1; i <= pperiod; i++)
                {
                    max = MyQuotes.High[bar - i] > MyQuotes.High[bar + i]
                              ? MyQuotes.High[bar - i]
                              : MyQuotes.High[bar + i];
                    pos = bar + i;
                    if(max > MyQuotes.High[bar])
                    {
                        //Начинаем с последнего бара
                        bar = pos;
                        break;
                    }
                    if(i == pperiod)
                    {
                        bits[bar + i] = true;
                        bar = pos;
                    }
                }
            }
        }

Um das Minimum zu finden, wird die entsprechende Funktion Down() in einem parallelen Thread gestartet. Wenn beide Funktionen beendet sind, werden ihre Ergebnisse in die allgemeine Liste geschrieben. Es geht ungefähr so.

 
C-4: Ich habe die Statistiken in meinem ersten Beitrag genannt. Die Berechnung für 1.000.000 Takte wächst arithmetisch mit zunehmender Dauer. So dauert die Berechnung für den Zeitraum 3 0,54 Sekunden, für den Zeitraum 51 0,94 Sekunden und für den Zeitraum 99 bereits 1,59 Sekunden.

Siehst du, du hast es falsch verstanden. Es ist nicht die Summe einer reichhaltigen Progression, C-4. Die Summe wächst quadratisch.

OCL ist unzweideutig.

 
Mathemat:

Der einfachste Algorithmus ist ArraySort(), der schnell genug ist, etwa O(n * ln( n ) ), aber für dieses Problem wahrscheinlich überflüssig ist.

Gedacht. Jede Sortierung ist inhärent langsamer als das Durchlaufen des gesamten Arrays mittels for. Denn es gibt eine Iteration, während arraysort bestenfalls Werte in jedem Teilfenster n sortiert, was wiederum Dutzende von Aktionen bedeutet.

Nein, Sie sollten dennoch anstreben, dass die Gesamtzahl der Iterationen qualitativ mit der Anzahl der Balken übereinstimmt.

Документация по MQL5: Доступ к таймсериям и индикаторам / Bars
Документация по MQL5: Доступ к таймсериям и индикаторам / Bars
  • www.mql5.com
Доступ к таймсериям и индикаторам / Bars - Документация по MQL5
 
Mathemat:

Siehst du, du hast es falsch verstanden. Es ist nicht die Summe einer reichhaltigen Progression, C-4. Die Summe wächst quadratisch.

OCL ist unzweideutig.

Wenn sie quadratisch ist, ist es noch schlimmer. Ohne Multithreading, so wie ich es verstehe, gibt es keinen Weg daran vorbei.
 

Die Bedingung für eine solche Extremsuche ist, gelinde gesagt, seltsam... Aber selbst dann ist es äußerst unvernünftig, eine Brute-Force-Suchmethode anzuwenden.

Ein klassischer ZigZag mit ExtDepth = n in einem Durchgang kommt einem sofort in den Sinn, wenn man eine leichte Anpassung an die aktuelle Bedingung vornimmt. OCL ist hier zu 100 % unnötig.

 
Ihr seid Feuer und Flamme. Ihr alle drei.
 
hrenfx:

Die Bedingung für eine solche Extremsuche ist, gelinde gesagt, seltsam... Aber selbst dann ist es äußerst unvernünftig, eine Brute-Force-Suchmethode anzuwenden.

Der klassische ZigZag mit ExtDepth = n in einem Durchgang kommt einem sofort in den Sinn, mit einer leichten Anpassung an die aktuellen Bedingungen. OCL ist hier zu 100 % unnötig.

Nun, im Prinzip brauche ich diese Extrema für einen Zick-Zack-Kurs. Welche Algorithmen sind dann besser zu verwenden? Gibt es einen effizienteren Code als den, den ich in der zweiten Fassung zitiert habe?
 
Sehen Sie sich die Single-Pass-ZigZags in CodeBase MT4 an - O(N).
 
TheXpert: Ihr seid Feuer und Flamme. Ihr alle drei.

Und warum? O(n) wird immer noch da sein, egal wie man es betrachtet.

Wenn alles andere fehlschlägt, versuchen Sie es mit OCL. Es gibt keine anderen Möglichkeiten, ohne dll-artige Perversionen in 5.

12345678910
Neuer Kommentar