Modo discussione | Modo lineare

Gabriele · 16-08-2011 10:59

Radix Sort (con Counting Sort) vs Quick Sort

Ecco il mio test con 9999 numeri Fermosu

In modalità Debug:

quick sort 0.001
Radix Sort 0.223

In modalità RS:
quick sort un numero inferiore al millesimo di secondo 0.000(?)
Radix Sort 0.019
(Su una cpu Q6600)

ecco il code:

Codice:

#include <bitset>

#include <iostream>

#include <Windows.h>

using namespace std;

long GetTime(){

        SYSTEMTIME systemTime;

        GetSystemTime( &systemTime );

        FILETIME fileTime;

        SystemTimeToFileTime( &systemTime, &fileTime );

        ULARGE_INTEGER uli;

         uli.LowPart = fileTime.dwLowDateTime;

         uli.HighPart = fileTime.dwHighDateTime;

        ULONGLONG systemTimeIn_ms( uli.QuadPart/10000 );

         return (long)systemTimeIn_ms;

    }

#define ARRAY_TO0(v,n)  memset(v, 0, sizeof(*(v)) * n);

void CountingSort(int *lista,int *risultato,int lenArr,int nCifra){

    int temp[2] = {0};    

    bitset<32> tempint;

    for (int x = 0; x<lenArr;x++){

        tempint=lista[x];

        temp[tempint[nCifra]] = temp[tempint[nCifra]]+1;

    }

        temp[1]=temp[1]+temp[0];

    for (int x = lenArr-1; x>-1;x--){

        tempint=lista[x];

        risultato[temp[tempint[nCifra]]-1] = lista[x];

        temp[tempint[nCifra]] = temp[tempint[nCifra]]-1;

    }

}

void RadixSort(int *lista,int *risultato,int lenArr,int nCifre){

    for (int x=0;x<nCifre;x++){

            CountingSort(lista,risultato,lenArr,x);

            for (int x = 0; x<lenArr; x++){

                lista[x]= risultato[x];

            }

    }

}

void quicksort(int *A, int inf, int sup){

    int perno = A[(inf+sup)/2], h = inf, k = sup;

    while (h<=k){

        while(A[h]<perno) h++;

        while(A[k]>perno) k--;

        if (h>k) break;

        h++;

        k--;

    }

    if (inf < k) quicksort(A,inf,k);

    if (h < sup) quicksort(A,h,sup);

}

int main(){

    int size=9999;

    int *risultato = new int[size];

    int *lista = new int[size];

    for (int x = 0; x<size; x++){

        lista[x]=rand()%size+1;

    }

 long stime,etime;

 stime=GetTime();

    ARRAY_TO0(risultato,size);

    RadixSort(lista,risultato,size,14); //9999 n binario richiede 14 cifre

 etime=GetTime();

        cout<<"\n RadixSort time:"<<(double)(etime-stime)/1000.0<< " etime:"<<etime<< " stime:" <<stime <<"\n";        

    for (int x = 0; x<size; x++){

        lista[x]=rand()%size+1;

    }

 stime=GetTime();

    quicksort(lista,0,size);

 etime=GetTime();

        cout<<"\n Quicksort time:"<<(double)(etime-stime)/1000.0<< " etime:"<<etime<< " stime:" <<stime <<"\n";        

    system("PAUSE");

   delete [] lista;

   delete [] risultato;

}

tutto questo per ordinare, quando viene modificato l'indice di uno sprite, l'ordine di disegno degli stessi Sorriso

io ho scelto il quick, cosi cambi solo i puntatori, però ho fatto un test con i numeri ove angelo mi ha detto che è meglio il Radix Sort, ma da questo test non sembra essere cosi. (Forse si riferiva ad altri casi, magari con strutture heap / albero?)

Quindi quello che mi chiedo è: c'è un errore di implementazione o è effettivamente più lento il Radix Sort ?

TheOne · 16-08-2011 11:06

