Plus rapide que QuickSort :

A-Sort

Article paru dans la revue Pascalissime, N°59 Juillet-Septembre 1994

Le présent document diffère légèrement du texte initialement paru, en particulier pour tenir compte de sa présentation en HTML.

 

1. Motivation

Au cours du mois d'avril 1994, j'ai découvert sur Compuserve un fichier dont le résumé annonçait fièrement comporter la description d'un algorithme de tri, ALPHASORT, plus rapide que celui bien connu de QuickSort. Intrigué, j'ai immédiatement récupéré ce fichier et j'ai commencé l'étude du texte qu'il comportait.

Il s'agissait en fait de la description de surface d'un brevet que l'auteur, Al Beechick, avait déposé sur l'algorithme en question.En revanche, le texte comportait une description des deux structures de données employées, ainsi que de l'idée de base pour les utiliser.Armé de ces renseignements, je me suis mis au travail pour réinventer l'algorithme complet et écrire le code correspondant. De cette façon, je pourrais vérifier les assertions de l'auteur.

Pour vous inciter à lire la suite, je vous donne immédiatement le résultat. Oui, AlphaSort est plus rapide. Mais il l'est seulement dans certaines conditions.

 

2. Rappel sur les algorithmes de tri

Les algorithmes de tri peuvent être divisés en deux classes: celle qui trie par comparaison des clés et celle qui ne le fait pas. QuickSort utilise les comparaisons, il est donc de la première classe. AlphaSort est de la seconde classe, car il utilise le tri par radical (radix sort).

AlphaSort porte son nom, parce qu'il trie en plaçant les clés d'après les lettres de l'alphabet, dans des boites. Cela exclus le besoin de comparaisons. En plus des lettres de l'alphabet, AlphaSort trie des nombres ou n'importe quel caractère reconnaissable par l'ordinateur. Cette manière de placer les clés dans des boites d'après les lettres qui les composent s'appelle : tri par radical.

AlphaSort est un tri par radical qui trie en plaçant les éléments dans les boites grâce aux lettres contenues dans les clés. Parler de lettres est un abus de langage. Il serai plus exact de parler de digits, car l'algorithme peut trier indifféremment tout type de clé : alphabétique, numérique, etc. Mais pour fixer plus facilement les idées, je parlerai de lettres.

Le tri par radical existe depuis longtemps dans la littérature informatique. Deux formes peuvent exister : en partant de la fin de la clé ou en partant du début de la clé.

 

2.1. Tri par radical LSD (Least Signifiant Digit)

Supposons que notre liste soit constituée des mots suivants: jour, mois, val, loi, vert, ver, gui. Nous allons commencer à la trier en distribuant les mots dans des boites en fonction de la quatrième lettre, puis de la troisième, seconde et enfin première lettre.

Passe 1 (sur la lettre n° 4)
r
 
 
 
jour
s
 
 
 
mois
t
 
 
 
vert
 non-traités 
gui
ver
loi
val

 

Passe 2 (sur la lettre n° 3)
i
 
mois
gui
loi
l
 
 
 
val
r
 
 
vert
ver
u
 
 
 
jour

 

Passe 3 (sur la lettre n° 2)
a
 
 
 
val
e
 
 
vert
ver
o
 
jour
mois
loi
u
 
 
 
gui

 

Passe 4 (sur la lettre n° 1)
g
 
 
 
gui
j
 
 
 
jour
l
 
 
 
loi
m
 
 
 
mois
v
 
vert
ver
val

 

Le détail de la gestion des boites est hors du propos de cet article. Sachez cependant que cette méthode nécessite pas mal de mémoire supplémentaire.

Vous remarquerez surtout que pour que le tri soit effectif avec cette méthode, tous les caractères des clés doivent être examinés.

 

2.2. Tri par radical MSD (Most Signifiant Digit)

Commencer par le chiffre le plus significatif, cela signifie que seulement une fraction des lettres demande à être examinée, au lieu de toutes dans le tri par radical LSD. Par exemple, si la première passe a pour résultat un placement unique de la clé, alors le reste des lettres n'a pas besoin d'être examiné. Dans l'exemple précédent les mots gui, jour, loi et mois ne sont pas examinés au-delà de la première lettre. Ceci élimine les passes inutiles, et a pour résultat une efficacité maximum.

Bien que cette idée soit particulièrement séduisante, le tri par radical MSD été abandonné pendant plusieurs décennies car les problèmes soulevés par l'utilisation de la mémoire pour conserver trace des boites n'étaient pas résolus.

D'après les études faîtes à ce sujet, le démarrage par le chiffre le plus significatif aurait pour résultat la multiplicité des boites, et utiliserait par conséquent une masse énorme de mémoire.

Résoudre ce problème de gestion de la mémoire est la clef d'un tri plus rapide. AlphaSort l'a fait.

 

3. Les concepts d'AlphaSort

Le concept majeur d'AlphaSort est que seulement le minimum nécessaire de passes soit effectué pour trier la liste, comme à la main. Quand il examine les lettres, il commence par la lettre la plus significative (MSD). Il commence donc au début de la clé. Par exemple, pour une liste de 10 articles quelconques, il y a une forte probabilité que la liste entière puisse être triée en une passe. Si par hasard, deux clés dans la liste commençaient avec la même lettre, alors une passe additionnelle serait faite uniquement sur les lettres non-examinées de ces deux clés.

Le pire scénario pour AlphaSort est l'existence d'un grand nombre de doubles ou similaires dans la liste à trier. Cela implique des passes supplémentaires pour arriver à une combinaison unique de lettres de début pour chaque article. Même dans ce cas, il se compare favorablement avec le tri par radical LSD, parce que celui-ci examine toujours toutes les lettres de toutes les clés.

Donc le temps de tri dépend de l'apparence de la liste plus que de sa taille. La classe d'algorithme qui utilise les comparaisons sera toujours désavantagée, parce qu'AlphaSort ne les utilise jamais. La nécessité de multiplier les comparaisons nuit à l'efficacité.

AlphaSort peut être décrit comme un tri par calcul d'adresse, parce qu'il place les clés dans des emplacements prédéterminés de la mémoire. Il ne place pas réellement la clé elle-même, parce que les clés ne sont jamais déplacées, mais un pointeur sur la clé va dans l'emplacement mémoire prédéterminé.

La première passe examine la première lettre de chaque clé. Tout les A sont chaînés ensemble en mémoire, tout les B sont chaînés ensemble en mémoire, et ainsi de suite. Les clés ne sont pas déplacées, mais la mémoire lie leurs adresses ensemble de manière qu'ils puissent être accessibles pour la prochaine passe. La seconde passe examine la seconde lettre, non pas la seconde lettre de chaque clé dans la liste, mais seulement la seconde lettre des clés commençant avec A. La troisième passe examine également la troisième lettre du plus grand groupe de clés dans la liste. Dans la plupart des cas une combinaison unique des premières deux ou trois lettres permet aux clés d'être triés rapidement. Dans les autres cas, lorsque les autres premières lettres sont les mêmes, alors des passes supplémentaires sont nécessaires pour trier de telles clés. Jamais une lettre n'est examinée inutilement. Le nombre de passes est gardé à un minimum absolu.

Avant d'avoir vu la liste, il sait déjà quel plage de valeurs sera utilisée. Celle-ci est la plage des caractères reconnaissables par l'ordinateur, qui va de 0 à 255 pour tous les inclure. Le programmeur peut resserrer la plage, en fonction de l'application. Par exemple, le programmeur peut décider de resserrer la plage de 0 à 127. Ou, si le programmeur sait qu'il n'y a pas de codes de contrôle utilisés dans l'application, alors il peut resserrer la plage encore plus, en commençant avec 32, par exemple. Plus restreinte est la plage, plus AlphaSort travaille rapidement.

La boite elle-même contient juste des pointeurs sur la dernière clé de cette liste. Donc, les boites n'ont pas besoin de contenir tous les pointeurs vers les clés dans chaque boite, parce qu'il est économiquement suffisant que le système soit capable de localiser immédiatement seulement la dernière clé de chaque boite.

Les structures de données nécessaires sont constituées de deux grands tableaux et d'un petit (?) tableau. Premièrement, un tableau de chaînes stocke la liste à trier. Deuxièmement, un tableau de nombres entiers, appelé "Pisteur de clé", stocke des pointeurs vers les clés dans la liste. Ces deux grands tableaux sont de la taille de la liste à trier.

