Optimierung von Algorithmen. - Seite 4

Neuer Kommentar
 
MetaDriver:
Jetzt habe ich ein Problem. Ich brauche, um eine effiziente Sortierung von Arrays mit großen "Kosten" von Elementen Kopieren (dh Elemente, von denen große, "schwere" Strukturen, Klasse Objekte, lange Strings, etc.). Der gesunde Menschenverstand legt nahe, dass wir sie an Ort und Stelle zu verlassen, sondern sortieren stattdessen eine Art von Zeigern - Indizes von Zellen ihrer ursprünglichen Position. Hier ist das Zitat von https://www.mql5.com/ru/forum/6476#comment_178318Оставим so weit, mit ihren vielen aktuellen Aufgaben, und implementieren Sie es in mql5.

Alles ist schon vor uns gestohlen worden :)

Tabellenkalkulationen in MQL5

Die Eingabe sollte eine Kopie des zu sortierenden Arrays sein, die Kommentare sollten kommentiert und das Unnötige auskommentiert werden

//+------------------------------------------------------------------+
//void QuickSort(double &A[],int &r[],int from,int to)
void QuickSort(double &A[],int from,int to)
  {
   int i,j;//,itemp;
   double x,temp;
   if(from>=to)return;
   i=from;
   j=to;
   x=A[(from+to)>>1];
   while(i<=j)
     {
      while(A[i]<x)i++; 
      while(A[j]>x)j--;
      if(i<=j)
        {
         temp=A[i]; A[i]=A[j]; A[j]=temp;
         //itemp=r[i]; r[i]=r[j]; r[j]=itemp;
         i++;
         j--;
        }
     }
   QuickSort(A,from,j);
   //QuickSort(A,r,from,j);
   QuickSort(A,i,to);  
   //QuickSort(A,r,i,to);
  }
//+------------------------------------------------------------------+
 
Urain:

Alles ist schon vor uns gestohlen worden :)

Tabellenkalkulationen in MQL5

Die Eingabe sollte eine Kopie des zu sortierenden Arrays sein, die Kommentare sollten kommentiert und das Unnötige auskommentiert werden.

Du bist gemein! Du hast den Song ruiniert... Oder besser gesagt, ich habe es versucht. :)

// Es ist klar, dass es gute Näherungen gibt. Ich hätte genauso gut ein Beispiel aus der Standardbibliothek nehmen können. :)

Es gibt Muster. Und es gibt auch einige hervorragende Beispiele. Aber trotzdem. Hier ist es wichtig, alles so zu spezifizieren und zu debuggen, dass ein funktionsfähiges, eigenständig nutzbares Produkt entsteht. Außerdem (deshalb sende ich sie hier) - so schnell wie möglich. D.h. ich schlage vor, alle möglichen Leistungen bis auf Hundertstelprozent genau auszuschöpfen. :)

Dies ist die erste. Zweitens benötigen wir für Objekte die Anzahl der Index-Arrays gleich der Anzahl der Sortierkriterien, die im allgemeinen Fall mehrere sein können, + (vorzugsweise) Funktion des Einfügens in das nach mehreren Kriterien sortierte Array.

 
MetaDriver:

Du bist gemein! Du hast den Song ruiniert... Oder besser gesagt, Sie haben es versucht. :)

// Es ist klar, dass es gute Näherungen gibt. Ich hätte genauso gut ein Beispiel aus der Standardbibliothek nehmen können. :)

Es gibt Muster. Und sogar einige großartige. Aber trotzdem. Es ist wichtig, alles zu prüfen und zu debuggen, bis ein funktionsfähiges, eigenständiges Produkt entsteht. Und (deshalb sende ich es hierher) - die schnellste. D.h. ich schlage vor, alle möglichen Leistungen bis auf Hundertstelprozent genau auszuschöpfen. :)

Das ist der erste Punkt. Zweitens - für Objekte benötigen wir die Anzahl der Index-Arrays gleich der Anzahl der Sortierkriterien, die im Allgemeinen mehrere sein können, + (vorzugsweise) Funktion der Einfügung in sortiert nach mehreren Kriterien indizierten Array.

Dieselbe Antwort Tabellenkalkulationen in MQL5.

Es ist alles da. Unter einem konkreten Problem ist es möglich, unter Manipulation nicht Spalten, sondern Zeilen neu zu bilden, es gibt Spalten, für die es möglich ist, sie als verschiedene Typen zu deklarieren. Wenn der Tabellentyp derselbe ist, kann alles wiedergegeben werden.

 

Es wurde ein Inluder mit Sortierindizes für Basistypen erstellt.

bool ArrayIndexSort(const void &source[], int &index[], bool byDescending=true);

Die Standardsortierung ist "absteigend", um in aufsteigender Richtung zu sortieren, setzen Sie das Flag für die Sortierrichtung auf false.

Testergebnisse: // Indizierung von Arrays double[], int[], string[]; sequentiell : raw array, descending array, ascending array

2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     SArray[index[i]] = {MetaQuotes, Абырвалг, Газета, Колбаса, Компилятор, Молоко, Препроцессор, Яйцо}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     SArray[index[i]] = {Яйцо, Препроцессор, Молоко, Компилятор, Колбаса, Газета, Абырвалг, MetaQuotes}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     SArray[i]        = {Абырвалг, Газета, MetaQuotes, Колбаса, Молоко, Яйцо, Компилятор, Препроцессор}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     iarray[index[i]] = {89, 2393, 3742, 4772, 5098, 5364, 5560, 6226, 6758, 7029, 7245, 7540, 8097, 8195, 8908, 8945}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     iarray[index[i]] = {8945, 8908, 8195, 8097, 7540, 7245, 7029, 6758, 6226, 5560, 5364, 5098, 4772, 3742, 2393, 89}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     iarray[i]        = {8945, 7245, 8195, 5364, 8097, 5560, 5098, 3742, 89, 6758, 6226, 7029, 4772, 7540, 8908, 2393}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     darray[index[i]] = {0.29, 13.40, 16.11, 28.86, 31.05, 35.63, 38.71, 39.65, 47.79, 50.33, 50.40, 59.39, 63.31, 65.35, 70.65, 78.98}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     darray[index[i]] = {78.98, 70.65, 65.35, 63.31, 59.39, 50.40, 50.33, 47.79, 39.65, 38.71, 35.63, 31.05, 28.86, 16.11, 13.40, 0.29}
2012.04.08 05:04:46     IndexSort_Test (USDJPY,M30)     darray[i]        = {50.33, 47.79, 39.65, 70.65, 31.05, 16.11, 38.71, 78.98, 50.40, 35.63, 0.29, 63.31, 13.40, 59.39, 28.86, 65.35}

Bibliothek und Test im Anhänger.

Legen Sie den Indexer in den Ordner "MQL5\Include\Indexes\".

Dateien:
IndexSort.mqh  14 kb
IndexSort_Test.mq5  4 kb
 

Hier ist eine Beispielklasse für die Arbeit mit OCL. Natürlich sind einige Dinge unvollständig und umständlich, aber vielleicht findet sie ja jemand nützlich.

