LE QUICKSORT NON-RECURSIF ET L'IMPACT DE L'INSERTIONSORT SUR SES PERFORMANCES

Commentaire de Pistol_Pete le 18/06/2008 09:41:06

Salut

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+

Commentaire de BruNews le 18/06/2008 19:56:57 administrateur CS

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;
  }
}

Commentaire de MuPuF le 21/06/2008 12:46:22

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 ;)