QUICKSORT - NON RECURSIF

Commentaire de vecchio56 le 03/03/2006 10:40:01 administrateur CS

Tu dis que les appels de fonctions sont pénalisants à cause des sauvegardes sur la pile et des réallocations mémoire. Qu'est ce que tu entends par réallocations mémoire?

Commentaire de vecchio56 le 03/03/2006 17:51:23 administrateur CS

Je sais ce qu'est une réallocation, mais dans le cas de la récursivité, tout se passe dans la pile, donc ya jamais d'allocation de mémoire ailleurs

Commentaire de vecchio56 le 03/03/2006 18:37:09 administrateur CS

Tu dis "à cause des sauvegardes sur la pile (...) et des réallocations mémoires" donc je me disais que tu parlais d'allocations ailleurs que dans la pile

Commentaire de shenron666 le 04/03/2006 10:09:58

Source intéressante de par ton approche ;-)

Il faudrait faire des tests de rapidité entre ta fonction et la même en mode récursif pour voir s'il y a réellement une différence de vitesse à ton avantage.
Surtout que tu  parles de réallocation mais tu en fais toi aussi avec "queue"

Dommage que tu n'utilises pas la stl mais ce n'est qu'un détail

Commentaire de vecchio56 le 04/03/2006 16:54:30 administrateur CS

Les allocations dans la pile sont bien moins couteux que dans le tas. Mais ici il n'y a c'est vrai qu'une allocation dans le tas, ce qui doit sans doute compenser en général

Commentaire de BruNews le 07/03/2006 10:28:48 administrateur CS

Vraiment je ne copprends pas votre problème.
Le tableau à trier existe déjà puisqu'on le reçoit en param donc aucun prob mémoire vu q'il n'y a aucune alloc à faire pour un quicksort, suffit de regarder l'implem de qsort() de la CRT.

Commentaire de BruNews le 07/03/2006 11:53:49 administrateur CS

qsort est un algo générique, on en a le code donc on le dévie pour le spécialiser:
http://www.cppfrance.com/code.aspx?id=11151

'goto' indique que c'est de la daube ? alors change de taf, un cpu ne comprend que cela les sauts de code, pas parce qu'on ne les voit pas que le compilo écrira autre chose.

Commentaire de nickydaquick le 07/03/2006 12:37:01