//——————————————————————————————————————————————————————————————————————————————
//|                                                            class   OCL.mqh |
//|                                                Copyright 2011, JQS aka Joo |
//|                                        https://www.mql5.com/ru/users/joo |
//——————————————————————————————————————————————————————————————————————————————
#property copyright "Copyright 2011, JQS aka Joo"
#property link      "https://www.mql5.com/ru/users/joo"
//——————————————————————————————————————————————————————————————————————————————
class OCL
{
public:
  bool              DeviceInfo(int DeviceID);
  bool              InitOCL   (int DeviceID,uint &Offset[],uint &Work[],int BuffCount,int ArgCount,string Source);
  bool              BuffInit  (int buffID,int size,int regime);
  bool              Execute   (int work_dim);
  void              DeinitOCL ();
  //---
  int               BuffID[]; // идентификаторы буферов
  //----------------------------------------------------------------------------
private:
  int               cl_ctx;   // идентификатор контекста
  int               cl_prg;   // идентификатор программы
  int               cl_krn;   // идентификатор ядра
  //---
  int               ArguID[]; // идентификаторы аргументов
  uint              offset[]; 
  uint              work  [];
};
//——————————————————————————————————————————————————————————————————————————————
bool OCL::DeviceInfo(int DeviceID)
{
  long DeviceCount=CLGetInfoInteger(0,CL_DEVICE_COUNT);
  if(DeviceCount<1)
    return(false);
  else
  {
    string s="Всего устройств OCL: "+(string)CLGetInfoInteger(0,CL_DEVICE_COUNT)+" - ";
    long DeviceType=CLGetInfoInteger(DeviceID,CL_DEVICE_TYPE);

    switch(DeviceType)
    {
    case CL_DEVICE_ACCELERATOR:
      s=s+"Используется спец.OpenCL ускоритель (например, IBM CELL Blade)";
      break;
    case CL_DEVICE_CPU:
      s=s+"Используется CPU";
      break;
    case CL_DEVICE_GPU:
      s=s+"Используется GPU";
      break;
    case CL_DEVICE_DEFAULT:
      s=s+"Устройство по умолчанию";
      break;
    case CL_DEVICE_CUSTOM:
      s=s+"Специализированный ускоритель, не поддерживает OpenCL";
      break;
    default:
      s=s+"Непонятное устройство, скорее всего это какое то устройство по умолчанию";
      break;
    }
    Print(s);
    return(true);
  }
}
//——————————————————————————————————————————————————————————————————————————————
bool OCL::InitOCL(int DeviceID,uint &Offset[],uint &Work[], int BuffCount,int ArgCount,string Source)
{
  ArrayResize(offset,ArraySize(Offset)); ArrayCopy(offset,Offset,0,0,WHOLE_ARRAY);
  ArrayResize(work,  ArraySize(Work));   ArrayCopy(work,  Work,  0,0,WHOLE_ARRAY);

  if((cl_ctx=CLContextCreate(DeviceID))==-1)
  {
    Print("OpenCL не найден: ",GetLastError());
    return(false);
  }
//----------------------------------------------------------------------------
// Создаем OpenCL программу из исходного кода
  if((cl_prg=CLProgramCreate(cl_ctx,Source))==-1)
  {
    CLContextFree(cl_ctx);
    Print("Ошибка созания OpenCL-программы");
    switch(GetLastError())
    {
    case ERR_OPENCL_INVALID_HANDLE:
      Print("Некоректный хендл на программу OpenCL");
      break;
    case ERR_INVALID_PARAMETER:
      Print("Некоректный строковой параметр");
      break;
    case ERR_OPENCL_TOO_LONG_KERNEL_NAME:
      Print("Имя кернела содержит более 127 символов");
      break;
    case ERR_OPENCL_KERNEL_CREATE:
      Print("Внутренняя ошибка при создании объекта OpenCL.");
      break;
    default: Print("Неопознанная ошибка.");
    }
    return(false);
  }
  //----------------------------------------------------------------------------
  //Создаем точку входа в программу OpenCL  
  if((cl_krn=CLKernelCreate(cl_prg,"Work"))==-1)
  {
    CLProgramFree(cl_prg);
    CLContextFree(cl_ctx);
    Print("Ошибка создания OpenCL-ядра");
    return(false);
  }
  //----------------------------------------------------------------------------
  ArrayResize(BuffID,BuffCount);
  ArrayResize(ArguID,ArgCount);
  return(true);
}
//——————————————————————————————————————————————————————————————————————————————
void OCL::DeinitOCL()
{
  for(int i=0;i<ArraySize(BuffID);i++)
    CLBufferFree(BuffID[i]);

  CLKernelFree (cl_krn);
  CLProgramFree(cl_prg);
  CLContextFree(cl_ctx);
}
//——————————————————————————————————————————————————————————————————————————————
bool OCL::Execute(int work_dim)
{
  if(!CLExecute(cl_krn,work_dim,offset,work))
  {
    Print("Ошибка при расчете в OpenCL");
    return(false);
  }
  return(true);
}
//——————————————————————————————————————————————————————————————————————————————
bool OCL::BuffInit(int buffID,int size,int regime)
{
  if(buffID>=ArraySize(BuffID))
    return(false);

  BuffID[buffID]=CLBufferCreate(cl_ctx,size,regime);
  if(BuffID[buffID]==-1)
  {
    Print("OpenCL buffer create failed");
    switch(GetLastError())
    {
    case ERR_OPENCL_INVALID_HANDLE:
      Print("Нкоректный хендл на контекст OpenCL");
      break;
    case ERR_NOT_ENOUGH_MEMORY:
      Print("Недостаточно памяти");
      break;
    case ERR_OPENCL_BUFFER_CREATE:
      Print("Внутренняя ошибка создания буфера");
      break;
    default: Print("Неопознанная ошибка.");
    }
    return(false);
  }
  //Выставляем буфер OpenCL в качестве параметра функции OpenCL
  if(!CLSetKernelArgMem(cl_krn,buffID,BuffID[buffID]))
    return(false);
  return(true);
}
//——————————————————————————————————————————————————————————————————————————————


Ich habe die Initialisierung ein wenig überarbeitet, jetzt kann man mehrdimensionale Berechnungen durchführen.

 
Das ist gut, das gefällt mir. Sollte ich meinen C-ähnlichen Code überarbeiten?
 

Tolles Thema!

Gerade stand ich vor einem Optimierungsproblem mit einem Algorithmus zum Auffinden eines Preisextremums (Minimum). Die Bedingungen sind wie folgt: Es gibt einen Balken, n Balken links und rechts davon liegen unter (über) seinem Maximum:

n ist ein freier, willkürlich gewählter Wert. Die Periode n ist immer ungerade, da die Summe der beiden Balken rechts und links immer eine gerade Zahl ist, zu der der mittlere Balken des eigentlichen Preisextremums addiert wird.

Ich habe nicht viel über die erste Version des Algorithmus nachgedacht und den offensichtlichsten Code geschrieben. Jetzt schreibe ich es in C# mit WealthLab-Plattform, aber ich denke, Sie können leicht verstehen, die Essenz der problematischen Algorithmus, hier ist der problematischste Teil davon:

//Перебираем все бары
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;
   }
}

Das ganze Problem liegt in der zweiten Schleife. Es behandelt gleichzeitig den linken und den rechten Zweig eines potenziellen Extremwerts und durchläuft daher nur (N - 1)/2 Balken, aber das ist nicht genug. Messungen zeigen, dass der Zeitaufwand für die Identifizierung eines Extremums in einer arithmetischen Progression von der Periode N abhängt, was sehr, sehr schlecht ist:

N         Time
3       00:00:00.5460312
4       00:00:00.4720270
5       00:00:00.4820276
6       00:00:00.4250243
7       00:00:00.4410252
8       00:00:00.4350249
9       00:00:00.4300246
10      00:00:00.4380251
11      00:00:00.4520258
12      00:00:00.4420253
13      00:00:00.4500257
14      00:00:00.4640266
15      00:00:00.5100291
16      00:00:00.4950284
17      00:00:00.5200297
18      00:00:00.5110292
19      00:00:00.5090291
20      00:00:00.5690326
21      00:00:00.5320304
22      00:00:00.5560318
23      00:00:00.5750329
24      00:00:00.5850335
25      00:00:00.6140351
26      00:00:00.6120350
27      00:00:00.6160352
28      00:00:00.6510373
29      00:00:00.6510372
30      00:00:00.6770387
31      00:00:00.6900395
32      00:00:00.7040403
33      00:00:00.7000400
34      00:00:00.7190411
35      00:00:00.7320419
36      00:00:00.7510430
37      00:00:00.7510429
38      00:00:00.8290474
39      00:00:00.7760444
40      00:00:00.8080463
41      00:00:00.7990457
42      00:00:00.8240471
43      00:00:00.8460484
44      00:00:00.8690497
45      00:00:00.8680496
46      00:00:00.9120522
47      00:00:00.8870507
48      00:00:00.9520545
49      00:00:00.9230528
50      00:00:00.9430539
51      00:00:00.9460541
52      00:00:00.9590549
53      00:00:00.9750558
54      00:00:00.9920567
55      00:00:01.0010573
56      00:00:01.0440597
57      00:00:01.0400595
58      00:00:01.0610607
59      00:00:01.0610606
60      00:00:01.0860622
61      00:00:01.0730613
62      00:00:01.1170639
63      00:00:01.1400652
64      00:00:01.1370651
65      00:00:01.1190640
66      00:00:01.1960684
67      00:00:01.1740671
68      00:00:01.2110693
69      00:00:01.2490715
70      00:00:01.3010744
71      00:00:01.2750730
72      00:00:01.3090748
73      00:00:01.3000744
74      00:00:01.3060747
75      00:00:01.3610779
76      00:00:01.3740785
77      00:00:01.4190812
78      00:00:01.3500772
79      00:00:01.3350764
80      00:00:01.3530774
81      00:00:01.4690840
82      00:00:01.4270816
83      00:00:01.3870794
84      00:00:01.4250815
85      00:00:01.4250815
86      00:00:01.4500829
87      00:00:01.4600835
88      00:00:01.4630837
89      00:00:01.4500830
90      00:00:01.5060861
91      00:00:01.4930854
92      00:00:01.5340878
93      00:00:01.5620893
94      00:00:01.5470885
95      00:00:01.5450884
96      00:00:01.5730899
97      00:00:01.5640895
98      00:00:01.5840906
99      00:00:01.5970914

