アルゴリズムの最適化

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で表計算

入力はソートする配列のコピーで、コメントには注釈を入れ、不要なものはコメントアウトする。

意地悪！曲を台無しに...。というか、そうしようとした。:)

// 良い近似値があることは明らかです。標準ライブラリからサンプルを引っ張ってきたようなものです。:)

パターンがあるんです。しかも、優秀なものもあるんですよ。でも、やっぱり。ここで重要なのは、すべてを別個に使える製品の動作状態まで仕様化し、デバッグすることです。しかも（なぜここに送るのか）--できるだけ早く。つまり、100分の1パーセントまで可能な限り性能を絞り込むことを提案します。:)

これが1つ目です。第二に、オブジェクトのために我々は、一般的なケースでは、いくつかのことができるソート基準の数に等しいインデックス配列の数、+（好ましくは）いくつかの基準インデックス配列に応じてソートでの挿入の関数が必要です。

Mykola Demko 2012.04.07 13:14 #33

MetaDriver:

意地悪！曲を台無しに...。というか、努力したんですね。:)

// 良い近似値があることは明らかです。標準ライブラリからサンプルを引っ張ってきたようなものです。:)

サンプルもあります。そして、素晴らしいものまで。でも、やっぱり。すべてをチェックし、別に使える状態までデバッグすることが重要です。そして（なぜここに送るかというと）-最速のもの。つまり、100分の1パーセントまで可能な限り性能を絞り込むことを提案します。:)

それがまず第一です。第二に - オブジェクトの我々は、一般的にいくつかの可能性がありますソート基準の数に等しいインデックス配列の数、+（好ましくは）いくつかの基準でソートされたインデックス配列で挿入の機能が必要です。

同じ答えMQL5でスプレッドシートを使う。

全部あるんです。具体的な問題としては、列ではなく行を操作して作り直すことが可能で、そのために作られた列があり、それらを異なる型として宣言することが可能である。テーブルの種類が同じであれば、すべて再生可能です。

Vladimir Gomonov 2012.04.08 03:11 #34

ベースタイプのソートインデックスを持つインルーラーを作りました。

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

デフォルトでは降順にソートされるが、昇順にソートする場合はソート方向フラグをfalseに設定する。

テスト結果： //配列のインデックス作成 double[], int[], string[]; sequentially : raw array, descending array, ascending array

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}

トレーラーでのライブラリとテスト。

インデクサを "MQL5Include "フォルダに配置します。

ファイル:

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 は任意に選んだ自由な値である。右と左の2本のバーの合計が必ず偶数になり、そこに価格極大値の中央のバーが加わるので、期間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;
   }
}

問題の全ては2番目のループにある。極限状態の左右の枝を同時に処理するため、(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 のバーが存在しないことが保証されるので、bar: current_bar + (N - 1)/2 で始まる新しい極限を特定することができるのです。しかし、極小値を極小値とともに特定する必要があり、current_bar + (N - 1)/2 の前に新しい極小値を見つけることができる。そのため、極値や極小値の探索を2回に分けて行う必要があり、せっかくの性能向上が台無しになってしまいます。C#で2つのパスを2つのコアで同時に処理するスレッドに分割することは簡単にできますが、まずは最適なアルゴリズムを見つけて最適化したいと思います。専門家の助けを待っています。
。

Sceptic Philozoff 2012.05.21 11:55 #38

C-4: ちょうど今、価格の極値（最小値）を探索するアルゴリズムの最適化問題に直面しているところです。

まあ、これは最適化問題ではないんですけどね。

ピリオドを試行すると、算術進行の和がとれ、これは非常に大きな値となる。

極限値を求めるのは、データ数をnとするとO(n)のオーダーの問題になるようだ。この漸近的な悪化、つまりO(n^2)をどうすればいいのか、私には想像もつかないのです。あるいは、用語を混同しているのか。

最も単純なアルゴリズムはArraySort() で、O(n * ln( n ) )程度の速度で組み込まれています。しかし、この問題ではおそらく冗長でしょう。

より高速な再帰的なものを思いつくことができるだろう。

最小値を求めるには、何本分の時間がかかりますか？まあ、100本の小節に対して、最大1.5秒を検索しているとは思えませんけどね。

TheXpert 2012.05.21 12:01 #39

Mathemat:

最も単純なアルゴリズムは ArraySort() で、組み込みのソートでも十分に高速です。しかし、このタスクではおそらく冗長です。

最適なソートはO(n*log(n))である。まさにredundant。

より高速な再帰的なものを考え出すことができるだろう。

より遅くなる。再帰は最もよく悪である。再帰的？これはおそらく、どうやったって速度は同じぐらいになるケースだと思います。

コードで

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

minとmaxのサイクルは明示的に分離する必要があります。そして、失敗したらすぐにループを終了させる。

Sceptic Philozoff 2012.05.21 12:08 #40

TheXpert: これはおそらく、どうやったってスピードは同じぐらいになるんでしょうね。

原則的には、そうです。しかし、それでもO(n)以上にはならない。

OCLはここで役に立つでしょう。もちろん、漸近法は変わりません。しかし、速度は100倍になることも十分にあり得ます。

アルゴリズムの最適化 - ページ 4