アルゴリズムの最適化

Serj 2012.04.04 21:48 #11

といった具合に。

//————————————————————————————————————————————————————————————————
int Selection()
{
  int    u=0;
  double p=RNDfromCI(Population[0][0]-Population[0][SizeOfPop-1]);

   for(u=0;u<SizeOfPop;u++)   if(Population[0][u+1]<=p)  break;
  
  return(u);
}
//————————————————————————————————————————————————————————————————

?

Vladimir Gomonov 2012.04.04 22:56 #12

1.5倍に加速させました。

// Рулетка.
int Roulette(double &array[], int SizeOfPop)
{
  double p, sum=0, zero = array[SizeOfPop-1] - 1.;
  for(int i=0; i<SizeOfPop; i++)
  {
    select[i] = sum += array[i] - zero;
  }
  // бросим "шарик"
  p=RNDfromCI(0,sum);
  // посмотрим, на какой сектор упал "шарик"
  for(int u=0;u<SizeOfPop;u++)   if(select[u]>=p)  return(u);
  return -1;    
}

ゼロ（あなたの場合は「係数」）は、まさに愚かな選択（ほとんど「青天の霹靂」）です。

// この点については、やはり潜在的なユーザーとして、よく考えてみることをお勧めします。

// 合理的な考えがあるのだから、ゆっくり議論すればいい。

ゼロの計算時に1ではなく1.1を入れると、結果（速度ではなく数値）はあなたのケースと全く同じになります。

2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     ----------------
2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     h0 = 38621212;  38.621212
2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     h1 = 31685827;  31.685827
2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     h2 = 17770070;  17.77007
2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     h3 = 7335400;  7.3354
2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     h4 = 4203603;  4.203603
2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     h5 = 383888;  0.383888
2012.04.05 02:30:17     mdRoulette (GBOTUSDMUR16Apr2012,M1)     10374 мс - Время исполнения
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       ----------------
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       h0 38635063 38.635063
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       h1 31678144 31.678144
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       h2 17759576 17.759576
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       h3 7333799 7.333799
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       h4 4208364 4.208364
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       h5 385054 0.385054
2012.04.05 02:30:00     Roulette (GBOTUSDMUR16Apr2012,M1)       16036 мс - Время исполнения
2012.04.05 02:29:24     Roulette (GBOTUSDMUR16Apr2012,M1)       ----------------

ファイル:

mdRoulette.mq5 3 kb

Yedelkin 2012.04.05 13:51 #13

このスレッドでは、そのような質問https://www.mql5.com/ru/forum/6343/page5#comment_177533 が適切なのでしょうか？

Andrey Dik 2012.04.05 14:43 #14

MetaDriver:

1.1.5倍に加速。

2.合理的な考えを持っている、ゆっくり議論できる。

1.良い解決策ですね、ありがとうございます。要は私と同じなのですが、マーキング配列を2つから1つにしたことで、スピードが上がったのですね。これ以上は無理なようですね。

マークアップをループから外せば別ですが。

for(int i=0; i<SizeOfPop; i++)
  {
    select[i] = sum += array[i] - zero;
  }

:)

2.もちろんです。

Andrey Dik 2012.04.05 14:44 #15

Yedelkin:

このスレッドでは、そのような質問https://www.mql5.com/ru/forum/6343/page5#comment_177533 が適切なのでしょうか？

そう、これはアルゴリズムに関する質問なのです。しかし、そのスレッドではすでに答えが出ています。

Dmitry Fedoseev 2012.04.05 14:59 #16

そして、このように...

void Test(){
   double SectorSize[]={22,3,2,1,7,12};
   
   double tc[];
   ArrayResize(tc,ArraySize(SectorSize));
   for(int i=0;i<100000;i++){
      tc[Roulete(SectorSize)]++;
   }
   int m=tc[ArrayMinimum(tc)];
   string str="";
      for(i=0;i<ArraySize(SectorSize);i++){
         tc[i]/=m;
         str=str+DoubleToStr(tc[i],2)+" ";
      }      
   Alert(str);
}

int Roulete(double & SectorSize[]){ // На входе размеры секторов
   double Sum=0;
   int i;
   for(i=ArraySize(SectorSize);i>=0;i--){
      Sum+=SectorSize[i];
   }
   for(i=ArraySize(SectorSize);i>0;i--){
      if(MathRand()<SectorSize[i]/Sum*32767){
         return(i);
      }
      Sum-=SectorSize[i];
   }
   return(i);   
   
}

入力はセクタサイズの配列です（配列のソートは必要ありません）。

配列の中になぜマイナスの数字が入っているのか、それがわからないのです。おそらくセクターパーティショニング？

Vladimir Gomonov 2012.04.05 16:41 #17

joo:

良い解決策です、ありがとうございます。アイデアは私と同じですが、マーキングアレイを2つから1つにすることで、スピードアップを実現しています。これ以上は無理なようですね。

この利得は、多くの小さな改善によって達成されたものです。また、もう少し「小さなこと」をスピードアップすることも可能です。

例えば、ルーレットを呼び出す際に、あらかじめ第2パラメータを1つ減らしておくと。

int Roulette(double &array[], int MaxIndex)
{
  double p, sum=0, zero = array[MaxIndex] - 1.1;
  for(int i=0; i!=MaxIndex; i++)
  {
    select[i] = sum += array[i] - zero;
  }
  // бросим "шарик"
  p=RNDfromCI(0,sum);
  // посмотрим, на какой сектор упал "шарик"
  for(int u=0;u!=MaxIndex;u++) 
  {  if(select[u]>=p)  return(u);}
  return -1;    
}

それでもかなり大きな差が出ます。

2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      ----------------
2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      h0 = 38784632;  38.784632
2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      h1 = 31791177;  31.791177
2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      h2 = 17835360;  17.83536
2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      h3 = 7365937;  7.365937
2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      h4 = 4222894;  4.222894
2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      h5 = 0;  0.0
2012.04.05 18:35:31     mdQuikRoulette (USDCHF,M1)      9828 мс - Время исполнения
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  ----------------
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  h0 = 38627427;  38.627427
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  h1 = 31682853;  31.682853
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  h2 = 17763763;  17.763763
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  h3 = 7334465;  7.334465
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  h4 = 4206490;  4.20649
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  h5 = 385002;  0.385002
2012.04.05 18:33:30     mdRoulette (USDCHF,M1)  10359 мс - Время исполнения

しかし、それだけではありません。本当の意味での「大勝利」はこの先です。待ってください、デバッグして投稿しますから。

// ここで小さなバグがあり、すでに修正されています。

Vladimir Gomonov 2012.04.05 16:45 #18

Integer:

そして、このように...

1. セクタサイズの配列が入力される（配列のソートは必要ない）。

2.配列の中になぜマイナスの数字が入っているのか、それがわからない。おそらくセクターパーティショニング？

1.入力が生データであることが問題である。ゲームの進行に合わせて、セクターサイズに変換していけばいいのです。そこが問題なんです。:)

2.まさかジュを拷問しろ強く押せば認めるだろう今デバッグしてるんだ;)

Vladimir Gomonov 2012.04.05 18:07 #19

そして、これが本当の速射式クィックルーレットです。

// Рулетка.
int Roulette(double &array[], int r)
{
  double p, sum=0, zero = array[r++] - 1.1;
  for(int i=0; i!=r; i++)
  {
    select[i] = sum += array[i] - zero;
  }
  p=RNDfromCI(0,sum);
  int l=0, m=(l+(--r))>>1;
  while(l<r) 
    {
     if(select[m]>=p) r=m;
     else l=m+1; 
     m=(l+r)>>1;
    }
  return m;    
}

2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      ----------------
2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      h0 = 38632491;  38.632491
2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      h1 = 31675215;  31.675215
2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      h2 = 17769223;  17.769223
2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      h3 = 7337466;  7.337466
2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      h4 = 4202088;  4.202088
2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      h5 = 383517;  0.383517
2012.04.05 19:58:24     mdQuikRoulette (USDCHF,M1)      11529 мс - Время исполнения
2012.04.05 19:57:06     mdQuikRoulette (USDCHF,M1)      ----------------

その結果、感動はなかったのですか？

それは甘えだ。;) 入力配列を10,000倍にする - そうすれば、感動すること間違いなしです。

--

大きなアレイでの比較テストを待っています。

;)

ファイル:

mdQuikRoulette.mq5 3 kb

Vladimir Gomonov 2012.04.05 19:35 #20

MetaDriver:

大きな配列での比較テストを // 待っています。

待ちきれないようだ...。:)

また自分でやるしかないですね。

2012.04.05 22:04:25     mdQuikRoulette_CompareTest (USDCHF,M1)  h0 = 2105;  0.02105
2012.04.05 22:04:25     mdQuikRoulette_CompareTest (USDCHF,M1)  h1 = 1782;  0.01782
2012.04.05 22:04:25     mdQuikRoulette_CompareTest (USDCHF,M1)  h2 = 2189;  0.02189
2012.04.05 22:04:25     mdQuikRoulette_CompareTest (USDCHF,M1)  h3 = 1793;  0.01793
2012.04.05 22:04:25     mdQuikRoulette_CompareTest (USDCHF,M1)  h4 = 1803;  0.01803
2012.04.05 22:04:25     mdQuikRoulette_CompareTest (USDCHF,M1)  h5 = 2075;  0.02075
2012.04.05 22:04:25     mdQuikRoulette_CompareTest (USDCHF,M1)  1825 мс - Время исполнения QuickRoulette
2012.04.05 22:04:23     mdQuikRoulette_CompareTest (USDCHF,M1)  h0 = 2104;  0.02104
2012.04.05 22:04:23     mdQuikRoulette_CompareTest (USDCHF,M1)  h1 = 1812;  0.01812
2012.04.05 22:04:23     mdQuikRoulette_CompareTest (USDCHF,M1)  h2 = 2088;  0.02088
2012.04.05 22:04:23     mdQuikRoulette_CompareTest (USDCHF,M1)  h3 = 1839;  0.01839
2012.04.05 22:04:23     mdQuikRoulette_CompareTest (USDCHF,M1)  h4 = 1769;  0.01769
2012.04.05 22:04:23     mdQuikRoulette_CompareTest (USDCHF,M1)  h5 = 2089;  0.02089
2012.04.05 22:04:23     mdQuikRoulette_CompareTest (USDCHF,M1)  183207 мс - Время исполнения Roulette

同時にクラスで全部梳いてCRoulette.Reset()に入れました。

ファイル:

mdQuikRoulette_CompareTest.mq5 4 kb

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