Wenn man die Perioden durchprobiert, braucht man die Zeit, um die arithmetische Progression zu summieren, und das ist ein sehr großer Wert.

Eine mögliche Lösung besteht darin, eine zusätzliche Variable einzuführen. Denn wenn ein Extremum identifiziert ist, ist garantiert, dass es rechts davon für (N - 1)/2 keinen Balken gibt, so dass ein neues Extremum identifiziert werden kann, das mit bar: current_bar + (N - 1)/2 beginnt. Allerdings müssen neben den Minima auch die Extrema ermittelt werden, und ein neues Minimum kann vor current_bar + (N - 1)/2 gefunden werden. Daher muss die Suche nach Extrema und Minima auf zwei Durchgänge aufgeteilt werden, was jeden Leistungsgewinn zunichte macht. Wir können zwei Durchläufe leicht in zwei Threads aufteilen, die gleichzeitig auf zwei Kernen in C# verarbeitet werden, aber ich würde gerne den optimalen Algorithmus finden und ihn zunächst optimieren. Ich warte auf die Hilfe von Experten.

 
C-4: Ich bin gerade mit dem Optimierungsproblem des Algorithmus für die Suche nach einem Preisextremum (Minimum) konfrontiert.

Es handelt sich nicht um ein Optimierungsproblem.

Wenn man die Perioden durchprobiert, erhält man die Summe der arithmetischen Progression, und das ist ein sehr großer Wert.

Die Suche nach einem Extremum scheint ein Problem der Größenordnung O(n) zu sein, wobei n die Anzahl der Daten ist. Wie man das asymptotisch verschlechtern kann, d.h. O(n^2), kann ich mir gar nicht vorstellen. Oder Sie verwechseln die Begriffe.

Der einfachste Algorithmus ist ArraySort(), der schnell genug ist, etwa O(n * ln( n ) ), 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? Nun, ich glaube nicht, dass Sie bei 100 Takten maximal anderthalb Sekunden suchen.

 
Mathemat:

Der einfachste Algorithmus ist ArraySort(), die eingebaute Sortierung ist schnell genug, aber für diese Aufgabe wahrscheinlich überflüssig.

Die beste Sortierung ist O(n*log(n)). Genau genommen überflüssig.

Wir könnten uns etwas Rekursives einfallen lassen, das schneller wäre.

Langsamer. Rekursion ist meistens böse. Rekursiv? Dies ist wahrscheinlich ein Fall, bei dem es egal ist, wie man es macht, die Geschwindigkeit ist ungefähr gleich.

Nach Code:

//Перебираем все бары
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;
   }
}

Die Zyklen für min und max müssen explizit getrennt werden. Und beenden Sie die Schleife sofort, wenn sie fehlschlägt.

 
TheXpert: Dies ist wahrscheinlich der Fall, bei dem die Geschwindigkeit, egal wie man es macht, ungefähr gleich ist.

Im Prinzip ja. Aber immer noch nicht mehr als O(n).

OCL würde hier helfen. Die Asymptotik bleibt natürlich dieselbe. Aber die Geschwindigkeit könnte durchaus um das Hundertfache erhöht werden.

12345678910
Neuer Kommentar
Grund der Beschwerde: