Optimización de algoritmos. - página 4

Nuevo comentario
 
MetaDriver:
Ahora tengo un problema. Necesito hacer una ordenación eficiente de arrays con gran "coste" de copia de elementos (es decir, elementos de los cuales son estructuras grandes y "pesadas", objetos de clase, cadenas largas, etc.). El sentido común sugiere que deberíamos dejarlos en su sitio, pero ordenar en su lugar algún tipo de punteros - índices de celdas de su ubicación original. Aquí está la cita de https://www.mql5.com/ru/forum/6476#comment_178318Оставим hasta ahora, y vamos a implementarla en mql5.

Ya nos han robado todo antes :)

Hojas de cálculo en MQL5

La entrada debe ser una copia del array a ordenar, los comentarios deben ser anotados y lo innecesario debe ser comentado

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

Ya nos han robado todo antes :)

Hojas de cálculo en MQL5

La entrada debe ser una copia del array a ordenar, los comentarios deben ser anotados y lo innecesario comentado.

¡Eres malo! Arruinaste la canción... O mejor dicho, lo intentó. :)

// Está claro que hay buenas aproximaciones. También podría haber sacado una muestra de la biblioteca estándar. :)

Hay patrones. Y también hay algunos excelentes. Pero aún así. Aquí es importante codificar y depurar todo para que funcione un producto utilizable por separado. Además (por eso lo envío aquí) - lo más rápido posible. Es decir, sugiero exprimir todo el rendimiento posible hasta las centésimas de porcentaje inclusive. :)

Esta es la primera. En segundo lugar, para los objetos necesitamos un número de matrices de índices igual al número de criterios de ordenación, que en el caso general pueden ser varios, + (preferentemente) función de inserción en matriz indexada ordenada según varios criterios.

 
MetaDriver:

¡Eres malo! Arruinaste la canción... O mejor dicho, lo intentaste. :)

// Está claro que hay buenas aproximaciones. También podría haber sacado una muestra de la biblioteca estándar. :)

Hay muestras. E incluso algunos grandes. Pero aún así. Es importante comprobar y depurar todo hasta conseguir un estado de funcionamiento de un producto utilizable por separado. Y (por eso lo envío aquí) - el más rápido. Es decir, sugiero exprimir todo el rendimiento posible hasta las centésimas de porcentaje inclusive. :)

Eso es lo primero. Segundo - para los objetos necesitamos el número de matrices de índices igual al número de criterios de ordenación, que en general pueden ser varios, + (preferentemente) función de inserción en matriz indexada ordenada por varios criterios.

La misma respuesta Hojas de cálculo en MQL5.

Todo está ahí. Bajo un problema concreto, es posible rehacer bajo manipulación no columnas sino filas, hay columnas hechas para es posible declararlas como tipos diferentes. Si el tipo de tabla es el mismo, todo puede ser reproducido.

 

Realizado un inluder con índices de ordenación para los tipos de base.

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

La ordenación por defecto es "descendente", para ordenar en dirección ascendente, ponga el indicador de dirección de ordenación en falso.

Resultados de la prueba: // indexación de matrices double[], int[], string[]; secuencialmente : matriz bruta, matriz descendente, matriz 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 y prueba en el remolque.

Ponga el indexador en la carpeta "MQL5\Include\Indexes\".

Archivos adjuntos:
IndexSort.mqh  14 kb
IndexSort_Test.mq5  4 kb
 

Aquí hay una clase de ejemplo para trabajar con OCL. Por supuesto, algunas cosas están incompletas y son incómodas, pero tal vez alguien lo encuentre útil.

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


He reelaborado un poco la inicialización, ahora se pueden realizar cálculos multidimensionales.

 
Eso es bueno, me gusta. ¿Debo rehacer mi código en C?
 

¡Gran tema!

Ahora mismo me he enfrentado a un problema de optimización con un algoritmo para encontrar un extremo de precio (mínimo). Las condiciones son las siguientes: hay una barra, n barras a la izquierda y a la derecha de la cual están por debajo (por encima) de su máximo:

n es un valor libre elegido arbitrariamente. El periodo n es siempre impar, porque la suma de las dos barras a la derecha y a la izquierda será siempre un número par al que se le suma la barra central del extremo del precio propiamente dicho.

No pensé mucho en la primera versión del algoritmo y escribí el código más obvio. Ahora lo estoy escribiendo en C# usando la plataforma WealthLab, pero creo que puedes entender fácilmente la esencia del algoritmo problemático, aquí está la parte más problemática:

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

Todo el problema está en el segundo bucle. Maneja simultáneamente las ramas izquierda y derecha de un extremo potencial y, por lo tanto, sólo pasa por (N - 1)/2 barras, pero eso no es suficiente. Las mediciones muestran que el tiempo empleado en identificar un extremo en una progresión aritmética depende del periodo N, lo cual es muy, muy malo:

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

Si se intenta recorrer los periodos, se tardará en sumar la progresión aritmética, y ésta es un valor muy grande.

Una posible solución es introducir una variable adicional. Al fin y al cabo, si se identifica un extremo, se garantiza que no hay ninguna barra a su derecha para (N - 1)/2 por lo que se puede identificar un nuevo extremo a partir de barra: barra_actual + (N - 1)/2. Sin embargo, es necesario identificar los extremos junto con los mínimos y se puede encontrar un nuevo mínimo antes de bar_actual + (N - 1)/2. Por lo tanto, será necesario dividir la búsqueda de extremos y mínimos en dos pasadas, lo que reducirá la ganancia de rendimiento a cero. Podemos dividir fácilmente dos pases en dos hilos procesados simultáneamente en dos núcleos en C#, pero me gustaría encontrar el algoritmo óptimo y optimizarlo en primer lugar. Espero la ayuda de los expertos.

 
C-4: Ahora me encuentro con el problema de optimización del algoritmo de búsqueda de un extremo de precio (mínimo).

Bueno, esto no es un problema de optimización.

Al intentar recorrer los periodos se tomará la suma de la progresión aritmética, y ésta es un valor muy grande.

Encontrar un extremo parece ser un problema del orden de O(n), donde n es el número de datos. Cómo se puede hacer esta asintótica peor, es decir, O(n^2) - no puedo ni imaginar. O estás confundiendo los términos.

El algoritmo más sencillo es ArraySort(), bastante rápido incorporado, algo así como O(n * ln( n ) ). Pero probablemente sea redundante para este problema.

Podrías idear algo recursivo que fuera más rápido.

¿Cuánto tiempo se tarda en encontrar el mínimo y para cuántas barras? Bueno, no creo que para 100 bares estés buscando un máximo de un segundo y medio.

 
Mathemat:

El algoritmo más sencillo es ArraySort(), la ordenación incorporada es suficientemente rápida, pero probablemente sea redundante para esta tarea.

La mejor ordenación es O(n*log(n)). Exactamente redundante.

Podríamos idear algo recursivo que fuera más rápido.

Más lento. La recursividad es, en la mayoría de los casos, maligna. ¿Recursivo? Este es probablemente un caso en el que no importa cómo lo hagas, la velocidad será más o menos la misma.

Por código:

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

Los ciclos para el mínimo y el máximo deben estar explícitamente separados. Y salir del bucle inmediatamente si falla.

 
TheXpert: Este es probablemente el caso en el que no importa cómo lo hagas, la velocidad será más o menos la misma.

En principio, sí. Pero aún así no es más que O(n).

La OCL ayudaría en este caso. La asintótica seguirá siendo la misma, por supuesto. Pero la velocidad podría multiplicarse por cien.

12345678910
Nuevo comentario