Algorithmus zum Kombinieren von Bereichen eines Segments - Hilfe zum Erstellen - Automatische Handelssysteme - MQL5 Forum über algorithmischen Handel

Dmitry Fedoseev 2021.04.19 20: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;
   }   
}

Irgendwie...

Aleksey Vyazmikin 2021.04.19 23:15 #12

Dmitry Fedoseev:

Irgendwie...

Ich danke Ihnen! Man kann die Hand des Meisters sofort erkennen! Ich werde es morgen ausprobieren, um zu sehen, was dabei herauskommt.

Aleksey Vyazmikin 2021.04.20 23:56 #13

Dmitry Fedoseev:

Irgendwie...

Ich habe angefangen, den Code auszuprobieren und ein künstliches Beispiel erstellt - das Array ausgefüllt

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;

Ich hab's:

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

Das heißt, wir haben eine Variante, aber wir erwarten auch eine andere Variante.

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

Ist es möglich, dem Algorithmus beizubringen, sie auch zu finden?

Dmitry Fedoseev 2021.04.21 04:32 #14

Aleksey Vyazmikin:

Ich habe angefangen, den Code auszuprobieren und ein künstliches Beispiel erstellt - das Array ausgefüllt

Ich hab's:

Das heißt, wir haben eine Variante, aber wir erwarten auch eine andere Variante.

Kann der Algorithmus lernen, sie auch zu finden?

Und die Variante "0-1 3-6 7-9" ist nicht besser als die Variante "0 - 0-1 2-5 7-9" - beide gehen von 0 bis 1 und haben jeweils 2 Auslassungen der Länge 1.

In diesem Fall gibt es zwei Möglichkeiten:

1 - machen Sie dasselbe, aber ab dem Ende des Satzes von Überspringen.

2 - suchen Sie nicht gleich nach dem nächstgelegenen Segment, sondern mit einer Toleranz. Aber in diesem Fall werden es noch mehr sein, wenn es viele Daten und viele Andocksequenzen gibt.

Nach Variante 1 werden Sie jedoch damit beginnen wollen, Ketten aus allen möglichen Ausgangspositionen zu bilden. Das ist richtig, aber der Arbeitsaufwand für den Algorithmus steigt dadurch erheblich.

Ja! Es ist notwendig, die Konstruktion von Varianten von jedem der Segmente der Ausgangsmenge aus zu beginnen und die Konstruktion bis zum Anfang und Ende fortzusetzen.

Feuervogel EA Maschinelles Lernen im Handel: Schaffung einer positiven IO

Aleksey Vyazmikin 2021.04.21 06:37 #15

Dmitry Fedoseev:

Und die Option "0-1 3-6 7-9" ist nicht besser als die Option "0 - 0-1 2-5 7-9" - beide gehen von 0 bis 1 und haben jeweils 2 Auslassungen der Länge 1.

In diesem Fall sind sie gleich, da stimme ich zu, aber sie sind unterschiedlich, und gemäß der Aufgabenstellung müssen wir die Summe ihrer Punkte schätzen, und bis wir eine Linie bilden, werden wir die kombinierte Punktzahl aller Segmente nicht kennen.

Dmitry Fedoseev:

Nach Option 1 besteht jedoch der Wunsch, mit der Konstruktion von Zeichenketten von allen möglichen Ausgangspositionen aus zu beginnen. Das ist richtig, aber der Arbeitsaufwand für den Algorithmus steigt dadurch erheblich.

Ja! Es ist notwendig, die Konstruktion von Varianten von jedem der Segmente der Ausgangsmenge aus zu beginnen und die Konstruktion bis zum Anfang und Ende fortzusetzen.

Das scheint mir auch die richtigere Strategie zu sein! Ich denke jedoch, dass es möglicherweise doppelte Varianten gibt.

Können Sie helfen, indem Sie einen Code schreiben?

Sie müssen immer den Fehler, Irrtümer, Fragen T3

Dmitry Fedoseev 2021.04.21 09: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;
   }   
}

Da jede Variante die Segmente nun in zwei Arrays speichert, können diese der Einfachheit halber mit der MethodeCombine() zu einem Array zusammengefasst werden.

Aleksey Vyazmikin 2021.04.22 16:01 #17

Dmitry Fedoseev:

Da nun jede Variante die Segmente in zwei Arrays speichert, kann man sie mit der MethodeCombine() zu einem Array zusammenfassen, um es bequemer zu machen.

Dmitry, vielen Dank für den neuen Algorithmus!

Ja, es gibt in der Tat sehr viele Kopien.

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