Le dernier tableau est un tableau à deux dimensions de nombres entiers. Une dimension correspond à la plage d'octets possibles (tel que de A à Z; ou en termes d'ordinateur, les caractères 0 jusqu'à 255 ou 0 jusqu'à 127). L'autre dimension correspond à la largeur possible des clés (tel que 30 en cas de tri d'une base de données dont le plus grand champ est long de 30 caractères). Ce tableau est appelé Pisteur de lettre. Une dimension du tableau garde trace de la clé examinée, si c'est la première lettre, la seconde, la troisième, et ainsi de suite. L'autre dimension garde trace de la lettre examinée, si c'est A, ou B, ou C et ainsi de suite.

Par conséquent, tout emplacement particulier du tableau Pisteur de lettre correspond à une certaine lettre et à la place de cette lettre. La valeur stockée en tout emplacement de Pisteur de lettre est un entier qui agit comme un pointeur. L'entier pointe vers un index dans le tableau Pisteur de clé. Ce pointeur désigne la dernière, ou la clé la plus récemment traitée, dans un groupe de clés.

Après que Pisteur de lettre désigne la clé la plus récente dans un groupe, Pisteur de clé traque le reste des clés de ce groupe. Comme les groupes sont subdivisés en groupes de plus en plus petits, à la manière du tri par radical, Pisteur de clé également garde trace de ces plus petits sous-groupes.

Donc, ces deux tableaux d'entiers travaillent ensemble. Pisteur de lettre et Pisteur de clé coopèrent pour garder trace des groupes et sous-groupes d'articles pendant le processus de tri. La manière dont ils travaillent ensemble permet d'utiliser moins de mémoire.

Le vieux problème du tri par radical MSD, comme nous l'avons évoqué est de garder trace des boites. Ces boites représentent des groupes de clés dans la liste. Ces groupes changent constamment pendant le processus de tri. De plus, les groupes deviennent plus petits et plus nombreux au cours de la progression du tri.

Le problème des boites est résolu par les deux tableaux d'entiers, Pisteur de lettre, qui se souvient de la dernière clé traitée et Pisteur de clé qui rappelle le reste du groupe. En premier, Pisteur de lettre pointe sur un index dans Pisteur de clé. Puis la valeur de l'index de Pisteur de clé pointe sur un autre index dans lui-même. Et la valeur de cet index à son tour pointe sur un autre index. Les valeurs continuent à pointer jusqu'à ce que la valeur zéro soit trouvée. La valeur zéro signale la fin du groupe.

Toutes ces valeurs qui pointent sur les index dans Pisteur de clé correspondent aussi au numéro d'enregistrement, à savoir aux numéros des clés stockées dans le tableau de chaînes. Par exemple, si le pointeur est 7, alors il correspond à la clé numéro 7, la 7ème clé dans le tableau de chaînes.

Lorsqu'une boite est retrouvée, elle est subdivisée en boites plus petites. Au cours de cette subdivision, les valeurs dans Pisteur de clé changent, une par une, à chaque clé traitée, avec pour résultat que les clés sont chaînées ensemble d'une nouvelle manière en fonction des nouvelles boites.

Les grandes boites sont divisées en boites de plus en plus petites, jusqu'à ce qu'il ne reste qu'une seule clé dans chaque boite.

 

4. Au cœur de l'algorithme

Nous voici maintenant au cœur du problème. Comment faire marcher tout cela ensemble et trier?

Tout d'abord, nos devons initialiser les deux tableaux "Pisteur ...". Il seront nommés tel que Al Beechick l'a fait :

Lo indique l'emplacement du début de la liste à prendre en considération et Hi l'emplacement maximum.

    {-Initialisation des structures de données}
    fillChar(WordTracker, ((Hi-Lo)+1)*SizeOf(word), 0);
    fillChar(LetterTracker, SizeOf(LetterArray), 0);

    {-Lecture et chaînage de la liste de chaînes}
    FOR I := Lo TO Hi DO BEGIN
      CharProcessed := Ord(UpCase(A[I,1]));
      WordTracker[I] := LetterTracker[1, CharProcessed];
      LetterTracker[1, CharProcessed] := I;
    END;

 

Après cette première phase, tout index de LetterTracker[1, lettre] différent de 0 contient le pointeur correspondant à la dernière clé du groupe de lettre. Le pointeur correspondant de WordTracker contient 0 si le groupe se termine. Sinon il contient un pointeur sur la clé précédente du même groupe.

La deuxième passe utilise ces indications pour trier les groupes comportant plusieurs clés. Last est un pointeur qui va nous permettre de pouvoir ensuite parcourir WordTracker pour sortir les clés triées. Parcourir LetterTracker en ordre inverse va nous permettre d'obtenir que Last contienne, à la fin, le premier pointeur sur le nouveau groupe constitué. En d'autres termes, cette phase doit travailler comme la première : à l'envers.

    Last := 0;
    FOR I := 255 DOWNTO 0 DO BEGIN
      IF LetterTracker[1, I] <> 0
      THEN BEGIN
        {il y a au moins une clé dans ce groupe}
        TmpPtr := LetterTracker[1, I];
        IF WordTracker[TmpPtr] <> 0
        THEN  {il y a au moins deux clés, on appelle une procédure}
              {qui va trier ce groupe récursivement}
          SecondPass(TmpPtr, 2, Last)
        ELSE  {ceci établi le lien avec le groupe précédent}
          WordTracker[TmpPtr] := Last;
        Last := TmpPtr;
      END;
    END;

 

Vous avez compris que la plupart du travail va se faire dans la procédure SecondPass. Cela est dû au fait que la lecture des pointeurs n'est pas identique dans la première passe et les suivantes. En réalité, au prix d'une initialisation préalable, la procédure de tri pourrait être entièrement récursive. Je vous laisse cette idée à mettre en application comme exercice.

SecondPass comporte deux phases identiques à celles que nous venons de voir. La première phase parcours les pointeurs du groupe qu'elle doit trier. EmptyPtr est un pointeur particulier qui sert à chaîner les clés qui n'ont plus de lettres à examiner. Par exemple, si nous devons examiner la troisième lettre et que la clé soit Jo, celle-ci sera placée dans un groupe particulier. Mis à part le test de la longueur de la clé examinée et le parcours des pointeurs, cette phase est identique à celle décrite plus haut.

      EmptyPtr := 0;
      REPEAT
        TmpPtr := NextPtr;
        NextPtr := WordTracker[TmpPtr];
        IF CurrentLetter <= Length(A[TmpPtr])
        THEN BEGIN 
          CharProcessed := Ord(UpCase(A[TmpPtr, CurrentLetter]));
          WordTracker[TmpPtr] := LetterTracker[CurrentLetter, CharProcessed];
          LetterTracker[CurrentLetter, CharProcessed] := TmpPtr;
        END 
        ELSE BEGIN
          WordTracker[TmpPtr] := EmptyPtr;
          EmptyPtr := TmpPtr;
        END;
      UNTIL NextPtr= 0;

 

La deuxième phase est identique à la deuxième phase vue plus haut, à l'exception d'un test à ajouter. Ce test permet de déterminer si nous avons atteint la longueur maximum de clé que nous pouvons traiter. Dans le programme réalisé cette valeur est fixée à 128. Pour de sombres raisons de gain de temps il ne faut pas réinitialiser LetterTracker pour le rang de la lettre triée. L'instruction LetterTracker[CurrentLetter, I] := 0; permet de ne réinitialiser que le minimum nécessaire.

      FOR I := 255 DOWNTO 0 DO BEGIN
        IF (LetterTracker[CurrentLetter, I] <> 0)
        THEN BEGIN
          NextPtr := LetterTracker[CurrentLetter, I];
          IF WordTracker[NextPtr] <> 0
          THEN BEGIN
            IF CurrentLetter <> MaxStrLength
            THEN SecondPass(NextPtr, CurrentLetter + 1, Last)
            ELSE BEGIN
              {La longueur maximum de traitement est atteinte}
              {nous devons stopper la récursivité, et lier ce}
              {groupe avec les autres}
              TmpPtr := NextPtr;
              WHILE WordTracker[TmpPtr] <> 0
                DO TmpPtr := WordTracker[TmpPtr];
              WordTracker[TmpPtr] := Last;
            END;
          END
          ELSE WordTracker[NextPtr] := Last; {link}
          Last := NextPtr;
          LetterTracker[CurrentLetter, I] := 0;
        END;
      END;

 

Comme nous avons éventuellement un groupe de clés n'ayant pas pu être examinées, elles sont forcément inférieures à celles qui ont été traitées. Ce groupe particulier doit donc être placé devant les autres.

      IF EmptyPtr <> 0
      THEN BEGIN                  {chaînage des chaînes vides pour ce niveau}
        NextPtr := EmptyPtr;
        WHILE WordTracker[EmptyPtr] <> 0
          DO EmptyPtr := WordTracker[EmptyPtr];
        WordTracker[EmptyPtr] := Last;
      END;

 

Pour travailler sur la liste triée, appelez une procédure en lui passant le pointeur Last : WalkList(Last). Cette procédure aura l'aspect suivant :

    PROCEDURE WalkList(TmpPtr : Word);
    BEGIN
      REPEAT
        WriteLn(A[TmpPtr]);  {par exemple...}
        TmpPtr := WordTracker[TmpPtr];
      UNTIL TmpPtr = 0;
    END;

 

Le programme complet se trouve ici. Il utilise l'unité TpTimer de TurboPower Software pour vérifier les temps d'exécution. Pour ceux qui ne disposent pas de cette unité, il faut désactiver l'instruction $DEFINE UseTimer.

 

5. Comparaison avec QuickSort

Les tests montrent qu'AlphaSort s'exécute environ deux fois plus rapidement que Quicksort, et même encore plus pour certains styles de listes. L'algorithme Quicksort utilisé est livré avec Turbo Pascal de Borland. Les listes tests sont constituées à partir de l'extraction de mots uniques dans des fichiers de documentation d'origine américaine. RANDOM est un fichier en désordre, ORDER est trié en ordre ascendant et REVERSE est trié en ordre descendant. Le fichier test SAME est constitué de la chaîne abracadabraabracadabra répétée 5000 fois. En théorie il place AlphaSort dans son pire cas d'exécution.

Les temps montrés dans les tables suivantes ne comprennent que le tri de la liste en mémoire. Les temps de lecture de la liste depuis le disque dur ne sont pas comptés.Les temps indiqués sont en secondes et centièmes de seconde.

 

5.1. Comparaison sur un PC 386 40 Mhz

Le tableau 5.1 permet de comparer les temps de tri de des différentes liste de clés de 10 lettres. Le programme a été compilé en Turbo Pascal 7.0.

  Random Order Reverse Same
 Nb d'éléments  Quick Alpha Quick Alpha Quick Alpha Quick Alpha
100 0:05 0:03 0:05 0:03 0:03 0:03 0:05 0:01
1000 0:83 0:42 0:83 0:42 0:54 0:45 0:80 0:08
2000 1:79 0:94 1:79 0:94 1:24 0:92 1:78 0:16
3000 2:83 1:40 2:83 1:40 1:94 1:38 2:85 0:24
4000 3:68 1:88 3:68 1:88 2:62 1:87 3:93 0:32
5000 4:92 2:35 4:92 2:35 3:48 2:34 5:19 0:39

Tableau 5.1

Ces temps sont similaires à ceux indiqués par Al Beechick dans sa dissertation sur AlphaSort.

 

5.2. Comparaison sur un PC 486 33 Mhz

Le tableau 5.2 permet de comparer les temps de tri de des différentes liste de clés de 10 lettres. Le programme a été compilé en Turbo Pascal 7.0.

  Random Order Reverse Same
 Nb d'éléments  Quick Alpha Quick Alpha Quick Alpha Quick Alpha
1000 0:62 0:23 0:58 0:25 0:40 0:24 0:59 0:06
2000 1:32 0:51 1:32 0:52 0:91 0:50 1:31 0:12
3000 2:10 0:75 1:99 0:77 1:44 0:75 2:10 0:18
4000 2:74 1:01 2:71 1:03 1:93 1:01 2:89 0:24
5000 3:65 1:27 3:34 1:28 2:56 1:27 3:82 0:32

Tableau 5.2

 

6. Justification des performances

Je vais maintenant expliquer brièvement pourquoi AlphaSort s'exécute plus rapidement que Quicksort.

