Оптимизация алгоритмов. - страница 4

Новый комментарий
 
MetaDriver:
Теперь у меня задачка.  Нужно сделать эффективную сортировку массивов с большой "стоимостью" копирования элементов (т.е. элементы которого - объёмистые, "тяжелые" структуры, объекты классов, длинные строки и т.п.).  Здравый смысл подсказывает, что нужно оставлять их на месте, а сортировать вместо них своего рода указатели - индексы ячеек их оригинального расположения.  Далее цитата отсюда :https://www.mql5.com/ru/forum/6476#comment_178318Оставим пока уважаемых разработчиков терминала с их многочисленными текущими задачами, и реализуем это на mql5.

Всё уже украдено до нас :)

Электронные таблицы на MQL5

на вход нужно подавать копию сортируемого массива, коментарии раскоментировать, ненужное закоментировать

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

Всё уже украдено до нас :)

Электронные таблицы на MQL5

на вход нужно подавать копию сортируемого массива, коментарии раскоментировать, ненужное закоментировать

Злой ты!  Песню испортил... Вернее - попытался. :)

// Понятно, что есть хорошие приближения. Я с тем же успехом мог из стандартной библиотеки вытащить образец. :)

Образцы есть. И даже замечательные. И всё же. Тут важно всё прописать и отладить до рабочего состояния отдельного юзабельного продукта. Притом (почему это посылаю сюда) - максимально скорострельного. Т.е. предлагаю выжать всё возможное быстродействие до сотых долей процента включительно. :)

Это первое. Второе - для объектов напрашивается количество индексных массивов равное количеству критериев сортировки, которых может быть в общем случае несколько, + (желательно) функция вставки в отсортированный по нескольким критериям проиндексированный массив.

 
MetaDriver:

Злой ты!  Песню испортил... Вернее - попытался. :)

// Понятно, что есть хорошие приближения. Я с тем же успехом мог из стандартной библиотеки вытащить образец. :)

Образцы есть. И даже замечательные. И всё же. Тут важно всё прописать и отладить до рабочего состояния отдельного юзабельного продукта. Притом (почему это посылаю сюда) - максимально скорострельного. Т.е. предлагаю выжать всё возможное быстродействие до сотых долей процента включительно. :)

Это первое. Второе - для объектов напрашивается количество индексных массивов равное количеству критериев сортировки, которых может быть в общем случае несколько, + (желательно) функция вставки в отсортированный по нескольким критериям проиндексированный массив.

Всё тот же ответ Электронные таблицы на MQL5

там всё это есть. Токма таблицу набок поверни. ну под конкретную задачу можно переделать под манипулирование не столбцов а строк, там сделаны столбцы для того чтоб можно было объявить их разными типами. Если тип таблицы один то всё можно переиграть.

 

Сделал инклюдник с сортировкой индексов для базовых типов.

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

Сортировка по умолчанию "по убыванию", для сортировки по возрастанию нужно установить флаг направления сортировки в false.

Результаты теста:     // индексирование массивов double[],  int[], string[];  Последовательно : сырой массив, по убыванию, по возрастанию

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}

Библиотека и тест в прицепе.

Инклюдник положить в папку "MQL5\Include\Indexes\"

Файлы:
IndexSort.mqh  14 kb
IndexSort_Test.mq5  4 kb
 

Вот, заготовка класса для работы с OCL. Кое что конечно не доделано и коряво, но может кому нибудь пригодится.

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


ЗЫ Чуток переделал инициализацию, теперь можно запускать многомерные расчеты.

 
Это хорошо, мне нравится. Переделать, что ли, свой С-подобный код?
 

 Отличная тема!

Как раз сейчас столкнулся с оптимизационной проблемой алгоритма поиска ценового экстремума (минимума). Условия такие, есть бар, n баров слева и справа от которого ниже (выше) его максимума:

 

n - свободная произвольно выбираемая величина. Период n всегда нечетный, так как сумма двух отрезков справа и слева всегда будет четным числом, к которому прибавляется центральный бар собственно  ценового экстермума.

Над первой версией алгоритма я особенно не задумывался и написал самый очевидный код. Сейчас я пишу на C# в рамках платформы WealthLab, но думаю вы без труда сможете понять суть проблемного алгоритма, вот его самая проблемная часть: 

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

 Вся проблема во втором цикле. Он одновременно обрабатывает левую и правую ветки от потенциального экстремума, а потому перебирает лишь (N - 1)/2 баров, но этого не достаточно. Иземерения показывают, что время затраченное на поиск экстремума в арифметической прогрессии зависит от периода N, а это очень, очень плохо:

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

Перебор периодов будет занимать по времени сумму арифметической прогрессии, а это очень большая величина.

Одно из возможных решений, это ввести доп. переменную. Ведь если экстремум обнаружен, то справа от него гарантированно нет ни одного бара на протяжении (N - 1)/2, значит поиск нового экстремума можно начинать с бара: current_bar +  (N - 1)/2. Но вместе с экстремумами требуется найти и минимумы, а новый минимум может быть обнаружен до бара current_bar +  (N - 1)/2. Поэтому потребуется разделить поиск экстремумов и минимумов на два прохода, что сведет на нет, выигрышь в производительности. На C# без проблем можно разделить два прохода на два потока обрабатываемых одновременно на двух ядрах, но хотелось бы в первую очередь найти оптимальный алгоритм и уже оптимизировать его.  Жду помощи знатоков. 

 
C-4: Как раз сейчас столкнулся с оптимизационной проблемой алгоритма поиска ценового экстремума (минимума).

Ну это не оптимизационная проблема. 

Перебор периодов будет занимать по времени сумму арифметической прогрессии, а это очень большая величина.

Поиск экстремума - вроде проблема порядка О(n), где n - число данных. Как можно сделать эту асимптотику хуже, т.е. O(n^2) - даже не представляю. Или ты путаешься в терминах.

Простейший алгоритм - сортировка ArraySort(), встроенная достаточно быстра, что-то в районе O(n * ln( n ) ).  Но она, вероятно, избыточна для этой задачи.

Можно придумать что-нибудь рекурсивное, которое будет быстрее.

Сколько времени у тебя ищется минимум и для какого кoличества барoв? Ну не верю, что на 100 барах ты ищещшь максимум полторы секунды.

 
Mathemat:

Простейший алгоритм - сортировка ArraySort(), встроенная достаточно быстра.  Но она, вероятно, избыточна для этой задачи.

Лучшая сортировка -- O(n*log(n)). Точно избыточна.

Можно придумать что-нибудь рекурсивное, которое будет быстрее.

Медленнее. Рекурсия чаще всего зло. Рекуррентное? Тут наверное тот случай, когда как ни делай, скорость будет примерно одинаковой.

По коду:

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

Циклы по мин и макс надо однозначно разделять. И выходить из цикла сразу при невыполнении.

 
TheXpert:  Тут наверное тот случай, когда как ни делай, скорость будет примерно одинаковой.

В принципе да. Но все равно не больше О(n).

OCL тут поможет. Асимптотика останется такой же, конечно. Но скорость вполне можно в сотню раз увеличить.

12345678910
Новый комментарий
Причина обращения: