セグメントの範囲を結合するアルゴリズム - 作成の支援 - トレーディングシステム - MQL5アルゴリズム取引フォーラム

Dmitry Fedoseev 2021.04.19 18:35 #11

struct SAllVariants{
   int m_cut[][2];
   int len;
   int li;
   void Init(int aLen){
      ArrayResize(m_cut,aLen);
      len=0;
   }
   void AddCut(int & a[][2],int i){
      m_cut[len][0]=a[i][0];
      m_cut[len][1]=a[i][1];
      len++;
      li=i;
   }
   void Set(SAllVariants & a){
      len=a.len;
      li=a.li;
      for(int i=0;i<len;i++){
         m_cut[i][0]=a.m_cut[i][0];
         m_cut[i][1]=a.m_cut[i][1];
      }
   }
};

SAllVariants av[];

int cut[][2];

void OnStart(){

   Print("=============================================================");
  
   // заполняем массив сотней каких-нибудь отрезков
   FillArray(cut,100);

   //=== алгоритм ====================
   
   // поправить все отрезки, чтобы первая координата была меньше второй   
   int itmp;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]>cut[i][1]){
         itmp=cut[i][0];
         cut[i][0]=cut[i][1];
         cut[i][1]=itmp;
      }
   }
   
   // сортировка массива по первой координате
   ArraySort(cut);
   ArrayPrint(cut);
   // удалить отрезки нулевой длины и повтряющиеся отрезки
   bool ex;
   int ti=0;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]!=cut[i][1]){
         ex=false;
         for(int j=i-1;j>=0 && cut[j][0]==cut[i][0];j--){
            if(cut[j][0]==cut[i][0] && cut[j][1]==cut[i][1]){
               ex=true;
               break;
            }
         }
         if(!ex){
            cut[ti][0]=cut[i][0];
            cut[ti][1]=cut[i][1];
            ti++;
         }
      }
   }
   ArrayResize(cut,ti);
   
   // добавить первый отрезок в массив всех вариантов и еще отрезков с наименьшей координатой
   ArrayResize(av,1);
   av[0].Init(ArrayRange(cut,0)); // вдруг ряд получится из всех отрезков
   av[0].AddCut(cut,0);
   for(int i=1;i<ArrayRange(cut,0);i++){ 
      if(cut[0][0]==cut[i][0]){
         ArrayResize(av,ArraySize(av)+1);
         av[ArraySize(av)-1].Init(ArrayRange(cut,0));
         av[ArraySize(av)-1].AddCut(cut,i);
      }
   }

   // добавить в начало еще отрезков, начинающихся чуть позже, но не позднее конца самого длинного из начальных
   
   // на сначала найти диапазон
   int mn=av[0].m_cut[0][0];
   int mx=av[0].m_cut[0][1];
   for(int i=1;i<ArraySize(av);i++){
      mx=MathMax(mx,av[i].m_cut[0][1]);
   }
   
   // добавить
   for(int i=1;i<ArrayRange(cut,0);i++){
      if(cut[i][0]>mn && cut[i][0]<mx){
         ArrayResize(av,ArraySize(av)+1);
         av[ArraySize(av)-1].Init(ArrayRange(cut,0));
         av[ArraySize(av)-1].AddCut(cut,i);
      }
   }   

   // а теперь самое интересное
   double r;
   bool n;
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){ // для каждого варианта
      //Comment(i," ",ArraySize(av));
      // найти ближайшее расстояние до следующего отрезка
      r=DBL_MAX;
      for(int j=av[i].li+1;j<ArrayRange(cut,0);j++){
         if(cut[j][0]>=av[i].m_cut[av[i].len-1][1]){
            r=MathMin(r,cut[j][0]-av[i].m_cut[av[i].len-1][1]); // потому что допускаются пропуски (важнее составить ряд, чем чтобы он был непрерывным)
         }
      }
      if(r!=DBL_MAX){
         n=false;
         for(int j=av[i].li+1;j<ArrayRange(cut,0);j++){
            if(cut[j][0]-av[i].m_cut[av[i].len-1][1]==r){
               if(!n){
                  n=true;
                  av[i].AddCut(cut,j);
               }
               else{
                  ArrayResize(av,ArraySize(av)+1);
                  av[ArraySize(av)-1].Init(ArrayRange(cut,0));
                  av[ArraySize(av)-1].Set(av[i]);
                  av[ArraySize(av)-1].AddCut(cut,j);
               }
            }
         }
         if(n){
            i--;
         }
      }
   }

   string str="";
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){
      str="";
      for(int j=0;j<av[i].len;j++){
         str=str+(string)av[i].m_cut[j][0]+"-"+(string)av[i].m_cut[j][1]+" ";
      }
      Print("Вариант ",i," - ",str);
   }

}
//+------------------------------------------------------------------+

void FillArray(int & a[][2],int cutCnt){
   ArrayResize(a,cutCnt);
   for(int i=0;i<cutCnt;i++){
      a[i][0]=MathRand()%30;
      a[i][1]=a[i][0]+MathRand()%15;
   }   
}

なんとなく...

Aleksey Vyazmikin 2021.04.19 21:15 #12

Dmitry Fedoseev:

なんとなく...

ありがとうございました。匠の技がすぐにわかる!何が出てくるか、明日から試してみます。

Aleksey Vyazmikin 2021.04.20 21:56 #13

Dmitry Fedoseev:

なんとなく...

コードを試し始め、人工的な例を作成 -配列を埋める

FillArray(cut,4);
cut[0][0]=0;
cut[0][1]=1;
cut[1][0]=3;
cut[1][1]=6;
cut[2][0]=2;
cut[2][1]=5;
cut[3][0]=7;
cut[3][1]=9;

了解です。

2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)       [,0][,1]
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [0,]   0   1
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [1,]   2   5
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [2,]   3   6
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   [3,]   7   9
2021.04.21 00:52:08.328 Q_Podbor (Si-6.21,W1)   Вариант 0 - 0-1 2-5 7-9

つまり、1つのバリエーションを手に入れたが、別のバリエーションも期待しているということだ。

Вариант 1 - 0-1 3-6 7-9

それを見つけるアルゴリズムも教えることは可能なのでしょうか？

Dmitry Fedoseev 2021.04.21 02:32 #14

Aleksey Vyazmikin:

コードを試し始め、人工的な例を作成 -配列を埋める

了解です。

つまり、1つのバリエーションを手に入れたが、もう1つのバリエーションも期待しているのだ。

アルゴリズムもそれを見つけるように学習できるのか？

そして，"0-1 3-6 7-9" という変形は "0 - 0-1 2-5 7-9" という変形よりも優れていません - どちらも 0 から 1 までで，それぞれ長さ 1 のスキップが 2 つあります．

この場合、2つのオプションが表示されます。

1 - 同じことを、スキップのセットの最後から行う。

2 - 最も近いセグメントではなく、公差ですぐに探してください。しかし、この場合、データが多く、ドッキングの配列がたくさんあれば、さらに多くなります。

しかし、variant1以降は、可能な限りのスタート位置から連鎖を作りたくなるものです。これは正しいのですが、アルゴリズムの作業量がかなり増えます。

はい！初期セットの各セグメントからバリアントを構築し始め、最初と最後に構築し続ける必要があるのです。

Aleksey Vyazmikin 2021.04.21 04:37 #15

Dmitry Fedoseev:

そして、「0-1 3-6 7-9」という選択肢は、「0 - 0-1 2-5 7-9」という選択肢よりも優れていません。どちらも0から1までの長さで、それぞれ1ずつスキップが2つあります。

この場合、それらは等しい、私は同意するが、それらは異なっており、問題の条件によって、我々はそれらのスコアの合計を推定する必要があり、ラインを構築するまで、我々はすべてのセグメントの合計スコアを知ることはできません。

ドミトリー・フェドセーエフ

しかし、オプション1以降は、可能な限りすべての開始位置から文字列を構成したいという欲求が生じる。これは正しいのですが、アルゴリズムの作業量がかなり増えます。

はい！初期セットの各セグメントからバリアントを構築し始め、最初と最後に構築し続ける必要があるのです。