So wie ich es verstehe, können sie nicht gezählt werden. Ich hatte es nicht geschafft, auf die Kombination von 1000 Elementen zu warten - meinem Netbook ging der Speicher aus :(

Und ist es möglich, beim Hinzufügen eines Segments nicht alle Kombinationen zu verwenden, sondern nur eine bestimmte Anzahl von möglichen im aktuellen Schritt, z. B. die besten 10?

Fragen von Neueinsteigern zu Fehler, Irrtümer, Fragen Stochastisch

Dmitry Fedoseev 2021.04.22 16:25 #18

Aleksey Vyazmikin:

Dmitry, vielen Dank für den neuen Algorithmus!

Ja, es gibt tatsächlich viele Kopien.

Soweit ich weiß, kann man sie nicht zählen. Ich konnte die Kombination von 1000 Elementen nicht abwarten - meinem Netbook ging der Speicher aus :(

Ist es möglich, beim Hinzufügen eines Segments nicht alle Kombinationen zu verwenden, sondern nur eine bestimmte Anzahl von möglichen im aktuellen Schritt, z. B. die besten 10?

Um zu wissen, dass sie die besten sind, muss man sie mit anderen vergleichen, d. h. man muss sie erst einmal alle haben. Eine andere Sache ist, den Algorithmus irgendwie zu optimieren, aber ich habe nicht das Ziel, mein Leben diesem Algorithmus zu widmen).

Vielleicht entscheiden Sie sich für das Kriterium der Suffizienz und erhalten zunächst alle Optionen, ausgehend von nur einem Segment, das zufällig ausgewählt wird, und so weiter, bis eine zufriedenstellende Option erscheint.

Und die zweite Option kann beschleunigt werden - um das Array mit Varianten nicht ein Element zu einer Zeit, sondern mehrere Dutzend Elemente auf einmal zu skalieren, und am Ende zu trimmen es.

Expert Advisor <CONSULTING PRODUCT Eine Liste von Programmierern, Von der Theorie zur

Aleksey Vyazmikin 2021.04.22 17:48 #19

Dmitry Fedoseev:

Um zu wissen, dass sie die besten sind, muss man sie mit anderen vergleichen, d. h. man muss sie erst einmal alle haben. Eine andere Sache ist, den Algorithmus irgendwie zu optimieren, aber ich habe nicht das Ziel, mein Leben diesem Algorithmus zu widmen).

Ich spreche über ein einzelnes Segment, sagen wir, es hat einen Koeffizienten, um seine Qualität zu bewerten, dann verzweigen wir nach jeder Iteration, zum Beispiel, nur auf die Top 10 dieser Koeffizienten.

Dmitry Fedoseev:

Vielleicht entscheiden Sie sich für ein Suffizienzkriterium und erhalten zunächst alle Varianten, ausgehend von nur einem Segment, das zufällig ausgewählt wird, und so weiter, bis eine zufriedenstellende Variante erscheint.

Leider ist die "Hinlänglichkeit" hier schwer einzuschätzen - dazu muss man eine Norm kennen, dann kann man daraus eine Toleranz definieren, und ich habe keine Norm.

Dmitry Fedoseev:

Und die zweite Option kann beschleunigt werden - zu skalieren Array mit Optionen nicht ein Element zu einer Zeit, aber mehrere Dutzend Elemente, und am Ende der es auszurichten.

Ich bin mir nicht ganz sicher, was Sie mit der Parallelisierung mit OpenCL meinen?

EURUSD - Trends, Prognosen Experiment Warum lese ich die

Dmitry Fedoseev 2021.04.22 18:24 #20

Aleksey Vyazmikin:

1. Ich spreche von einem einzelnen Segment, sagen wir, es hat einen Koeffizienten, um seine Qualität zu bewerten, dann verzweigen wir nach jeder Iteration zum Beispiel nur zu den Top 10 dieser Koeffizienten.

2. Leider lässt sich die "Hinlänglichkeit" hier nur schwer einschätzen - man muss die Benchmark kennen, dann kann man daraus die Toleranz bestimmen, und ich habe keine Benchmark.

3. ich bin mir nicht ganz sicher, was Sie mit Parallelisierung mittels OpenCL meinen?

1. wo liegt dieser Koeffizient?

2. Was ist mit Punkt 1?

3. Nein, es ist einfacher. Okay, ich werde versuchen, es morgen zu beschleunigen.

Algorithmus zum Kombinieren von Bereichen eines Segments - Hilfe zum Erstellen - Seite 2