Quicksort utilise des partitions. Il divise une liste en deux, compare les clés dans chaque moitié, et échange les clés si nécessaire. Il sépare de nouveau les partitions et fait de nouveau des échanges. Chaque fois que deux clés sont échangées elles se rapprochent d'environ la moitié du chemin vers leur destination. A ce rythme elles doivent atteindre leur destination en Log2(N) passes. Par conséquent, chaque clé est déplacée plusieurs fois, chaque fois un peu plus près de sa destination finale. Chaque fois qu'une clé est déplacée, elle est déplacée deux fois plus près (en moyenne) de sa destination finale.

En assumant seulement 26 lettres dans l'alphabet, chaque passe d'AlphaSort obtient que la clé soit 26 fois plus près de sa destination. AlphaSort atteint souvent l'objectif en seulement 2 ou 3 passes. De plus chaque caractère d'une clé n'est examiné qu'une seule fois dans tout le processus de tri. Enfin, les clés ne sont pas déplacées physiquement.

 

7. Trier des nombres entiers

Comment AlphaSort peut-il manier les nombre entiers? Il examine les octets, lesquels peuvent être tout caractère alphanumérique. Il importe peu si l'octet est une lettre, un nombre, ou tout autre caractère spécial de l'ensemble de caractères reconnaissables par votre ordinateur.

Lors du tri de nombres entiers, cependant, vous aurez besoin de faire un petit ajustement. Faites la première passe sur la longueur du nombre entier, puis la seconde passe sur le premier octet du nombre entier. En d'autres termes, lors du tri de 10, 100, et 1000, les longueurs respectives sont 2, 3 et 4. Donc la première passe place les nombres entiers plus courts avant les plus longs, de façon que 10 finisse dans une boite différente de celle de 100. La seconde passe, alors, distingue 10 de 20, et ainsi de suite jusqu'à 99. Si votre nombre est du type STRING, vous pouvez penser à cela comme le tri sur l'octet zéro en premier puis l'octet un en second, etc.

 

8. Conclusions

L'algorithme qui a été décrit ici est une libre interprétation du texte original (voir en référence), sans aucun autre document disponible. Tel quel, il n'est plus rapide que QuickSort que si un travail supplémentaire sur les clés est réalisé, par exemple une confusion majuscule/minuscule. Si ce n'est pas le cas, QuickSort est toujours le meilleur.

La description des tests que Al Beechick a réalisés ne comportait aucune indication là-dessus. Il se peut qu'AlphaSort codé par son concepteur soit plus performant, bien que les temps que j'ai obtenu soient très proches des siens (je suis même semble-t-il un peu meilleur).

La question est « Peut-on faire encore mieux ? ». Eh bien, la réponse est OUI !

D'abord, il existe dans l'abondante littérature informatique des algorithmes de tri de nombres qui sont plus rapides que QuickSort. Malheureusement, ils sont souvent gros consommateurs de mémoire.

D'autre part, une version améliorée du programme ci-joint a été réalisée. Elle permet de trier jusqu'à 32000 clés et s'exécute 4,5 fois plus rapidement (sans une ligne d'assembleur). De plus elle est indifférente aux modifications apportées aux lettres de la clé : confusion des majuscules/minuscules par exemple. Elle bat QuickSort en toute circonstance.

Enfin, l'exigence de mémoire d'AlphaSort pour un tri sur la plage large et la limitation de longueur de la clé me semblait intolérable (64k pour Pisteur de clé [0..255, 1..128] + 64K pour Pisteur de lettre [1..32000]).

J'ai donc réfléchi un petit moment et écrit un algorithme basé sur d'autres idées (Beta Sort), abandonnées elles aussi depuis longtemps. Cela a donné un tri qui possède les avantages suivants :

Mais ceci est une autre histoire !...

Lionel Delafosse, juin 1994
révisé le 16 mars 1998
révisé le 24 janvier 1999

Vous pouvez télécharger les programmes de tests et le document original de Al Beechick ( ) en cliquant ici.

Référence DISCOURSE ON ALPHASORT, PATENT NO. 5,218,700,
COMPARISON WITH OTHER SORTING ALGORITHMS
Al Beechick, Copyright 1994 by Arrow Connection, P.O. Box 899
Pollock Pines CA 95726 USA, Phone: (916) 644-2341

 


Author's Home PagePapers Links Projects What's New ? What's New ?

Last updated on: 24 January 1999 ©  Lionel Delafosse