Optimisation des algorithmes. - page 4

Nouveau commentaire
 
MetaDriver:
Maintenant, j'ai un problème. J'ai besoin de faire un tri efficace des tableaux avec un grand "coût" de la copie des éléments (c'est-à-dire les éléments dont les structures sont grandes, "lourdes", des objets de classe, de longues chaînes, etc). Le bon sens suggère que nous devrions les laisser en place, mais trier à la place une sorte de pointeurs - index des cellules de leur emplacement d'origine. Voici la citation de https://www.mql5.com/ru/forum/6476#comment_178318Оставим jusqu'à présent, avec leurs nombreuses tâches en cours, et l'implémenter dans mql5.

Tout a déjà été volé avant nous :)

Feuilles de calcul dans MQL5

L'entrée doit être une copie du tableau à trier, les commentaires doivent être annotés, et le superflu doit être commenté.

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

Tout a déjà été volé avant nous :)

Feuilles de calcul dans MQL5

L'entrée doit être une copie du tableau à trier, les commentaires doivent être annotés et le superflu commenté.

Tu es méchant ! Tu as gâché la chanson... Ou plutôt, j'ai essayé. :)

// Il est clair qu'il existe de bonnes approximations. J'aurais pu aussi bien tirer un échantillon de la bibliothèque standard. :)

Il y a des modèles. Et il y en a d'excellentes, aussi. Mais quand même. Dans ce cas, il est important de tout enregistrer et de tout déboguer pour obtenir un produit utilisable distinct. De plus (pourquoi je l'envoie ici) - le plus vite possible. C'est-à-dire que je suggère d'exploiter toutes les performances possibles jusqu'aux centièmes de pour cent inclus. :)

C'est le premier. Deuxièmement, pour les objets, nous avons besoin d'un nombre de tableaux d'index égal au nombre de critères de tri, qui, dans le cas général, peuvent être plusieurs, + (de préférence) une fonction d'insertion dans un tableau indexé trié selon plusieurs critères.

 
MetaDriver:

Tu es méchant ! Tu as gâché la chanson... Ou plutôt, vous avez essayé. :)

// Il est clair qu'il existe de bonnes approximations. J'aurais pu aussi bien tirer un échantillon de la bibliothèque standard. :)

Il y a des échantillons. Et même quelques grands. Mais quand même. Il est important de tout vérifier et de tout déboguer pour obtenir un produit distinct et utilisable. Et (pourquoi je l'envoie ici) - le plus rapide. C'est-à-dire que je suggère d'exploiter toutes les performances possibles jusqu'aux centièmes de pour cent inclus. :)

C'est la première chose. Deuxièmement - pour les objets, nous avons besoin d'un nombre de tableaux d'index égal au nombre de critères de tri, qui en général peuvent être plusieurs, + (de préférence) une fonction d'insertion dans un tableau indexé trié par plusieurs critères.

Même réponse Feuilles de calcul dans MQL5.

Tout est là. Sous un problème concret, il est possible de refaire sous manipulation non pas des colonnes mais des lignes, il y a des colonnes faites pour il est possible de les déclarer comme des types différents. Si le type de table est le même, tout peut être rejoué.

 

Réalisation d'un inluder avec des index de tri pour les types de base.

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

Le tri par défaut est "descendant", pour trier dans la direction ascendante, mettez l'indicateur de direction du tri à false.

Résultats du test : // indexation des tableaux double[], int[], string[] ; séquentiellement : tableau brut, tableau descendant, tableau ascendant

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}

Bibliothèque et test dans la remorque.

Placez l'indexeur dans le dossier "MQL5\Include\Indexes\".

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

Voici un exemple de classe pour travailler avec OCL. Bien sûr, certaines choses sont incomplètes et maladroites, mais peut-être que quelqu'un trouvera cela 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);
}
//——————————————————————————————————————————————————————————————————————————————


J'ai retravaillé un peu l'initialisation, maintenant vous pouvez exécuter des calculs multidimensionnels.

 
C'est bien, j'aime ça. Dois-je refaire mon code en C ?
 

Grand sujet !

Je viens d'être confronté à un problème d'optimisation avec un algorithme pour trouver un extremum (minimum) de prix. Les conditions sont les suivantes : il existe une barre, dont n barres à gauche et à droite sont inférieures (supérieures) à son maximum :

n est une valeur libre choisie arbitrairement. La période n est toujours impaire, car la somme des deux barres à droite et à gauche sera toujours un nombre pair auquel on ajoute la barre centrale de l'extremum de prix proprement dit.

Je n'ai pas beaucoup réfléchi à la première version de l'algorithme et j'ai écrit le code le plus évident. Maintenant, je l'écris en C# en utilisant la plateforme WealthLab, mais je pense que vous pouvez facilement comprendre l'essence de l'algorithme problématique, voici la partie la plus problématique de celui-ci :

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

Tout le problème est dans la deuxième boucle. Il traite simultanément les branches gauche et droite d'un extremum potentiel et ne passe donc que par (N - 1)/2 barres, mais cela ne suffit pas. Des mesures montrent que le temps passé à identifier un extremum dans une progression arithmétique dépend de la période N, ce qui est très, très mauvais :

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

En parcourant les périodes, il faudra du temps pour résumer la progression arithmétique, et il s'agit d'une très grande valeur.

Une solution possible est d'introduire une variable supplémentaire. Après tout, si un extremum est identifié, il est garanti qu'il n'y a pas de barre à sa droite pendant (N - 1)/2, de sorte qu'un nouvel extremum peut être identifié en commençant par bar : current_bar + (N - 1)/2. Cependant, les extrema doivent être identifiés en même temps que les minima et un nouveau minimum peut être trouvé avant current_bar + (N - 1)/2. Il sera donc nécessaire de diviser la recherche des extrema et des minima en deux passes, ce qui annulera tout gain de performance. Nous pouvons facilement diviser deux passes en deux threads traités simultanément sur deux cœurs en C# mais j'aimerais d'abord trouver l'algorithme optimal et l'optimiser. J'attends l'aide d'experts.

 
C-4: Je suis maintenant confronté au problème d'optimisation de l'algorithme de recherche d'un extremum (minimum) de prix.

Ce n'est pas un problème d'optimisation.

En essayant de parcourir les périodes, on obtient la somme de la progression arithmétique, et cette valeur est très grande.

La recherche d'un extremum semble être un problème de l'ordre de O(n), où n est le nombre de données. Comment vous pouvez rendre cette asymptotique pire, c'est-à-dire O(n^2) - je ne peux même pas imaginer. Ou vous confondez les termes.

L'algorithme le plus simple est ArraySort(), intégré assez rapidement, quelque chose autour de O(n * ln( n ) ). Mais il est probablement redondant pour ce problème.

Vous pourriez trouver quelque chose de récursif qui serait plus rapide.

Combien de temps faut-il pour trouver le minimum et pour combien de barres ? Eh bien, je ne crois pas que vous cherchiez un maximum d'une seconde et demie pour 100 barres.

 
Mathemat:

L'algorithme le plus simple est ArraySort(), le tri intégré est assez rapide, mais il est probablement redondant pour cette tâche.

Le meilleur tri est O(n*log(n)). Exactement redondant.

On pourrait trouver quelque chose de récursif qui serait plus rapide.

Plus lentement. La récursion est le plus souvent maléfique. Récursif ? Il s'agit probablement d'un cas où, quelle que soit la façon dont vous le faites, la vitesse sera à peu près la même.

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

Les cycles pour min et max doivent être explicitement séparés. Et quittez la boucle immédiatement si elle échoue.

 
TheXpert: C'est probablement le cas où, quelle que soit la façon dont vous le faites, la vitesse sera à peu près la même.

En principe, oui. Mais toujours pas plus de O(n).

OCL serait utile ici. L'asymptotique restera la même, bien sûr. Mais la vitesse pourrait bien être multipliée par cent.

12345678910
Nouveau commentaire