Ottimizzazione degli algoritmi. - pagina 4

Nuovo commento
 
MetaDriver:
Ora ho un problema. Ho bisogno di rendere efficiente l'ordinamento degli array con grande "costo" della copia degli elementi (cioè elementi di cui sono grandi, strutture "pesanti", oggetti di classe, lunghe stringhe, ecc. Il senso comune suggerisce che dovremmo lasciarli sul posto, ma ordinare invece una sorta di puntatori - indici di celle della loro posizione originale. Ecco la citazione di https://www.mql5.com/ru/forum/6476#comment_178318Оставим finora, con i loro molti compiti attuali, e implementarlo in mql5.

Tutto è già stato rubato prima di noi :)

Fogli di calcolo in MQL5

L'input dovrebbe essere una copia dell'array da ordinare, i commenti dovrebbero essere annotati e il non necessario dovrebbe essere commentato

//+------------------------------------------------------------------+
//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:

Tutto è già stato rubato prima di noi :)

Fogli di calcolo in MQL5

L'input dovrebbe essere una copia dell'array da ordinare, i commenti dovrebbero essere annotati e il superfluo commentato.

Sei cattivo! Hai rovinato la canzone... O meglio - ci ha provato. :)

// È chiaro che ci sono buone approssimazioni. Potrei anche aver preso un campione dalla libreria standard. :)

Ci sono degli schemi. E ce ne sono anche di eccellenti. Ma comunque. Qui è importante registrare e fare il debug di tutto fino a una condizione di lavoro di un prodotto utilizzabile separatamente. Inoltre (perché lo sto inviando qui) - il più velocemente possibile. Cioè suggerisco di spremere tutte le prestazioni possibili fino ai centesimi di percentuale inclusi. :)

Questo è il primo. In secondo luogo, per gli oggetti abbiamo bisogno di un numero di array di indici pari al numero di criteri di ordinamento, che nel caso generale possono essere diversi, + (preferibilmente) la funzione di inserimento nell'array indicizzato secondo diversi criteri.

 
MetaDriver:

Sei cattivo! Hai rovinato la canzone... O meglio, ci hai provato. :)

// È chiaro che ci sono buone approssimazioni. Potrei anche aver preso un campione dalla libreria standard. :)

Ci sono dei campioni. E anche alcuni grandi. Ma comunque. È importante controllare e fare il debug di tutto fino a una condizione di lavoro di un prodotto utilizzabile separatamente. E (perché lo sto inviando qui) - il più veloce. Cioè suggerisco di spremere tutte le prestazioni possibili fino ai centesimi di percentuale inclusi. :)

Questa è la prima cosa. Secondo - per gli oggetti abbiamo bisogno di un numero di array di indici pari al numero di criteri di ordinamento, che in generale possono essere diversi, + (preferibilmente) la funzione di inserimento nell'array indicizzato secondo diversi criteri.

Stessa risposta Fogli di calcolo in MQL5.

È tutto lì. Sotto un problema concreto, è possibile rifare sotto manipolazione non colonne ma righe, ci sono colonne fatte per è possibile dichiararle come tipi diversi. Se il tipo di tabella è lo stesso, tutto può essere riprodotto.

 

Fatto un inluder con indici di ordinamento per i tipi di base.

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

L'ordinamento predefinito è "discendente", per ordinare in senso ascendente, impostare il flag di direzione dell'ordinamento su false.

Risultati del test: // indicizzazione degli array double[], int[], string[]; sequenzialmente: array grezzo, array discendente, array ascendente

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}

Biblioteca e test nel rimorchio.

Metti l'indicizzatore nella cartella "MQL5\Include\Indexes\".

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

Ecco un esempio di classe per lavorare con OCL. Naturalmente, alcune cose sono incomplete e scomode, ma forse qualcuno lo troverà utile.

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


Ho rielaborato un po' l'inizializzazione, ora è possibile eseguire calcoli multidimensionali.

 
Questo è buono, mi piace. Devo rifare il mio codice in stile C?
 

Grande argomento!

Proprio ora ho affrontato un problema di ottimizzazione con un algoritmo per trovare un estremo (minimo) di prezzo. Le condizioni sono le seguenti: c'è una barra, n barre a sinistra e a destra della quale sono sotto (sopra) il suo massimo:

n è un valore libero scelto arbitrariamente. Il periodo n è sempre dispari, perché la somma delle due barre a destra e a sinistra sarà sempre un numero pari a cui si aggiunge la barra centrale dell'estremo del prezzo vero e proprio.

Non ho pensato molto alla prima versione dell'algoritmo e ho scritto il codice più ovvio. Ora lo sto scrivendo in C# usando la piattaforma WealthLab, ma penso che si possa facilmente capire l'essenza dell'algoritmo problematico, ecco la parte più problematica di esso:

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

L'intero problema è nel secondo ciclo. Gestisce simultaneamente i rami sinistro e destro di un potenziale estremo e quindi attraversa solo (N - 1)/2 barre, ma questo non è sufficiente. Le misurazioni mostrano che il tempo impiegato per identificare un estremo in una progressione aritmetica dipende dal periodo N, il che è molto, molto brutto:

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

Provare attraverso i periodi richiederà il tempo di sommare la progressione aritmetica, e questo è un valore molto grande.

Una possibile soluzione è quella di introdurre una variabile aggiuntiva. Dopo tutto, se un estremo è identificato, è garantito che non c'è nessuna barra alla sua destra per (N - 1)/2 quindi un nuovo estremo può essere identificato a partire da bar: current_bar + (N - 1)/2. Tuttavia, gli estremi devono essere identificati insieme ai minimi e un nuovo minimo può essere trovato prima di current_bar + (N - 1)/2. Sarà quindi necessario dividere la ricerca degli estremi e dei minimi in due passaggi, il che annullerà qualsiasi guadagno di prestazioni. Possiamo facilmente dividere due passaggi in due thread elaborati simultaneamente su due core in C#, ma vorrei trovare l'algoritmo ottimale e ottimizzarlo prima di tutto. Sto aspettando l'aiuto degli esperti.

 
C-4: Mi trovo ora di fronte al problema di ottimizzazione dell'algoritmo per la ricerca di un estremo (minimo) di prezzo.

Beh, questo non è un problema di ottimizzazione.

Provando attraverso i periodi si prende la somma della progressione aritmetica, e questo è un valore molto grande.

Trovare un estremo sembra essere un problema dell'ordine di O(n), dove n è il numero di dati. Come si può rendere questo asintotico peggiore, cioè O(n^2) - non posso nemmeno immaginare. O stai confondendo i termini.

L'algoritmo più semplice è ArraySort(), abbastanza veloce, qualcosa intorno a O(n * ln( n ) ), ma probabilmente è ridondante per questo problema.

Si potrebbe inventare qualcosa di ricorsivo che sarebbe più veloce.

Quanto tempo ci vuole per trovare il minimo e per quante barre? Beh, non credo che per 100 barre si cerchi al massimo un secondo e mezzo.

 
Mathemat:

L'algoritmo più semplice è ArraySort(), l'ordinamento integrato è abbastanza veloce, ma è probabilmente ridondante per questo compito.

Il miglior ordinamento è O(n*log(n)). Esattamente ridondante.

Potremmo inventare qualcosa di ricorsivo che sarebbe più veloce.

Più lento. La ricorsione è il più delle volte un male. Ricorsivo? Questo è probabilmente un caso in cui non importa come lo fai, la velocità sarà circa la stessa.

Per codice:

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

I cicli per min e max devono essere esplicitamente separati. E uscire immediatamente dal ciclo se fallisce.

 
TheXpert: Questo è probabilmente il caso in cui non importa come lo fai, la velocità sarà circa la stessa.

In linea di principio, sì. Ma ancora non più di O(n).

OCL aiuterebbe qui. L'asintotica rimarrà la stessa, ovviamente. Ma la velocità potrebbe essere aumentata di cento volte.

12345678910
Nuovo commento