これもまた、より正しい戦略であるように思いますただし、バリアントが重複している可能性があると思います。

コードを書いて助けてくれる？

Dmitry Fedoseev 2021.04.21 07:51 #16

struct SAllVariants{
   
   int m_cut[][2];
   int len;

   int m_cut1[][2]; // к концу
   int len1;
   int li1;
   
   int m_cut2[][2]; // с началу
   int len2;
   int li2;   
   
   bool isDopel;
   
   void Init(int aLen){
      ArrayResize(m_cut1,aLen);
      len1=0;
      ArrayResize(m_cut2,aLen);
      len2=0;      
   }
   void AddCut1(int & a[][2],int i){
      m_cut1[len1][0]=a[i][0];
      m_cut1[len1][1]=a[i][1];
      len1++;
      li1=i;
   }
   void AddCut2(int & a[][2],int i){
      m_cut2[len2][0]=a[i][0];
      m_cut2[len2][1]=a[i][1];
      len2++;
      li2=i;
   }   
   void Set(SAllVariants & a){
      len1=a.len1;
      li1=a.li1;
      for(int i=0;i<len1;i++){
         m_cut1[i][0]=a.m_cut1[i][0];
         m_cut1[i][1]=a.m_cut1[i][1];
      }
      len2=a.len2;
      li2=a.li2;
      for(int i=0;i<len2;i++){
         m_cut2[i][0]=a.m_cut2[i][0];
         m_cut2[i][1]=a.m_cut2[i][1];
      }      
   }
   
   bool Eq(SAllVariants & a){
      if(len1!=a.len1 || len2!=a.len2){
         return(false);
      }
      for(int i=0;i<len1;i++){
         if(m_cut1[i][0]!= a.m_cut1[i][0] || m_cut1[i][1]!= a.m_cut1[i][1]){
            return(false);
         }
      }
      for(int i=0;i<len2;i++){
         if(m_cut2[i][0]!= a.m_cut2[i][0] || m_cut2[i][1]!= a.m_cut2[i][1]){
            return(false);
         }      
      }      
      return(true);
   }
   
   void Combine(){
      len=len1+len2-1;
      ArrayResize(m_cut,len);
      int j=0;
      for(int i=len2-1;i>0;i--){
         m_cut[j][0]=m_cut2[i][0];
         m_cut[j][1]=m_cut2[i][1];         
         j++;
      }
      for(int i=0;i<len1;i++){
         m_cut[j][0]=m_cut1[i][0];
         m_cut[j][1]=m_cut1[i][1]; 
         j++;
      }      
   }
};

SAllVariants av[];

int cut[][2];

void OnStart(){

   Print("=============================================================");
  
   // заполняем массив сотней каких-нибудь отрезков
   FillArray(cut,100);

   //=== алгоритм ====================
   
   // поправить все отрезки, чтобы первая координата была меньше второй   
   int itmp;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]>cut[i][1]){
         itmp=cut[i][0];
         cut[i][0]=cut[i][1];
         cut[i][1]=itmp;
      }
   }
   
   // сортировка массива по первой координате
   ArraySort(cut);
   ArrayPrint(cut);
   // удалить отрезки нулевой длины и повтряющиеся отрезки
   bool ex;
   int ti=0;
   for(int i=0;i<ArrayRange(cut,0);i++){
      if(cut[i][0]!=cut[i][1]){
         ex=false;
         for(int j=i-1;j>=0 && cut[j][0]==cut[i][0];j--){
            if(cut[j][0]==cut[i][0] && cut[j][1]==cut[i][1]){
               ex=true;
               break;
            }
         }
         if(!ex){
            cut[ti][0]=cut[i][0];
            cut[ti][1]=cut[i][1];
            ti++;
         }
      }
   }
   ArrayResize(cut,ti);
   
   // добавить каждый отрезок в массив всех вариантов
   ArrayResize(av,ArrayRange(cut,0));
   for(int i=0;i<ArrayRange(cut,0);i++){
      av[i].Init(ArrayRange(cut,0));
      av[i].AddCut1(cut,i); // в массив, идущий к концу
      av[i].AddCut2(cut,i); // в массив, идущий к началу
   }


   // а теперь самое интересное
   
   // к концу
   
   double r;
   bool n;
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){ // для каждого варианта
      // найти ближайшее расстояние до следующего отрезка
      r=DBL_MAX;
      for(int j=av[i].li1+1;j<ArrayRange(cut,0);j++){
         if(cut[j][0]>=av[i].m_cut1[av[i].len1-1][1]){
            r=MathMin(r,cut[j][0]-av[i].m_cut1[av[i].len1-1][1]); // потому что допускаются пропуски (важнее составить ряд, чем чтобы он был непрерывным)
         }
      }
      if(r!=DBL_MAX){
         n=false;
         for(int j=av[i].li1+1;j<ArrayRange(cut,0);j++){
            if(cut[j][0]-av[i].m_cut1[av[i].len1-1][1]==r){
               if(!n){
                  n=true;
                  av[i].AddCut1(cut,j);
               }
               else{
                  ArrayResize(av,ArraySize(av)+1);
                  av[ArraySize(av)-1].Init(ArrayRange(cut,0));
                  av[ArraySize(av)-1].Set(av[i]);
                  av[ArraySize(av)-1].AddCut1(cut,j);
               }
            }
         }
         if(n){
            i--;
         }
      }
   }
   
   // к началу
   
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){ // для каждого варианта
      // найти ближайшее расстояние до следующего отрезка
      r=DBL_MAX;
      for(int j=av[i].li2-1;j>=0;j--){
         if(cut[j][1]<=av[i].m_cut2[av[i].len2-1][0]){
            r=MathMin(r,av[i].m_cut2[av[i].len2-1][0]-cut[j][1]); // потому что допускаются пропуски (важнее составить ряд, чем чтобы он был непрерывным)
         }
      }
      if(r!=DBL_MAX){
         n=false;
         for(int j=av[i].li2-1;j>=0;j--){
            if(av[i].m_cut2[av[i].len2-1][0]-cut[j][1]==r){
               if(!n){
                  n=true;
                  av[i].AddCut2(cut,j);
               }
               else{
                  ArrayResize(av,ArraySize(av)+1);
                  av[ArraySize(av)-1].Init(ArrayRange(cut,0));
                  av[ArraySize(av)-1].Set(av[i]);
                  av[ArraySize(av)-1].AddCut2(cut,j);
               }
            }
         }
         if(n){
            i--;
         }
      }
   } 
   
   // пометить дубли
   
   for(int i=0;i<ArraySize(av);i++){   
      av[i].isDopel=false;
      for(int j=0;j<i;j++){   
         if(av[i].Eq(av[j])){
            av[i].isDopel=true;
            break;
         }
      }
   }
   
   // соединить два массива в 1
   
   for(int i=0;i<ArraySize(av);i++){
      if(!av[i].isDopel){
         av[i].Combine();
      }
   }
   
   // вывод
   
   int h=FileOpen("Выстраивание отрезков.txt",FILE_TXT|FILE_WRITE);
   
   for(int i=0;i<ArrayRange(cut,0);i++){
      FileWrite(h,(string)cut[i][0]+"-"+(string)cut[i][1]);
   }   
   
   FileWrite(h,"");
   
   string str="";
   int vn=0;
   for(int i=0;i<ArraySize(av) && !IsStopped();i++){
      if(!av[i].isDopel){
         str="";
         for(int j=0;j<av[i].len;j++){
            str=str+(string)av[i].m_cut[j][0]+"-"+(string)av[i].m_cut[j][1]+" ";
         }
         Print("Вариант ",vn," - ",str);
         FileWrite(h,"Вариант ",vn," - ",str);
         vn++;
      }
   }
   
   FileClose(h);

}
//+------------------------------------------------------------------+

void FillArray(int & a[][2],int cutCnt){
   ArrayResize(a,cutCnt);
   for(int i=0;i<cutCnt;i++){
      a[i][0]=MathRand()%30;
      a[i][1]=a[i][0]+MathRand()%15;
   }   
}

各バリアントは 2 つの配列にセグメントを格納するので、Combine() メソッドを使用してそれらをひとつにまとめると便利です。

Aleksey Vyazmikin 2021.04.22 14:01 #17

Dmitry Fedoseev:

配列から重複をふるい落としたわけではなく、マークをつけただけです。各バリアントはセグメントをふたつの配列に格納するようになったので、Combine() メソッドでひとつにまとめればより便利になります。

Dmitryさん、新しいアルゴリズムありがとうございます。

はい、確かに枚数は多いです。

2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 0 - 0-1 2-5 7-9 
2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 1 - 0-1 2-5 7-9 
2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 2 - 0-1 3-6 7-9 
2021.04.22 16:55:43.829 Q_Podbor_02 (Si-6.21,M1)        Вариант 3 - 0-1 3-6 7-9

私の理解では、それらは数えることができない。1000のエレメントの組み合わせを待つことができず、ネットブックがメモリ不足になり始めた :(

また、セグメントを追加する際にすべての組み合わせを使用せず、現在のステップで可能な一定の数、例えばベスト10だけを使用することは可能でしょうか？

Dmitry Fedoseev 2021.04.22 14:25 #18

Aleksey Vyazmikin:

Dmitryさん、新しいアルゴリズムありがとうございます。

はい、確かに枚数は多いです。

私の理解では、数えることはできません。1000個の元素の組み合わせが待ちきれず、ネットブックがメモリ不足になり始めた :(

セグメントの追加時にすべての組み合わせを使用せず、現在のステップで可能な特定の数、例えばベスト10だけを使用することは可能ですか？

それがベストだと知るためには、他と比較しなければならない、つまり、まず全部を手に入れなければならないのです。もうひとつは、アルゴリズムをどうにかして最適化することですが、このアルゴリズムに人生を捧げるという目標はありません（笑)。

たぶん、十分性の基準を決めて、まずすべての選択肢を手に入れ、ランダムに選ばれた1つのセグメントだけから始めて、満足のいく選択肢が現れるまで、そうしていくのだろう。

また、2つ目の方法として、1要素ずつではなく、数十要素を一度にバリアントでスケーリングし、最後にトリミングすることも可能です。

Aleksey Vyazmikin 2021.04.22 15:48 #19

Dmitry Fedoseev:

それがベストだと知るためには、他と比較しなければならない、つまり、まず全部を手に入れなければならないのです。もうひとつは、アルゴリズムをどうにかして最適化することですが、このアルゴリズムに人生を捧げるという目標はありません（笑)。

1つのセグメントについて、その品質を評価する係数があるとします。そして、反復するたびに、例えば、その係数の上位10個だけで分岐させます。

ドミトリー・フェドセーエフ：

多分、充足基準を決めて、まずすべての変種を、ランダムに選ばれた1つのセグメントだけから始めて、満足のいく変種が現れるまで、繰り返し取得します。

残念ながら、ここで「十分」を推し量るのは難しい。ここでは、基準を知ることが必要で、そこから公差を定義することが可能だが、私は基準を持っていないのだ。

ドミトリー・フェドセーエフ

また、2番目のオプションは、オプションで配列を1要素ずつではなく、数十要素に拡大縮小し、最後に整列させるというもので、高速化が可能です。

OpenCLを使ったパラレルの意味がよくわからないのですが？

Dmitry Fedoseev 2021.04.22 16:24 #20

Aleksey Vyazmikin:

1.1つのセグメントについてですが、その品質を評価するための係数があるとします。そして、反復するたびに、例えばその係数の上位10件だけに分岐します。

2.残念ながら、ここで「充足感」を見積もるのは難しい。ベンチマークを知る必要があり、そこから許容範囲を決めればいいのですが、私はベンチマークを持っていないのです。

3.OpenCLを使ったパラレルの意味がよくわからないのですが？

1.この係数はどこにあるのですか？

2.ポイント1はどうでしょうか？

3.いいえ、もっとシンプルです。よし、明日からスピードアップしてみよう。

セグメントの範囲を結合するアルゴリズム - 作成の支援 - ページ 2