L'implementazione è presa dal libro di algoritmi "Introduzione agli algoritmi e strutture dati" della McGraw-Hill (si, il librone Sorriso

)... non ho controllato se sui libri di knuth c'è qualcosa di meglio, ma volevamo risparmiare più spazio e tempo possibile senza modificare troppo la struttura dati che avevamo...

hurricane86 · 16-08-2011 11:32

sarò scontato e ripetitivo ma:

KISS

TheOne · 16-08-2011 11:43

Nel dubbio, queste risposte sono sempre gradite Sorriso

TheCrib · 16-08-2011 12:04

1) Non ha senso profilare debug

2) L'implementazione conta

3) La GetTime() mi sembra fin troppo elaborata *

4) L'efficenza di un algoritmo dipende dal numero di elementi e possibilemente anche dallo stato iniziale dei dati (QuickSort)

Farei un profiling piu' accurato per vedere se si arriva a delle condizioni per le quali il radix funziona meglio.

* io uso questa

Codice:

typedef    __int64    I64;

//==========================

I64 GetTimeTicks()

{

    I64    val;

    QueryPerformanceCounter( (LARGE_INTEGER *)&val );

    return val;

}

//==========================

double TimeTicksToMS( I64 ticks )

{

    static double    coe;

    static I64      freq;

    if ( freq == 0 )

    {

        QueryPerformanceFrequency( (LARGE_INTEGER *)&freq );

        coe = 1000.0 / freq;

    }

    return ticks * coe;

}

Gabriele · 16-08-2011 12:20

(16-08-2011 12:04)TheCrib ha scritto: 1) Non ha senso profilare debug

2) L'implementazione conta

3) La GetTime() mi sembra fin troppo elaborata *

4) L'efficenza di un algoritmo dipende dal numero di elementi e possibilemente anche dallo stato iniziale dei dati (QuickSort)

Farei un profiling piu' accurato per vedere se si arriva a delle condizioni per le quali il radix funziona meglio.

* io uso questa

Codice:

typedef __int64 I64; //========================== I64 GetTimeTicks() { I64 val; QueryPerformanceCounter( (LARGE_INTEGER *)&val ); return val; } //========================== double TimeTicksToMS( I64 ticks ) { static double coe; static I64 freq; if ( freq == 0 ) { QueryPerformanceFrequency( (LARGE_INTEGER *)&freq ); coe = 1000.0 / freq; } return ticks * coe; }

grazie, sia per la risposta che per il codice Sisi

cmq:

Cerco di "spiegare":

1) si, inizialmente non l'ho messo poi ho editato tanto per mettere un dato in più...( Linguaccia

)

2) si infatti mi chiedevo se c'erano migliore implementazioni (molto probabile anche perché uno già me ne era venuta una in mente...), c'è da dire che nel caso mio cmq ho un vettore semplice di puntatori, quindi forse è meglio il quick sort...

3) Asd

sii, ero sicuro che c'era un modo + veloce con l'api win32 per conoscere "il tempo della macchina" cmq non credo cambi più di tanto, infondo rallenta in entrambi i casi ....

4) nel caso mio ho potenzialmente infiniti elementi quindi non saprei quanto mi conviene il Radix Sort , ufficialmente maggiore è il numero migliore è il Radix Sort però.... boh non saprei...

una cosa è sicura: l'implementazione più semplice è quella del quick mi basta un vettore d puntatori, mentre con il Radix Sort dovrei mettere varie restrizioni...

cmq ora provo Sisi

TheCrib · 16-08-2011 12:26

(16-08-2011 12:20)Gabriele ha scritto: 4) nel caso mio ho potenzialmente infiniti elementi quindi non saprei

.."potenzialmente infiniti" non esiste 8)

Gabriele · 16-08-2011 12:27

(16-08-2011 12:26)TheCrib ha scritto:
(16-08-2011 12:20)Gabriele ha scritto: 4) nel caso mio ho potenzialmente infiniti elementi quindi non saprei

.."potenzialmente infiniti" non esiste 8)

cioè, non imposto un limite, anche se potrei farlo Sisi

sicuramente il minore dei problemi...
[Immagine: 0269_rm5f.gif]

