Orario: 24-05-2013, 18:33 Benvenuto ospite! (Log inRegistrati)


Rispondi 
Radix Sort vs Quick Sort
Autore Messaggio
Gabriele
Posting Freak

Messaggi: 4,386
Registrato: Oct 2010
Offline Offline
#1 Radix Sort vs Quick Sort
0
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 ?

Gabriele Di Bari
Account G+
Account bitbucket
Account GITHUB
E ricordate: ((VMJava*)(NULL))->~VMJava();
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 12:25 da Gabriele.)
16-08-2011 10:59
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
TheOne
Junior Member

Messaggi: 22
Registrato: Jul 2011
Offline Offline
#2 RE: Radix Sort vs Quick Sort
0
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...

Tra le cose sicure, la più sicura è il dubbio.
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 11:18 da TheOne.)
16-08-2011 11:06
Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
hurricane86
Posting Freak

Messaggi: 1,266
Registrato: Jun 2009
Offline Offline
#3 RE: Radix Sort vs Quick Sort
+1
sarò scontato e ripetitivo ma:

KISS

Martino Giovanelli
16-08-2011 11:32
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
TheOne
Junior Member

Messaggi: 22
Registrato: Jul 2011
Offline Offline
#4 RE: Radix Sort vs Quick Sort
0
Nel dubbio, queste risposte sono sempre gradite Sorriso

Tra le cose sicure, la più sicura è il dubbio.
16-08-2011 11:43
Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
TheCrib
Indie Pellerossa

Messaggi: 5,200
Registrato: Sep 2010
Offline Offline
#5 RE: Radix Sort vs Quick Sort
0
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;
}

Davide Pasca
http://v5.kazzuya.com - @109mae
http://oyatsukai.com - @oyatsukai
"O frechete !" - M.Magnotta
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 12:05 da TheCrib.)
16-08-2011 12:04
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
Gabriele
Posting Freak

Messaggi: 4,386
Registrato: Oct 2010
Offline Offline
#6 RE: Radix Sort vs Quick Sort
0
(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

Gabriele Di Bari
Account G+
Account bitbucket
Account GITHUB
E ricordate: ((VMJava*)(NULL))->~VMJava();
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 13:03 da Gabriele.)
16-08-2011 12:20
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
TheCrib
Indie Pellerossa

Messaggi: 5,200
Registrato: Sep 2010
Offline Offline
#7 RE: Radix Sort vs Quick Sort
0
(16-08-2011 12:20)Gabriele ha scritto:  4) nel caso mio ho potenzialmente infiniti elementi quindi non saprei

.."potenzialmente infiniti" non esiste 8)

Davide Pasca
http://v5.kazzuya.com - @109mae
http://oyatsukai.com - @oyatsukai
"O frechete !" - M.Magnotta
16-08-2011 12:26
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
Gabriele
Posting Freak

Messaggi: 4,386
Registrato: Oct 2010
Offline Offline
#8 RE: Radix Sort vs Quick Sort
0
(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]

Gabriele Di Bari
Account G+
Account bitbucket
Account GITHUB
E ricordate: ((VMJava*)(NULL))->~VMJava();
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 12:43 da Gabriele.)
16-08-2011 12:27
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
TheCrib
Indie Pellerossa

Messaggi: 5,200
Registrato: Sep 2010
Offline Offline
#9 RE: Radix Sort vs Quick Sort
0
(16-08-2011 12:27)Gabriele ha scritto:  cioè, non imposto un limite, anche se potrei farlo Sisi 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)

Davide Pasca
http://v5.kazzuya.com - @109mae
http://oyatsukai.com - @oyatsukai
"O frechete !" - M.Magnotta
(Questo messaggio è stato modificato l'ultima volta il: 17-08-2011 1:16 da TheCrib.)
16-08-2011 12:45
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
Gabriele
Posting Freak

Messaggi: 4,386
Registrato: Oct 2010
Offline Offline
#10 RE: Radix Sort vs Quick Sort
0
(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 Sisi 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

Gabriele Di Bari
Account G+
Account bitbucket
Account GITHUB
E ricordate: ((VMJava*)(NULL))->~VMJava();
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 13:02 da Gabriele.)
16-08-2011 13:01
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
_tommo_
Mod nerdcore

Messaggi: 5,908
Registrato: Nov 2008
Online Online
#11 RE: Radix Sort vs Quick Sort
0
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

Tommaso Checchi
< devlog | twitter | Dojo, a C++ game framework >
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 13:17 da _tommo_.)
16-08-2011 13:16
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
Gabriele
Posting Freak

Messaggi: 4,386
Registrato: Oct 2010
Offline Offline
#12 RE: Radix Sort vs Quick Sort
0
(16-08-2011 13:16)_tommo_ ha scritto:  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

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

[Immagine: particle_engine.jpg]

Gabriele Di Bari
Account G+
Account bitbucket
Account GITHUB
E ricordate: ((VMJava*)(NULL))->~VMJava();
16-08-2011 18:49
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
Eclipse
npc in fps 4 food

Messaggi: 11,275
Registrato: Sep 2004
Offline Offline
#13 RE: Radix Sort vs Quick Sort
0
e ti serve ordinare tutto ogni frame? Sorriso

Giuseppe Navarria - Moonloop
[Immagine: twittericon.png] [Immagine: linkedinicon.png] [Immagine: steamicon.png]
16-08-2011 18:55
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
Gabriele
Posting Freak

Messaggi: 4,386
Registrato: Oct 2010
Offline Offline
#14 RE: Radix Sort vs Quick Sort
0
(16-08-2011 18:55)Eclipse ha scritto:  e ti serve ordinare tutto ogni frame? Sorriso

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!

Gabriele Di Bari
Account G+
Account bitbucket
Account GITHUB
E ricordate: ((VMJava*)(NULL))->~VMJava();
(Questo messaggio è stato modificato l'ultima volta il: 16-08-2011 19:25 da Gabriele.)
16-08-2011 18:58
Visita il sito web di questo utente Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
fzambetta
Senior Lecturer

Messaggi: 1,743
Registrato: Dec 2009
Offline Offline
#15 RE: Radix Sort vs Quick Sort
0
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

Fabio Zambetta
Senior Lecturer, School of CS&IT
RMIT University (Melbourne, AU)

Games & Graphics Programming degree Coordinator

My Kinect hand gestures debugger
(Questo messaggio è stato modificato l'ultima volta il: 17-08-2011 0:58 da fzambetta.)
17-08-2011 0:57
Trova tutti i messaggi di questo utente Cita questo messaggio nella tua risposta
Rispondi 


Vai al forum: