Kth selection routine - Floyd Algorithm 489

6

Recentemente mi sono imbattuto in una promettente procedura di selezione Kth che, a quanto pare, supera la selezione rapida della routine Floyd, Rivest Select. Questo articolo di Wikipedia fornisce una versione pseudocodice che ho provato a tradurre in C.

Il link all'attuale carta con il codice in ALGOL.

Questa è la mia traduzione del codice

void 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 n, i, j, ll, rr;
    int s, sd;
    float z, t;

    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 > 600)
        {
            n = right - left + 1;
            i = k - left + 1;
            z = log(n);
            s = 0.5 * exp(2 * z/3);
            sd = 0.5 * sqrt(z * s * (n - s)/n) * sign(i - n/2);
            ll = max(left, k - i * s/n + sd);
            rr = min(right, k + (n - i) * s/n + sd);
            select(array, ll, rr, k);
        }
        // partition the elements between left and right around t
        t = array[k];
        i = left;
        j = right;

        F_SWAP(array[left],array[k]);

        if (array[right] > t)
        {
            F_SWAP(array[right],array[left]);//swap array[right] and array[left]
        }

        while (i < j)
        {
            F_SWAP(array[i],array[j]);
            i = i + 1;
            j = j -1;

            while (array[i] < t)
            {
                i = i + 1;
            }

            while (array[j] > t)
            {
                j = j - 1;
            }
        }

        if (array[left] == t)
        {
            F_SWAP (array[left], array[j])
        }             
        else
        {
            j = j + 1;
            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;
        }
    }
 #undef sign
 #undef F_SWAP
}

Sembra funzionare bene, tuttavia, ho molte domande su questa routine che mi confondono.

Innanzitutto, in base a ciò che ho letto, questa routine dovrebbe essere più veloce degli algoritmi di selezione QuickSelect e Wirth di Hoare. Tuttavia, nel mio codice sembra essere più lento.

Che cosa fanno esattamente i numeri magici 600 e .5? Lo pseudocodice spiega che sono costanti arbitrarie per ridurre al minimo il tempo di esecuzione. Era specifico del linguaggio ALGOL?

Quali sono esattamente il log, l'esponenziale, la radice quadrata e l'esecuzione di Sigma per trovare effettivamente la posizione K?

Penso che il problema di prestazioni che sto riscontrando con la mia traduzione di questa routine sia probabilmente dovuto all'esponente e al logaritmo.

    
posta Andy Dansby 23.05.2015 - 14:27
fonte

1 risposta

7

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.

    
risposta data 24.05.2015 - 23:12
fonte

Leggi altre domande sui tag