MErci pour tous vos commentaires... Je tenais a te dire shenron666, que ce code a ete depose ici a titre illustratif et comprehensif. La taille du tableau est uniquement suggestif alors arrete de faire des copier - coller et inspire toi de ce code pour ameliorer le tien. Toi ki fait par exemple des tests de rapidite , arrete de nous dire si le test plante ( parce que tu n'as certainement pas determine la taille du heap a reserver au depart du prog ) , et donne nous des resultats temporels
   Merci

Commentaire de nickydaquick le 07/03/2006 14:57:03

En fait je viens de comprendre ton pb, tu voudrais un code que tu puisse carrement coller sans avoir a comprendre quoi que ce soit , faire un test si ca marche Bingo. Dans ce cas demande le moi je te le donne , optimisé et avec les comparaisons temporels en ms.
       J'attends de tes news

PS: De nos jour les gens ne savent plus la signification du mot algorithme ...

Commentaire de nickydaquick le 07/03/2006 16:07:31

  Ok Shenron , tu gagnes , je vais te mettre un version rapide du Tri rapide , sans bug ... tu pourras faire les tests. Toutes mes excuses si je t'ai mal compris mais mon but etait initialement de montrer un algorithme , donc une logique revue du quicksort. Je recorrigerait donc ma source , pour que tu puisses faire des test sur autant de nombres que tu veux. Je mettrai aussi des resultats en comparatif avec la fonction qsort() de vc++6.0. Donne moi juste 5 minutes.

Commentaire de fuliculi le 09/03/2006 15:30:01

L'algo le plus efficace à ce jour (il me semble) est le tri à panier. Ca ne s'applique qu'au tri de nombres entiers (pas de réel) et c'est terriblement simple et rapide.

Commentaire de fuliculi le 09/03/2006 16:04:23

Allez hop, c'est codé à l'arrache mais j'ai pris le temps de tester un peu quand même...

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>

void tri(long *tab, long size)
{
if (size<=0 || tab==NULL)
return;

long min = tab[0];
long max = tab[0];
long i, j;

// Recherche les bornes de la liste
for (i=0; i<size; i++)
{
if (tab[i]<min) min=tab[i];
if (tab[i]>max) max=tab[i];
}

if (min==max)
return;

// Un panier par valeur possible entre le min et le max
long *paniers = new long[max-min+1];
memset(paniers, 0, (max-min+1)*sizeof(long));

// Ajouter un jeton dans le panier de la valeur (min = premier panier, max = dernier panier)
for (i=0; i<size; i++)
paniers[tab[i]-min]++;

long numVal = 0;

// Remplir le tableau d'entrée avec les paniers en partant du premier (ou du dernier pour un tri décroissant)
for (i=0; i<max-min+1; i++)
// Copier autant de fois la valeur du panier qu'il contient de jetons
for (j=0; j<paniers[i]; j++)
tab[numVal++] = min+i;

delete [] paniers;
}

//#define PRINT

void main (void)
{
long max = 1000000;
long *values = new long[max];
long i;

srand((unsigned)time(NULL));

for (i=0; i<max; i++)
      values[i] = (long)rand();

#ifdef PRINT
for (i=0; i<max; i++)
printf("in  : %d ", values[i]);
#endif

long startTime = clock();
tri(values, max);
long stopTime = clock();

#ifdef PRINT
for (i=0; i<max; i++)
printf("out : %d\n", values[i]);
#endif

printf("Temps ecoule : %d ms", stopTime - startTime);

delete [] values;
}

Commentaire de fuliculi le 09/03/2006 16:27:15

J'ai ces temps là avec l'algo de nickydaquick

400 ms pour 1 millions de valeurs (26x plus de temps)
5200 ms pour 10 millions de valeurs (24x plus de temps)

Et vous?

Commentaire de BruNews le 09/03/2006 23:00:53 administrateur CS

Je viens de tester, nickel pour la vitesse (presque 12 fois plus vite que celui que j'ai mis en lien).
Dommage qu'il y ait cette alloc mémoire qui peut rater (par exemple sur une plage full 32 bits on ne passe pas) mais enfin devrait aller dans beaucoup de cas, vraiment très bien.

Commentaire de Noxk le 11/03/2006 16:56:41

shenron666, ton algo de tri je viens de le tester il ne marche pas, certe il est rapide mais en sorti c'est pas trié, il y a certainement quelque chose a revoir.

Commentaire de nickydaquick le 14/03/2006 01:52:00

Je suis desole mais tes temps ne sont pas exacts sur le mien ( mon ordi ) je suis en dessous des 1.6 sur un random de 10 millions de int , si tu utilises une tranche de reallocation moindre ( de l'ordre de la centaine de milliers )

Commentaire de Noxk le 14/03/2006 09:28:10

Salut Nicky,

J'ai effectué les test comme tu l'indiquais et les temps donnés pour le tri sont reellement meilleur mais y a un bogue, le tri est partiellement effectué. Ceci provient du fait que tu as oublié de remettre cursor a sa position final quand tu realloues la memoire.

Ca se corrige en remplacant les "*(cursor++)" par des  "*(cursor + i++)" et ensuite dans la condition "if" mettre "*(cursor + i);"


Mais meme avec ca on remarque un probleme, tu rentres trop souvent dans la condition "if" de realloc et ca bouffe un temps enorme.Ce que je te propose, vu que tu utilise dans ton algo une pile, que tu ne depiles jamais, c'est justement s'en servir comme d'une pile qu'on depile et plus besoin de realloué la memoire, le seul probleme reside dans le fait de definir une taille de la pile suffisante.

Je me permets de mettre le code corrigé a ma manière et qui ressemble un peu a celui que j'ai écrit sur l'aspect pile/depile.

#define RHASH    100000
  
void quicksort(int* const tablo, const int first , const int last)
  {
     //first = premier index du tableau
     //last = dernier index du tableau
     int debut;
     int fin;
         int begin;
     int end;
     int pivot;
     int temp;
int i=0;
  
     int index=0;
     int size=0;
     int capacite = RHASH+2;
  
     //allocation de la file
     int* queue = NULL;
     int* cursor;
     int* indexc;
    
     queue = (int*)malloc(capacite*sizeof(int));
        
     if(queue == NULL)
         return;
  
     cursor = queue;
     indexc = queue;
  
     *(cursor + i++) = first; //sauvegarde du debut du tablo a trier
     *(cursor + i++) = last;    //sauvegarde de la fin du tablo a trier
     index = 0;
     size = 2;
  
     do
     {
         //debut = *(indexc++); //recuperation de l'indice de debut
         //fin    = *(indexc++);    //recuperation de l'indice de fin
fin    = *(cursor + --i);    //recuperation de l'indice de fin
debut = *(cursor + --i); //recuperation de l'indice de debut
        
  
         index+=2;
  
         if(debut < fin)
         {
             begin    = debut;
             end      = fin;
             pivot    = tablo[fin];//on prend le dernier element comme valeur pivot
  
             do
             {
                 //progresser jusqu'a un element superieur ou egal au pivot
                 while ( (begin < fin) && (tablo[begin]<=pivot) )
                     begin++;
                 //progresser jusqu'a un element inferieur ou egal au pivot
                 while ( (end > begin) && (tablo[end]>=pivot) )
                     end--;
  
                 //echanger les 2 elements qui sont dans le mauvais ordre
                 //comparativement au pivot
                 if (begin < end)
                 {
                     temp            = tablo[end];
                     tablo[end]      = tablo[begin];
                     tablo[begin]    = temp;
                 }
  
             }while(begin < end);//continuer a parcourir le tablo
  
             //mettre le pivot a sa place dans le tableau trie
             temp            = tablo[fin];
             tablo[fin]      = tablo[begin];
             tablo[begin]    = temp;
  
  
             //sauvegarder les indexes des prochains tris a faire
             // dans les sous-tableaux prochains
             // a savoir : a gauche du pivot , puis a droite du pivot
  
             //sauvegarde du debut du sous-tableau a trier => a gauche du pivot
             *(cursor + i++) = debut;
             //sauvegarde de la fin du sous-tableau a trier => a gauche du pivot
             *(cursor + i++) = begin-1;
  
             //sauvegarde du debut du sous-tableau a trier => a droite du pivot
             *(cursor + i++) = begin+1;
             //sauvegarde de la fin du sous-tableau a trier => a droite du pivot
             *(cursor + i++) = fin;
             size+=4;
  
     //        if(size==capacite)
     //        {
     //            capacite += RHASH;
     //            cout << "rehash" << endl;
     //            queue = (int*)realloc(queue,capacite*sizeof(int));
     //            cursor = queue;
     //            indexc = &cursor[index];
//*(cursor + i);
     //            if(queue == NULL)
     //             return;
     //        }
         }
     }
     while(index<size);
     cursor = NULL;
     indexc = NULL;
     free(queue);
}

Reste plus qu'a trouver un matheux pour trouver la formule de la taille de la pile en rapport avec celle du tableau :)

Sinon au niveau des score maintenant tu es meilleur que le mien mais reste tres legerement en dessous de ceux de BruNew.

Commentaire de Maroi le 29/04/2010 20:41:39

Salut,
Est ce que vous pouvez donner un exemple de quicksort non récursif pr les réels?
Merci bcp