Le quicksort non-recursif et l'impact de l'insertionsort sur ses performances

Soyez le premier à donner votre avis sur cette source.

Vue 4 795 fois - Téléchargée 134 fois

Description

Je depose cette source en rapport avec une discussion sur les performances du tri rapide (quicksort) qui pourraient etre ameliorees en visant une implementation non-recursive. Je me suis penche sur l'apport cote performance d'une autre methode de tri elle aussi tres rapide, sur des morceaux du tableau a trier de taille moindre lors du processus.

J'ai pour cela , par recurrence, demontrer que la taille maximale de la pile a allouer pour sauvegarder les index de tableau de taille N est le nombre binaire le plus proche >= N note N2.Par exemple si votre tableau est de 1000 items, la pile ne depassera pas les 1024 items (512 index de debut et 512 index de fin).
Ici vous pouvez modifier le code a votre guise. J'ai utiliser un tableau d'entiers. Les variables pour tester les performances et l'impact sont INSERTION_SORT_LIMIT(taille limite du tableau en dessous de laquelle on realise un insertionSort au lieu d'un quicksort) et ARRAY_SIZE pour la taille du tableau.

Source / Exemple :


// voir le Zip - source main.cpp windows Visual c++ 2005 professionnel

Conclusion :


J'espere que vous serez nombreux a realiser des tests et a les rapporter pour comparer, ou corriger et/ou ameliorer la source. Pour ma part voici le resultat pour un exemple-test de configuration:

Hardware: Hewlett-Packard m8307c
Intel Core2 Quad CPU Q6600 @ 2.40Ghz 2.40Ghz
RAM = 3Gb
Vista 32bits

INSERTION_SORT_LIMIT = 500
ARRAY_SIZE = 10000000;//10 millions

temps d'execution moyen : 818 ms (millisecondes).

Codes Sources

A voir également

Ajouter un commentaire Commentaires
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
27
29 avril 2010 à 21:43
Des réels, double ou float, se trient exactement comme des entiers signés.

Exemple pour float, il n'y a quasi rien à changer.

void __stdcall triInts(int *ptab, DWORD count)
{
int *lo, *hi, *mid, *loguy, *higuy, v;
int *lostk[STKSIZ], *histk[STKSIZ];
size_t size;
int stkptr = 0;
lo = (int*) ptab; // CAST ICI ET BASTA
...
...
cs_Maroi
Messages postés
10
Date d'inscription
mercredi 30 décembre 2009
Statut
Membre
Dernière intervention
1 avril 2012

29 avril 2010 à 17:39
Salut
est ce que vous pouvez me donner un exemple de quicksort non récursif pour des réels?
Merci bcp
MuPuF
Messages postés
536
Date d'inscription
mercredi 27 avril 2005
Statut
Membre
Dernière intervention
22 août 2008

21 juin 2008 à 12:46
Salut Brunews, Je suis pas entièrement d'accord avec toi sur le fait de ne pas créer une thread.
Grâce à la librairie Intel (TBB), on peut définir des seuils avant qu'une autre thread soit exécutée (granularité), ça permet lors de tri d'énormes tableaux d'utiliser le 2eme (ou plus) processeur et on est libre sur le choix de quand l'utilisation de la(/ces) thread(s) apporte un interêt.

C'est sur que dans l'absolu, si on avait pas cette librairie, dans 99% des cas, la création d'une thread serait contre productif, mais faut aussi se pencher sur les concepts qu'essaye de diffuser Intel. Je ne dis pas que c'est la panacée, mais ça a le mérite d'exister et d'être déjà pas mal efficace.

bon week end ;)
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
27
18 juin 2008 à 20:01
Pour ce qui est du multi thread, je ne suis pas convaincu du tout d'aller créer un thread pour un algo restant dans les milli secondes. La crétion d'un thread risque fort de consommer autant que le temps de tri.
BruNews
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
27
18 juin 2008 à 19:56
Salut,

le gros problème avec ce genre de tri c'est qu'il ne peut aller en prod dans un prog qui effectue des tris sur de gros tableaux pour la simple raison qu'il fait une alloc qui risque de ne pas réussir. Un algo de tri doit fonctionner à tout coup et la seule méthode certaine est un tri sur place sans aucune alloc.
On évacue la discussion sur la récursivité, il est clair que si un quicksort est récursif, il ne reste que le 'sort' mais plus du tout le 'quick'.

Essaie avec ça, j'ai fait qlqs tests et il me semble que c'est au moins aussi rapide (voire +) avec garantie de finir le tri qlq soit la taille du tableau:

#define STKSIZ (8 * sizeof(void*) - 2)

__inline void ShortsortLong(int *lo, int *hi)
{
int *p, *max, v;
while(hi > lo) {
max = lo;
for(p = lo + 1; p <= hi; p++) {
if(*p > *max) max = p;
}
v *max; *max *hi; *hi = v;
hi--;
}
}

void __stdcall triInts(int *ptab, DWORD count)
{
int *lo, *hi, *mid, *loguy, *higuy, v;
int *lostk[STKSIZ], *histk[STKSIZ];
size_t size;
int stkptr = 0;
lo = ptab;
hi = lo + (count - 1); /* DERNIER ELEM */
recurse:
size = (hi - lo) / sizeof(long) + 1; /* NBR ELEMS A TRIER */
if(size <= 8) {
ShortsortLong(lo, hi);
goto goSTACK;
}
mid = lo + (size / 2); /* ELEM CENTRAL */
if(*lo > *mid) {v *lo; *lo *mid; *mid = v;}
if(*lo > *hi) {v *lo; *lo *hi; *hi = v;}
if(*mid > *hi) {v *mid; *mid *hi; *hi = v;}
loguy = lo;
higuy = hi;
for(;;) {
if(mid > loguy) {
do {
loguy++;
} while(loguy < mid && *loguy <= *mid);
}
if(mid <= loguy) {
do {
loguy++;
} while(loguy <= hi && *loguy <= *mid);
}
do {
higuy--;
} while (higuy > mid && *higuy > *mid);
if(higuy < loguy) break;
v *loguy; *loguy *higuy; *higuy = v;
if(mid higuy) mid loguy;
}
higuy++;
if(mid < higuy) {
do {
higuy--;
} while(higuy > mid && *higuy == *mid);
}
if(mid >= higuy) {
do {
higuy--;
} while(higuy > lo && *higuy == *mid);
}
if(higuy - lo >= hi - loguy) {
if(lo < higuy) {
lostk[stkptr] = lo;
histk[stkptr] = higuy;
++stkptr;
}
if(loguy < hi) {
lo = loguy;
goto recurse;
}
}
else {
if(loguy < hi) {
lostk[stkptr] = loguy;
histk[stkptr] = hi;
++stkptr;
}
if(lo < higuy) {
hi = higuy;
goto recurse;
}
}
goSTACK:
if(--stkptr >= 0) {
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse;
}
}
Afficher les 7 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.