Optimização dos algoritmos. - página 4

Novo comentário
 
MetaDriver:
Agora tenho um problema. Preciso de fazer uma classificação eficiente de matrizes com grandes "custos" de cópia de elementos (ou seja, elementos dos quais são grandes, estruturas "pesadas", objectos de classe, cordas longas, etc.). O senso comum sugere que devemos deixá-los no lugar, mas ordenar em vez disso algum tipo de ponteiros - índices de células da sua localização original. Aqui está a citação de https://www.mql5.com/ru/forum/6476#comment_178318Оставим até agora, e vamos implementá-la no mql5.

Tudo já foi roubado antes de nós :)

Folhas de cálculo em MQL5

A entrada deve ser uma cópia da matriz a ser classificada, os comentários devem ser anotados, e os desnecessários devem ser comentados

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

Tudo já foi roubado antes de nós :)

Folhas de cálculo em MQL5

A entrada deve ser uma cópia da matriz a ser classificada, os comentários devem ser anotados e os comentários desnecessários devem ser comentados.

Estragaste a canção... Ou melhor - tentou fazê-lo. :)

// É evidente que existem boas aproximações. Poderia muito bem ter tirado uma amostra da biblioteca padrão. :)

Existem padrões. E também há alguns excelentes. Mas ainda assim. Aqui é importante especificar e depurar tudo para uma condição de trabalho de um produto utilizável separado. Além disso (porque o estou a enviar para aqui) - o mais rápido possível. Isto é, sugiro que se aperte todo o desempenho possível até centésimos de um por cento inclusive. :)

Este é o primeiro. Em segundo lugar, para objectos precisamos do número de matrizes indexadas igual ao número de critérios de ordenação, que em geral podem ser vários, + (de preferência) função de inserção em ordenação de acordo com vários critérios indexados.

 
MetaDriver:

Estragaste a canção... Ou melhor, tentou. :)

// É evidente que existem boas aproximações. Poderia muito bem ter tirado uma amostra da biblioteca padrão. :)

Há amostras. E mesmo alguns grandes. Mas ainda assim. É importante verificar e depurar tudo até à condição de funcionamento de um produto utilizável separado. E (porque o estou a enviar para aqui) - o mais rápido. Isto é, sugiro que se aperte todo o desempenho possível até centésimos de um por cento inclusive. :)

Isso é a primeira coisa. Segundo - para objectos precisamos do número de matrizes indexadas igual ao número de critérios de ordenação, que em geral podem ser vários, + (de preferência) função de inserção em ordenação por vários critérios de matriz indexada.

A mesma resposta Folhas de cálculo em MQL5.

Está tudo aí. Sob um problema concreto, é possível refazer sob manipulação não de colunas mas de filas, há colunas feitas para que seja possível declará-las como diferentes tipos. Se o tipo de mesa for o mesmo, tudo pode ser reproduzido.

 

Feito um inluder com índices de ordenação para tipos de base.

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

A classificação por defeito é "decrescente", para classificar em direcção ascendente, definir a bandeira de classificação em direcção falsa.

Resultados dos testes: // matrizes de indexação duplo[], int[], string[]; sequencialmente: 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 e teste em reboque.

Colocar o indexador na pasta "MQL5Inclua os índices".

Arquivos anexados:
IndexSort.mqh  14 kb
IndexSort_Test.mq5  4 kb
 

Aqui está uma aula de amostra para trabalhar com OCL. É claro que algumas coisas são incompletas e incómodas, mas talvez alguém o considere ú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);
}
//——————————————————————————————————————————————————————————————————————————————


Refiz um pouco a inicialização, agora é possível fazer cálculos multidimensionais.

 
Isso é bom, eu gosto disso. Devo refazer o meu código tipo C?
 

Grande tema!

Ainda agora enfrentei um problema de optimização com um algoritmo para encontrar um preço extremo (mínimo). As condições são as seguintes: há uma barra, n barras à esquerda e à direita das quais estão abaixo (acima) do seu máximo:

n é um valor escolhido arbitrariamente e gratuito. O período n é sempre estranho, porque a soma das duas barras à direita e à esquerda será sempre um número par ao qual se acrescenta a barra central do preço extremo propriamente dito.

Não pensei muito sobre a primeira versão do algoritmo e escrevi o código mais óbvio. Agora estou a escrevê-lo em C# usando a plataforma WealthLab, mas penso que se pode facilmente compreender a essência do algoritmo problemático, aqui está a parte mais problemática do mesmo:

//Перебираем все бары
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 o problema está na segunda etapa. Lida simultaneamente com ramos esquerdos e direitos de um potencial extremo e, portanto, passa apenas por (N - 1)/2 barras, mas isso não é suficiente. As medições mostram que o tempo gasto na identificação de um extremo numa progressão aritmética depende do período N, que é muito, muito mau:

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

Tentar através dos períodos levará o tempo necessário para resumir a progressão aritmética, e este é um valor muito grande.

Uma solução possível é a introdução de uma variável adicional. Afinal, se um extremo for identificado, é garantido que não há barra à sua direita para (N - 1)/2 de modo a que um novo extremo possa ser identificado começando com barra: actual_bar + (N - 1)/2. No entanto, os extremos têm de ser identificados juntamente com os mínimos e um novo mínimo pode ser encontrado antes do actual_bar + (N - 1)/2. Será portanto necessário dividir a procura de extremos e mínimos em duas passagens que negarão qualquer ganho de desempenho. Podemos facilmente dividir duas passagens em dois fios processados simultaneamente em dois núcleos em C#, mas gostaria de encontrar o algoritmo óptimo e optimizá-lo antes de mais nada. Estou à espera da ajuda de peritos.

 
C-4: Acabo de me deparar com o problema da optimização do algoritmo de procura de um preço extremo (mínimo).

Bem, isto não é um problema de optimização.

Tentar através dos períodos levará a soma da progressão aritmética, e este é um valor muito grande.

Encontrar um extremo parece ser um problema da ordem de O(n), onde n é o número de dados. Como se pode piorar esta assimptótica, ou seja, O(n^2) - Nem consigo imaginar. Ou está a confundir os termos.

O algoritmo mais simples é o ArraySort(), incorporado suficientemente rápido, algo em torno de O(n * ln( n ) ), mas é provavelmente redundante para este problema.

Poderia surgir algo recursivo que fosse mais rápido.

Quanto tempo demora a encontrar o mínimo e por quantos bares? Bem, não acredito que durante 100 barras esteja à procura de um máximo de um segundo e meio.

 
Mathemat:

O algoritmo mais simples é o ArraySort(), a classificação integrada é suficientemente rápida, mas é provavelmente redundante para esta tarefa.

A melhor ordenação é O(n*log(n)). Exactamente redundante.

Poderíamos encontrar algo recursivo que seria mais rápido.

Mais devagar. A recorrência é mais frequentemente maligna. Recursivo? Este é provavelmente um caso em que não importa como o faça, a velocidade será praticamente a mesma.

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

Ciclos para min e max devem ser explicitamente separados. E sair imediatamente do laço se este falhar.

 
TheXpert: Este é provavelmente o caso onde não importa como o faça, a velocidade será praticamente a mesma.

Em princípio, sim. Mas ainda não mais do que O(n).

A OCL ajudaria aqui. As assimptóticas permanecerão as mesmas, é claro. Mas a velocidade poderia muito bem ser aumentada em cem vezes.

12345678910
Novo comentário
Razão: