LE QUICKSORT NON-RECURSIF ET L'IMPACT DE L'INSERTIONSORT SUR SES PERFORMANCES
Pistol_Pete
Messages postés
1053
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
-
18 juin 2008 à 09:41
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 29 avril 2010 à 21:43
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 29 avril 2010 à 21:43
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/47044-le-quicksort-non-recursif-et-l-impact-de-l-insertionsort-sur-ses-performances
https://codes-sources.commentcamarche.net/source/47044-le-quicksort-non-recursif-et-l-impact-de-l-insertionsort-sur-ses-performances
29 avril 2010 à 21:43
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
...
...
29 avril 2010 à 17:39
est ce que vous pouvez me donner un exemple de quicksort non récursif pour des réels?
Merci bcp
21 juin 2008 à 12:46
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 ;)
18 juin 2008 à 20:01
18 juin 2008 à 19:56
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;
}
}
18 juin 2008 à 09:46
Merci pour le commentaire, effectivement le tri de tableaux en parallèle pourrait avoir un impact mais je doute qu'il y ait un gain significatif. cependant , tu as raison , je vais modifier la source et des que le temps me le permettra je déposerait une autre source, multithreaded, en rapport avec celle-ci ... histoire de comparer.
18 juin 2008 à 09:41
Voila mes resultats pour 10 millions: 166 ms
AMD Athlon 64 X2 Dual
Core processor 6000+
3 GHz
XP sp3
Et puisse que l'on parle de performance, je ne comprend pas pourquoi ce programme n'est pas multithread...
Utiliser la moitier de la puissance de son PC, ca ne te gene pas?
Je suis sur que pour des plus grandes listes le gain sera immense. Ca serai cool de pouvoir tester.
A+