算法的优化。

Mykola Demko 2012.04.06 22:19 #31

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

Vladimir Gomonov 2012.04.06 22:48 #32

Urain:

一切都已经在我们面前被偷走了 :)

MQL5中的电子表格

输入应该是要排序的数组的副本，注释应该是注释，不必要的注释应该是注释。

你真卑鄙，你毁了这首歌...或者说--试图这样做。:)

// 很明显，有很好的近似值。我还不如从标准库中提取一个样本。:)

是有规律可循的。也有一些优秀的作品。但仍然如此。在这里，重要的是编码和调试一切，以达到一个独立可用的产品的工作状态。此外（我为什么在这里发送）--尽可能快。也就是说，我建议将所有可能的性能压缩到百分之一（包括百分之一）。:)

这是第一次。第二，对于对象，我们需要的索引数组的数量等于排序标准的数量，在一般情况下可以是几个，+（最好是）根据几个标准的索引数组插入的功能。

Mykola Demko 2012.04.07 13:14 #33

MetaDriver:

你真卑鄙，你毁了这首歌...或者说，你试过了。:)

// 很明显，有很好的近似值。我还不如从标准库中提取一个样本。:)

有样品。甚至还有一些伟大的。但仍然如此。重要的是要检查和调试一切，使其达到独立可用产品的工作状态。还有（我为什么要把它发到这里）--最快的一个。也就是说，我建议将所有可能的性能压缩到百分之一（包括百分之一）。:)

这是第一件事。第二，对于对象，我们需要的索引数组的数量等于排序标准的数量，一般来说可能是几个，+（最好是）插入按几个标准排序的索引数组中的功能。

同样的答案MQL5中的电子表格。

这一切都在那里。在一个具体的问题下，有可能在操纵下重新制作的不是列而是行，有列做的是有可能将它们声明为不同的类型。如果表格类型相同，一切都可以重放。

Vladimir Gomonov 2012.04.08 03:11 #34

制作了一个带有基本类型的排序索引的输入器。

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

Andrey Dik 2012.05.18 18:54 #35

这里有一个使用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);
}
//——————————————————————————————————————————————————————————————————————————————

我对初始化做了一些修改，现在你可以运行多维计算了。

Sceptic Philozoff 2012.05.20 15:40 #36

这很好，我喜欢这样。我应该重做我的类C代码吗？

Vasiliy Sokolov 2012.05.21 09:26 #37

很好的主题!

刚才我面临一个优化问题，有一个寻找价格极值（最小值）的算法。条件如下：有一个柱子，其左边和右边的n个柱子都低于（高于）其最大值。

n 是一个自由的任意选择的值。周期n总是奇数，因为右边和左边的两根柱子的总和将总是一个偶数，价格极值本身的中心柱子被加到这个偶数上。

我对第一版的算法没有多想，写了最明显的代码。现在我使用WealthLab平台用C#编写，但我认为你可以很容易地理解有问题的算法的本质，这里是最有问题的部分。

//Перебираем все бары
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#中很容易地将两个通道分成两个线程同时在两个核心上处理，但我想首先找到最佳算法并对其进行优化。我在等待专家的帮助。

Sceptic Philozoff 2012.05.21 11:55 #38

C-4: 我现在刚刚面临着寻找价格极值（最低点）的算法的优化问题。

嗯，这不是一个优化问题。

试着通过期数会取算术级数的总和，而这是一个非常大的数值。

寻找极值似乎是一个O(n)级的问题，其中n是数据的数量。你怎么能让这个渐进式更糟糕，即O(n^2) - 我甚至无法想象。或者你混淆了这些术语。

最简单的算法是ArraySort()，内置足够快，大约是O(n * ln( n ))。但对于这个问题，它可能是多余的。

你可以想出一些递归的方法，这样会更快。

找到最小值需要多长时间，有多少条？好吧，我不相信你在寻找100条的最多一秒半的时间。

TheXpert 2012.05.21 12:01 #39

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

最小和最大的循环必须明确分开。并在失败时立即退出循环。

Sceptic Philozoff 2012.05.21 12:08 #40

TheXpert: 这可能是无论你怎么做，速度都会差不多的情况。

原则上，是的。但仍不超过O(n)。

OCL在这里会有帮助。当然，渐进法将保持不变。但速度完全可以提高一百倍。

算法的优化。 - 页 4