TheCrib · 16-08-2011 12:45

(16-08-2011 12:27)Gabriele ha scritto: cioè, non imposto un limite, anche se potrei farlo sicuramente il minore dei problemi...

Volevo dire che se la performance e' il punto in questione allora e' importante sapere quale e' il numero approssimativo di elementi.

Per 4 elementi un bubble sort probabilmente vince. Per migliaia di elementi un qucik sort, se si cresce ancora di piu' allora il radix potrebbe vincere.

P.S. Buono il gyoza 8)

Gabriele · 16-08-2011 13:01

(16-08-2011 12:45)TheCrib ha scritto:
(16-08-2011 12:27)Gabriele ha scritto: cioè, non imposto un limite, anche se potrei farlo sicuramente il minore dei problemi...

Volevo dire che se la performance e' il punto in questione allora e' importante sapere quale e' il numero approssimativo di elementi.

Per 4 elementi un bubble sort probabilmente vince. Per migliaia di elementi un qucik sort, se si cresce ancora di piu' allaora il radix potrebbe vincere.

P.S. Buono il gyoza 8)

AHHHHH! Si ora ho capito cosa intendi Sorriso

beh si, si parla di cento - duecento elementi alla fine Sisi

Ora cmq mi è venuta voglia di cucina orientale Piange

**_tommo_** · 16-08-2011 13:16

Essì, dovresti provare con numeri diversi di elementi Sisi

Comunque nel radix sort l'implementazione conta tantissimo, perchè mi pare sia algoritmicamente meno efficiente di quick sort, che è O(nlogn) come tutti gli altri algoritmi di sort ottimizzati.
Tuttavia è l'unico sorting che può essere usato in maniera efficente in cache, out of core, o in situazioni pesantemente multithread (a parte forse il mergesort) e infatti in CUDA è praticamente lo standard.

In sostanza, se non sfrutti questi vantaggi è sempre meglio quicksort.

E poi mi chiedo che c'avrai da sortare che ti serve tutta sta performance Asd

Gabriele · 16-08-2011 18:49

(16-08-2011 13:16)_tommo_ ha scritto: Essì, dovresti provare con numeri diversi di elementi
Comunque nel radix sort l'implementazione conta tantissimo, perchè mi pare sia algoritmicamente meno efficiente di quick sort, che è O(nlogn) come tutti gli altri algoritmi di sort ottimizzati.
Tuttavia è l'unico sorting che può essere usato in maniera efficente in cache, out of core, o in situazioni pesantemente multithread (a parte forse il mergesort) e infatti in CUDA è praticamente lo standard.

In sostanza, se non sfrutti questi vantaggi è sempre meglio quicksort.

E poi mi chiedo che c'avrai da sortare che ti serve tutta sta performance

ripeto lo uso per gli sprite, una sorta di zorder self made:

[Immagine: particle_engine.jpg]

**Eclipse** · 16-08-2011 18:55

e ti serve ordinare tutto ogni frame? Sorriso

Gabriele · 16-08-2011 18:58

(16-08-2011 18:55)Eclipse ha scritto: e ti serve ordinare tutto ogni frame?

eheheh no il cuoricino non viene ordinato Asd

solo l'emettitore Sorriso

il resto si, ma l'ordinamento scatta solo se viene modificato l'indice.... e naturalmente gli sprite (le non particelle) vengono disegnate solo se stanno su schermo...

cioè questa parte:

Codice:

    FGraphic fg(&camera);

    MSprite *sfg[]={fg.CreateSprite(0),

                    fg.CreateSprite(0),

                    fg.CreateSprite(0),

                    fg.CreateSprite(0)};

    MLight *light=fg.CreateLight(100);    

    light->SetPosition(170,166);

    light->SetRotation(0.0f);

    light->SetDiffuse(1.0,0.0,0.0,1.0);

    light->SetSpecular(1.0,0.3,0.3,1.0);

    light->radius=100;

    sfg[0]->material=&material;

    sfg[0]->SetScale(100,100);

    sfg[0]->SetRotation(45);

    sfg[0]->SetPosition(50,50);

    sfg[0]->SetIndex(11);

    sfg[1]->material=&material;

    sfg[1]->SetScale(100,100);

    sfg[1]->SetRotation(180);

    sfg[1]->SetPosition(100,50);

    sfg[1]->SetIndex(9);

    sfg[2]->material=&material2;

    sfg[2]->SetScale(100,100);

    sfg[2]->SetRotation(10);

    sfg[2]->SetPosition(100,100);

    sfg[2]->SetIndex(1000);

    sfg[2]->AddChild(sfg[1], PARENT::ENABLE_ROTATION);

    sfg[1]->AddChild(sfg[0], PARENT::ENABLE_POSITION);

    sfg[3]->material=&material;

    sfg[3]->SetScale(100,100);

    sfg[3]->SetRotation(45);

    sfg[3]->SetPosition(100,50);

    sfg[3]->SetIndex(9);

    sfg[0]->AddChild(sfg[3], PARENT::ENABLE_ROTATION | PARENT::ENABLE_POSITION);

    MSprite *test;

    for(int i=0;i<1000;i+=90){

        (test=fg.CreateSprite())->SetScale(10+i*0.1,10+i*0.1);

        test->SetPosition(100+300*sin(i*0.002),-150+300*cos(i*0.002));

        test->material=&material2;

        sfg[3]->AddChild(test, PARENT::ENABLE_ROTATION | PARENT::ENABLE_POSITION );

    }

mentre il cuoricino sono 2 emettitori, solo loro vengono ordinati, le particelle no...

Codice:

    ParticleEmettitor ps,ps2;

    ps.SetPosition(400,300);

    ps.SetTexture(tex2.GetIDTexture());

    ps.SetPartcle(10,60);

    ps.SetParticleLife(7,1);

    ps.SetParticleRateEmission(50);

    ps.SetParticleScale(Vector2D(0,0),Vector2D(30,30),Vector2D(0,0));

    ps.SetParticlePosition(Vector2D(0,0));

    ps2.SetPosition(400,300);

    ps2.SetTexture(tex2.GetIDTexture());

    ps2.SetPartcle(10,60);

    ps2.SetParticleLife(7,1);

    ps2.SetParticleRateEmission(50);

    ps2.SetParticleScale(Vector2D(0,0),Vector2D(30,30),Vector2D(0,0));

    ps2.SetParticlePosition(Vector2D(0,0));

    ps.SetParticleDirection(Vector2D(5,-200),Vector2D(5,-200));

    ps2.SetParticleDirection(Vector2D(-5,-200),Vector2D(-5,-200));

    ps.SetParticleIncVelocity(-5,-5);

    ps.SetParticleTangentialVelocity(-200,-100);

    ps2.SetParticleIncVelocity(-5,-5);

    ps2.SetParticleTangentialVelocity(200,100);

    ps.SetParticleGravity(Vector2D(0,50));

    ps2.SetParticleGravity(Vector2D(0,50));

    float color1[]={1.0,0.0,0.0,1.0};

    float color2[]={0.0,0.0,1.0,0.0};

    ps.SetParticleColor(color1,color2);

    ps2.SetParticleColor(color1,color2);

cmq ho provato a mettere la scala anche l'emettitore, c fata ... vedere il cuoricino schiacciato XD
W LE MATRICI ANCHE NEL 2D!

fzambetta · 17-08-2011 0:57

Come dicevano Tommo e TheCrib quello che importa e' l'ordine di grandezza dei dati da ordinare.
So benissimo che su questo forum c'e' un numero piuttosto elevato di persone che credono che l'Universita' sia un optional, magari lo e', ma guardo caso questa e' roba che un qualsiasi corso di Laurea in Informatica, pure sgangherato, tratta in dettaglio Asd

In alternativa, basta essere in grado di studiare tutta la roba necessaria a compredere uno e due Occhiolino

Modo discussione \| Modo lineare Radix Sort vs Quick Sort
Autore	Messaggio