Dopo essermi agitato un po 'con il codice, ho ottenuto risultati migliori. Sono tornato al documento originale e ho ignorato la pagina di Wikipedia. Ho confrontato l'algoritmo con altre routine di selezione rapida con ottimi risultati.
Ok, ecco i metodi con cui ho giocato. Nota che questi sono per virgola mobile e anche che ho cambiato il mio metodo da un vuoto.
Selezione rapida ver 1
float quickselect(float *arr, int length, int kTHvalue)
{
#define F_SWAP(a, b) { tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; }
int i, st;
float tmp;
for (st = i = 0; i < length - 1; i++)
{
if (arr[i] > arr[length-1]) continue;
F_SWAP(i, st);
st++;
}
F_SWAP(length-1, st);
#undef F_SWAP
return kTHvalue == st ?arr[st]
:st > kTHvalue ? quickselect(arr, st, kTHvalue)
: quickselect(arr + st, length - st, kTHvalue - st);
}
Penso che la fonte originale sia il codice Rosetta. Funziona piuttosto rapidamente, ma dopo aver visto alcuni altri codici, è stata scritta un'altra funzione di selezione rapida.
Selezione rapida ver 2
float quickselect2(float *arr, int length, int kthLargest)
{
#define F_SWAP(a, b) { tmp = a; a = b; b = tmp; }
int left = 0;
int right = length - 1;
int pos;
float tmp;
for (int j = left; j < right; j++)
{
float pivot = arr[kthLargest];
F_SWAP(arr[kthLargest], arr[right]);
for (int i = pos = left; i < right; i++)
{
if (arr[i] < pivot)
{
F_SWAP(arr[i], arr[pos]);
pos++;
}
}
F_SWAP(arr[right], arr[pos]);
#undef F_SWAP
if (pos == kthLargest) break;
if (pos < kthLargest) left = pos + 1;
else right = pos - 1;
}
return arr[kthLargest];
}
Mi sono guardato intorno e ho trovato un altro rapido intervento che aveva delle buone promesse. È stata una selezione rapida con una mediana di 3
float quickselect_MO3(float *arr, const int length, const int kTHvalue)
{
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
unsigned int low = 0;
unsigned int high = length - 1;
for (unsigned int j = low; j < high; j++)
{
if (high <= low) // One element only
return arr[kTHvalue];
if (high == low + 1)
{ // Two elements only
if (arr[low] > arr[high])
F_SWAP(arr[low], arr[high]);
return arr[kTHvalue];
}
//median of 3
int middle = (low + high) / 2;
if (arr[middle] > arr[high])
F_SWAP(arr[middle], arr[high]);
if (arr[low] > arr[high])
F_SWAP(arr[low], arr[high]);
if (arr[middle] > arr[low])
F_SWAP(arr[middle], arr[low]);
// Swap low item (now in position middle) into position (low+1)
F_SWAP(arr[middle], arr[low+1]);
// Nibble from each end towards middle, swapping items when stuck
unsigned int ll = low + 1;
unsigned int hh = high - 1;//unsigned int hh = high;
for (unsigned int k = ll; k < hh; k++)
{
do ll++; while (arr[low] > arr[ll]);
do hh--; while (arr[hh] > arr[low]);
if (hh < ll)
break;
F_SWAP(arr[ll], arr[hh]);
}
// Swap middle item (in position low) back into correct position
F_SWAP(arr[low], arr[hh]);
// Re-set active partition
if (hh <= kTHvalue)
low = ll;
if (hh >= kTHvalue)
high = hh - 1;
}
#undef F_SWAP
}
La mediana di 3 è veloce e piuttosto impressionante.
Successivamente, con il mio riscritto (dall'ALGOL originale convertito nel foglio) Routine Floyd.
la funzione mediana Floyd ver 1
float select(float array[], int left, int right, int k)
{
#define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
int i;
right = right - 1;
while (right > left)
{
// use select recursively to sample a smaller set of size s
// the arbitrary constants 600 and 0.5 are used in the original
// version to minimize execution time
if (right - left > right)
{
int n = right - left + 1;
i = k - left + 1;
float z = logf(n);
float s = 0.5 * expf(2 * z/3);
float sd = 0.5 * sqrtf(z * s * (n - s) / n) * sign(i - n / 2);
int ll = max(left, k - 1 * s/n + sd);
int rr = min(right, k + (n - 1) * s/n + sd);
select(array, ll, rr, k);
}
// partition the elements between left and right around t
float t = array[k];
i = left;
int j = right;
F_SWAP(array[left],array[k]);
if (array[right] > t)
{
F_SWAP(array[right],array[left]);
}
while (i < j)
{
F_SWAP(array[i],array[j]);
i++;
j--;
while (array[i] < t)
{
i++;
}
while (array[j] > t)
{
j--;
}
}
if (array[left] == t)
{
F_SWAP (array[left], array[j])
}
else
{
j++;
F_SWAP (array[j],array[right])
}
// adjust left and right towards the boundaries of the subset
// containing the (k - left + 1)th smallest element
if (j <= k)
{
left = j + 1;
}
if (k <= j)
{
right = j - 1;
}
}
return array[k];
#undef sign
#undef F_SWAP
}
Infine, ho deciso di rimuovere le funzioni Log, Esponente e radice quadrata e ho ottenuto lo stesso risultato e anche un tempo migliore.
la funzione mediana Floyd ver 2
float select1(float array[], int left, int right, int k)
{
#define sign(x) ((x > 0.0) ? 1 : ((x < 0.0) ? (-1) : 0))
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
int i;
right = right - 1;
while (right > left)
{
// use select recursively to sample a smaller set of size s
// the arbitrary constants 600 and 0.5 are used in the original
// version to minimize execution time
if (right - left > right)
{
int n = right - left + 1;
i = k - left + 1;
int s = (2 * n / 3);
int sd = (n * s * (n - s) / n) * sign(i - n / 2);
int ll = max(left, k - i * s / n + sd);
int rr = min(right, k + (n - i) * s / n + sd);
select1(array, ll, rr, k);
}
// partition the elements between left and right around t
float t = array[k];
i = left;
int j = right;
F_SWAP(array[left],array[k]);
if (array[right] > t)
{
F_SWAP(array[right],array[left]);
}
while (i < j)
{
F_SWAP(array[i],array[j]);
i++;
j--;
while (array[i] < t)
{
i++;
}
while (array[j] > t)
{
j--;
}
}
if (array[left] == t)
{
F_SWAP (array[left], array[j])
}
else
{
j++;
F_SWAP (array[j],array[right])
}
// adjust left and right towards the boundaries of the subset
// containing the (k - left + 1)th smallest element
if (j <= k)
{
left = j + 1;
}
if (k <= j)
{
right = j - 1;
}
}
return array[k];
#undef sign
#undef F_SWAP
}
Ecco un grafico dei risultati
EDITHocodificatolaroutineFloydconlamedianadi3eaggiornatoilgrafico.Valutaall'incircalastessavelocitàdellaselezionerapidaconMedianadi3,leggermentepiùlento.Meritaunpo'piùdiesplorazione.
floatselect3(floatarray[],intleft,intright,intk){#definesign(x)((x>0.0)?1:((x<0.0)?(-1):0))#defineF_SWAP(a,b){floattemp=(a);(a)=(b);(b)=temp;}inti;right=right-1;while(right>left){if(array[k]<array[left])F_SWAP(array[left],array[k]);if(array[right]<array[left])F_SWAP(array[left],array[right]);if(array[right]<array[k])F_SWAP(array[k],array[right]);if(right-left>right){intn=right-left+1;i=k-left+1;ints=(2*n/3);intsd=(n*s*(n-s)/n)*sign(i-n/2);intll=max(left,k-i*s/n+sd);intrr=min(right,k+(n-i)*s/n+sd);select1(array,ll,rr,k);}//partitiontheelementsbetweenleftandrightaroundtfloatt=array[k];i=left;intj=right;F_SWAP(array[left],array[k]);if(array[right]>t){F_SWAP(array[right],array[left]);}while(i<j){F_SWAP(array[i],array[j]);i++;j--;while(array[i]<t){i++;}while(array[j]>t){j--;}}if(array[left]==t){F_SWAP(array[left],array[j])}else{j++;F_SWAP(array[j],array[right])}//adjustleftandrighttowardstheboundariesofthesubset//containingthe(k-left+1)thsmallestelementif(j<=k){left=j+1;}if(k<=j){right=j-1;}}returnarray[k];#undefsign#undefF_SWAP}
Comepuoivedere,laroutinediFloydèpiùvelocediunaqualsiasidelleselezionirapidediversadallaversioneconlamedianadi3.Nonvedoperchélamedianadi3nonpossaessereaggiuntaallaroutinediFloydeioguardaquellodopo.PerquantoriguardalaroutineFloyd,ovviamenterimuovendoilloginvirgolamobile,lefunzioniexpesqrtacceleralaroutine.
NonhoancoracapitoperchéFloydl'abbiamessolìinprimoluogo.
modifica6-7-15Eccolaversionenonricorsiva,vieneeseguitaallastessavelocitàdellaversionericorsiva.
floatselect7MO3(floatarray[],constintlength,constintkTHvalue){#definesign(x)((x>0)?1:((x<0)?(-1):0))#defineF_SWAP(a,b){floattemp=(a);(a)=(b);(b)=temp;}intleft=0;inti;intright=length-1;intrr=right;intll=left;while(right>left){if(array[kTHvalue]<array[left])F_SWAP(array[left],array[kTHvalue]);if(array[right]<array[left])F_SWAP(array[left],array[right]);if(array[right]<array[kTHvalue])F_SWAP(array[kTHvalue],array[right]);if((right-left)>kTHvalue){intn=right-left+1;i=kTHvalue-left+1;ints=(2*n/3);intsd=(n*s*(n-s)/n)*sign(i-n);ll=max(left,kTHvalue-i*s/n+sd);rr=min(right,kTHvalue+(n-i)*s/n+sd);}//partitiontheelementsbetweenleftandrightaroundtfloatt=array[kTHvalue];i=left;intj=right;F_SWAP(array[left],array[kTHvalue]);if(array[right]>t){F_SWAP(array[right],array[left]);}while(i<j){F_SWAP(array[i],array[j]);i++;j--;while(array[i]<t){i++;}while(array[j]>t){j--;}}if(array[left]==t){i--;F_SWAP(array[left],array[j])}else{j++;F_SWAP(array[j],array[right])}//adjustleftandrighttowardstheboundariesofthesubset//containingthe(k-left+1)thsmallestelementif(j<=kTHvalue){left=j+1;}elseif(kTHvalue<=j){right=j-1;}}returnarray[kTHvalue];#undefsign#undefF_SWAP}
modifica6-13-15
Hosperimentatounpo'dipiùconlaroutinediselezioneFloydehoiniziatoaconfrontarelasuaroutineconlaroutinediselezioneN.Wirth.Vennefuoriun'idea,cosasarebbesuccessoseavessicombinatolasuaroutineconlaroutinediFloyd.Questoèquellochemièvenutoinmente.
floatFloydWirth_kth(floatarr[],constintlength,constintkTHvalue){#defineF_SWAP(a,b){floattemp=(a);(a)=(b);(b)=temp;}#defineSIGNUM(x)((x)<0?-1:((x)>0?1:(x)))intleft=0;intright=length-1;intleft2=0;intright2=length-1;//while(left<right)while(left<right){if(arr[right2]<arr[left2])F_SWAP(arr[left2],arr[right2]);if(arr[right2]<arr[kTHvalue])F_SWAP(arr[kTHvalue],arr[right2]);if(arr[kTHvalue]<arr[left2])F_SWAP(arr[left2],arr[kTHvalue]);intrightleft=right-left;if(rightleft<kTHvalue){intn=right-left+1;intii=kTHvalue-left+1;ints=(n+n)/3;intsd=(n*s*(n-s)/n)*SIGNUM(ii-n/2);intleft2=max(left,kTHvalue-ii*s/n+sd);intright2=min(right,kTHvalue+(n-ii)*s/n+sd);}floatx=arr[kTHvalue];while((right2>kTHvalue)&&(left2<kTHvalue)){do{left2++;}while(arr[left2]<x);do{right2--;}while(arr[right2]>x);//F_SWAP(arr[left2],arr[right2]);F_SWAP(arr[left2],arr[right2]);}left2++;right2--;if(right2<kTHvalue){while(arr[left2]<x){left2++;}left=left2;right2=right;}if(kTHvalue<left2){while(x<arr[right2]){right2--;}right=right2;left2=left;}if(arr[left]<arr[right])F_SWAP(arr[right],arr[left]);}#undefF_SWAP#undefSIGNUMreturnarr[kTHvalue];}
Ladifferenzadivelocitàèincredibile(almenoperme).Eccoungraficochemostralevelocitàdellevarieroutine.