Optimisation of algorithms. - page 2

New comment
 

And so:

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

?

 

I have accelerated it by a factor of one and a half.

// Рулетка.
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;    
}

Zero (in your case "coefficient") is just as stupidly chosen (almost "out of the blue").

// As a potential user, I suggest that you still think carefully about this point.

// I have reasonable thoughts on the subject, we can discuss it at our leisure.

If you put 1.1 instead of 1 when calculating zero, the results (numeric, not speed) will be exactly the same as in your case.

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)       ----------------
Files:
mdRoulette.mq5  3 kb
 

Is such a question https://www.mql5.com/ru/forum/6343/page5#comment_177533 appropriate in this thread?

 
MetaDriver:

1. Accelerated by a factor of one and a half.

2. have reasonable thoughts on the subject, can be discussed at leisure.

1. good solution, thanks. The gist is the same as mine, but you've done with one marking array instead of two - hence the speed gain. Looks like you couldn't do any better.

Unless you take the markup out of the loop:

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

:)

2. Sure.

 
Yedelkin:

Is such a question https://www.mql5.com/ru/forum/6343/page5#comment_177533 appropriate in this thread?

Yes, these are algorithmic questions. However, that thread has already answered it.
 

And like this...

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

The input is an array with sector sizes( nosorting of the array is required).

Why you have a negative number in the array there - I don't understand. Probably sector partitioning?

 
joo:

Good solution, thanks. The idea is the same as mine, but you've made do with one marking array instead of two - hence the speed gain. Looks like you couldn't do any better.

The gain has been achieved by many small improvements. You can also speed up a little bit more "small stuff".

For example, if you reduce the second parameter by one beforehand when calling the roulette:

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

you still get a quite measurable difference.

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 мс - Время исполнения

But that's not all. The real "big win" is ahead. Wait, I'll debug it and post it.

// there is a small bug - already fixed.

 
Integer:

And like this...

1. an array with sector sizes is input( nosorting of the array is required).

2. Why you have a negative number in the array there - I don't get it. Probably sector partitioning?

1. the problem is that the input is raw data. They just need to be converted into sector sizes as the game goes on. That's part of the problem. :)

2. No way. Just torture joo, he'll admit it if you push hard enough. I'm debugging now. ;)

 
And this is a real high-speed Quik-roulette. 
// Рулетка.
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)      ----------------
You were not impressed by the result?

That's naive. ;) Increase the input array 10,000 times - then you're bound to be impressed.

--

I'm waiting for comparative tests // on large array.

;)

Files:
mdQuikRoulette.mq5  3 kb
 
MetaDriver:

I'm waiting for comparative tests // on a large array.

Can't seem to wait... :)

I'll have to do it myself again:

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


At the same time I've combed it all in the class and put into CRoulette.Reset();

12345678910
New comment