Comment trier ses donnees vite et bien ?

Le Byte Sort, algorithme de tri efficace.

(c) Mai 1996 Phar /Flower Corp

 

Si vous avez des questions concernant le present document, n'hesitez pas a m'envoyer un mail, ou a me parler sur IRC sur #demofr

 

I Presentation

Maintenant que la 3D est vraiment a la mode, tout le monde parle de trier les faces des objets. Et ici, on observe tres vite que chacun prefere un algorithme de tri different. Toutefois, on observe 2 grandes tendances : le Radix Sort, ou le Quick Sort (tri par tas ou tri rapide), qui ont tous les deux l'avantage d'etre rapides. Neanmoins, dans des applications comme les demos, ou la rapidite est vraiment l'element le plus important, ces deux tris souffrent de leurs tares : ils sont trop generaux : il conviennent a n'importe quel type de donnee (pour le quick sort en tout cas).

Le Byte sort est un algorithme inspire tout droit du Radix sort, mais il a 2 enormes avantages : il est facile a coder, et il est tres rapide. Facile a coder, nous allons le voir, puisque son algo est tres simple. Tres rapide, puisque c'est un tri en N, et non en N Log N.

 

II Principe de base

Quel est le principe de base du Byte Sort ?? C'est tout simplement de ne faire AUCUNE comparaison. Tout notre travail va etre de savoir OU placer la donnee, et c'est tout.

On va donc travailler en 3 etapes :

On le voit donc, il n'y a pas de comparaisons! Juste des positions... Cela fait que chacune des trois etapes se code en quelques lignes d'assembleur.

Pour faire ce tri, on a donc besoin des ingredients suivants :
Un bouquet garni.
Un processeur.
250g de beurre pour 8 personnes.
Plus :
Un tableau qui contient les donnees.
Un tableau qui contient les adresses.
Un tableau qui contiendra les donnees triees.

Pour les programmeurs PC en mode 32 bits, on pourrait dire : 

Tableau de 1 a N de Structures  <= Tableau non Trie, de N faces
    Numero de Face : Entier 32 bits
    Valeur du Z    : Entier 32 bits

Tableau de 0 a 255 de           <= Tableau pour les positions
    Nombre : Entier 32 bits

Tableau de 1 a N de             <= Tableau Trie de N faces
    Numero de Face

 

III Le fonctionnement

Nous avons donc Notre Tableau1, qui contient les donnees a trier. On va trier ce tableau en 4 passes : on va trier les octets 1,2,3 puis 4 (note : cela marche aussi dans l'autre sens, car le tri est sequentiel : pour 2 memes valeurs, il ne change pas l'ordre). 

<--- 32 bits --->
 _______________
|   |   |   |   |
| 1 | 2 | 3 | 4 |
|___|___|___|___|

Nous verrons au dernier chapitre comment faire en moins de passes...(patience)

Bien, maintenant que nous savons que nous allons trier en 4 passes, voyons chacune des 3 etapes qui composent notre tri :

 

A) Etape I : la creation du tableau 2.

Dans un premier temps, on va initialiser le tableau 2 a zero : 

Pour i=0 a 255 faire
  Tab2[i]=0;

Nous allons ensuite parcourir les cases de notre tableau 1 (celui a trier) une par une. Pour chaque case, on va recuperer la valeur. Ensuite, comme vu plus haut, nous allons indiquer dans le tableau 2, que cette valeur a ete vue une fois de plus. La boucle est donc : 

Pour i=0 a n-1 faire
   val=octet(Tab1[i].Z);         /* On recupere la coordonnee. */
   Tab2[val]=Tab2[val]+1;

A la fin de cette premiere etape, le tableau 2 contient le nombre de fois ou on a vu chaque octet.

Exemple :
Soit le tableau 1 : 

indice 0 1 2 3 4 5 6 7
------------------------
valeur 2 4 6 3 2 4 5 1

Le tableau 2 correspondant (ou tout du moins son debut) sera : 

indice 0 1 2 3 4 5 6 7 8
------------------------
valeur 0 1 2 1 2 1 1 0 0

 

B) Etape II : Transformation du tableau 2.

Nous avons donc dans le tableau 2 le nombre d'occurences de chaque valeur. Celles-ci vont nous permettre de connaitre la position de chaque valeur. En effet, il suffit de parcourir notre tableau 2, puis de calculer la nouvelle position. Celle-ci se deduit de la precedente, puis on ajoute le nombre d'occurences courant. Voyons l'algo : 

position=0
Pour i=0 a 255 faire
   increment=Tab2[i]
   Tab2[i]=position
   position=position+increment

Donc, si on applique cette boucle a l'exemple precedent, on trouve: 

indice   0  1  2  3  4  5  6  7  8
---------------------------------
valeur   0  0  1  3  4  6  7  8  8

Qu'est-ce que cela veut dire ??? Et bien tout simplement que l'emplacement de depart des donnees dont la valeur est 1 sera la case 0. Ou que l'emplacement de depart des donnees dont la valeur est 6 sera la case 7.
C'est magique! C'est Fantastique! (envoyez vos dons a Phar, C.C.P 148691738)

Bien, il nous reste a regler un dernier point de detail (mineur), le tri de nos donnees :

 

C) Etape III : Tri des donnees, du tableau 1 au tableau 3.

Il nous reste finalement a trier les donnees, et on va encore effectuer une boucle. En fait, pour chaque case de notre tableau initial, nous allons recuperer la valeur de l'octet voulu. Nous allons chercher dans le tableau 2 quelle est la position ou il faut mettre cette valeur. Et on va mettre notre donnee a la bonne position du tableau 3.

2 remarques :

  1. pour ne pas ecraser les donnees du tableau 1, on utilise un 3eme tableau, qui contiendra donc les donnees triees.

  2. Il faut aussi gerer le fait que l'on avance dans notre tableau 3 : si l'on trouve la valeur 3, puis que l'on retrouve une autre fois la valeur 3, il fait que la position ait avance d'une case. Donc, a chaque fois que l'on recupere une position dans le tableau 2, on incremente la case.

Tout cela donne l'algo suivant : 

Pour i=0 a N-1 faire :

   val=octet(Tab1[i].Z);      /* on recupere la clef de tri. */

   pos=tab2[val];             /* on en deduit la position. */
   tab2[val]=tab2[val]+1;

   tab3[pos]=Tab1[i].Numero_de_face /* on place la donnee a la bonne pos*/

Et si, une fois encore, on reprend l'exemple, on avait : 

Tableau 1 =

indice 0 1 2 3 4 5 6 7
------------------------
valeur 2 4 6 3 2 4 5 1


Tableau 2 =

indice   0  1  2  3  4  5  6  7  8
---------------------------------
valeur   0  0  1  3  4  6  7  8  8


Donc, Tableau 3=

indice   0  1  2  3  4  5  6  7
--------------------------------
valeur   7  0  4  3  1  5  6  2

Et on voit le resultat :
On a un fabuleux tableau trie! (sisi, verifiez!! il est trie!)

Donc, on vient de trier un tableau en 200 lignes de texte, mais sans aucune comparaison

 

IV Precisions

L'algo, tel que je vient de l'expliquer, marche tres bien, mais il ne faut pas oublier qu'il faut l'effectuer 4 fois, pour 4 octets... (32 bits), chaque fois sur un octet different.
De plus, la premiere passe se fait en transformant le tableau 1 en tableau 3, mais a la 2eme etape, il faudra reutiliser les donnees contenues dans le tableau 3!! 
Donc, passes 1 et 3 : Tab1 => Tab3
             2    4 : Tab3 => Tab1 (pour ne pas consommer trop de memoire)

Revoyons l'algo au complet :

A chaque Passe, octet(x), donne l'octet de x que l'on souhaite trier. 

/* Etape I */

Pour i=0 a n-1 faire
   val=octet(Tab1[i].Z);         /* On recupere la coordonnee. */
   Tab2[val]=Tab2[val]+1;


/* Etape II */

position=0
Pour i=0 a 255 faire
   increment=Tab2[i]
   Tab2[i]=position
   position=position+increment


/* Etape III */

Pour i=0 a n-1 faire :
   val=octet(Tab1[i].Z);

   pos=tab2[val];             /* on en deduit la position. */
   tab2[val]=tab2[val]+1;

   tab3[pos]=Tab1[i].Numero_de_face /* on place la donnee a la bonne pos */

 

V Optimisation

Comme je l'ai deja dit plus haut, ce tri est typiquement fait pour les demos pour une raison tres simple : il s'ecrit formidablement bien en Assembleur!

C'est un pur bonheur... Roudoudou en a fait une implementation, et celle-ci fait 84 lignes... Mais ce n'est pas a moi de vous expliquer comment coder ce tri en ASM...

Je vais neanmoins donner quelques tips :

  1. Remplacez les positions par des pointeurs (des offsets quoi). En effet, si dans le Tableau 2, vous remplacez la valeur 17 par exemple, par l'adresse de la case 17 dans Tab3, vous gagnerez en temps lors de la 3eme etape. Cela s'implemente tres facilement si vous regardez l'algo de l'etape 2. au depart, position=offset Tab3
    puis a l'interieur, position=position+increment*4 Et voila!

  2. Le Byte Sort c'est bien, mais le Word Sort, c'est mieux. En effet, on effectue les 3 etapes 4 fois avec le byte sort, alors que le Word Sort permet de ne les effectuer que 2 fois... Le principe : on utilise un Tab2 de 65536 cases (256 Ko), pour trier les valeurs sur 16 bits.
    Sachant que tout le monde a 8 Mo maintenant (sur PC), on voit l'interet... On pourrait meme trier sur 24 bits seulement, ce qui fait un traitement en une passe, et ce qui ne consomme que 16 Mo :-) (pour l'an 2006 je pense) Et pour les petits veinards de l'an 2996, en une passe : 4 Go de Memoire :-)

  3. Ce tri ne marche malheureusement pas pour les entiers signes (j'ai oublie de le dire). Donc, en entree de la routine, ajoutez 128 (ou 32768) a toutes vos valeurs, et en sortie, faites l'inverse... (Sauf si il y a une meilleure methode, ce qui ne m'etonnerais pas... Si vous en avez une, faites le moi savoir!)

Voila, c'est fini maintenant. J'espere que vous avez a peu pres compris. Et si vous avez des remarques, n'hesitez pas : un mail, ou venez sur #demofr!

- Phar / Flower Corp.