Algorithmes de tri linéaires

Les algorithmes de tri de complexité $O(n \texttt{log} n)$ font leur travail uniquement en comparant les éléments du domaine deux à deux. On peut prouver que cette complexité est optimale pour ce type d'algorithmes.

Pour faire mieux, il faut donc abandonner la simple comparaison. Si le domaine est relativement petit et relativement compact, on peut faire correspondre les éléments du domaine à une suite d'entiers telle que la différence entre le plus grand et le plus petit est relativement petite. Autrement dit, on ne doit pas avoir trop de trous parmi les entiers de cet intervalle, à savoir des entiers qui ne correspondent pas à un élément du domaine.

Un exemple relativement typique est une application nécessitant de trier des personnes vivantes par année de naissance. Ici, il y a rarement plus de 100 ans de différence entre le dernier et le premier né et jamais plus de 200. C'est un exemple de domaine très compact.

L'algorithme de tri que nous allons présenter s'appelle tri par casier (en Anglais : bucket sort). C'est un algorithme qui nécessite un peu d'espace mémoire supplémentaire pour faire son travail. Si la séquence à trier est une liste, il nécessite un vecteur temporaire de la taille du domaine à trier, dans notre exemple, environ 100. Si la séquence est un vecteur, il nécessite deux vecteurs temporaires de cette taille. C'est souvent un prix raisonnable à payer pour un algorithme très rapide.

L'algorithme sur les listes contient quatres étapes :

1. déterminer le plus petit et le plus grand élément de la liste, et calculer la taille du domaine,
2. créer un vecteur de listes de la taille du domaine contenant une liste par élément du domaine,
3. parcourir la liste en insérant chaque élément au début de la liste correspondante,
4. concaténer les listes du vecteur.

Toutes ces étapes ont clairement une complexité $O(n)$.

Voici le code :

triparcasier.lisp

L'exemple suivant montre la différence en temps d'exécution entre ce code et la fonction primitive sort sur une liste de taille $100000$ ne contenant que des éléments 5.

* (progn (setf *l* (make-list 100000 :initial-element 5)) nil)

NIL
* (time (progn (setf *l* (sort *l* #'<)) nil))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 1.74 seconds of real time
 1.46 seconds of user run time
 0.11 seconds of system run time
 [Run times include 0.57 seconds GC run time]
 0 page faults and
 6999704 bytes consed.
NIL
* (time (progn (setf *l* (bucketsort *l*)) nil))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 0.11 seconds of real time
 0.09 seconds of user run time
 0.0 seconds of system run time
 0 page faults and
 0 bytes consed.
NIL
*

Pour trier un vecteur, les choses se compliquent un peu. Il est bien sûr possible de convertir le vecteur en liste, puis de trier la liste, et enfin re-convertir la liste en vecteur. Cette méthode est souvent plus rapide que trier le vecteur avec un algorithme $O(n\texttt{log} n)$ :

* (progn (setf *v* (make-array '(100000) :initial-element 5)) nil)

NIL
* (time (progn (sort *v* #'<) nil))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 4.94 seconds of real time
 4.04 seconds of user run time
 0.33 seconds of system run time
 [Run times include 1.46 seconds GC run time]
 0 page faults and
 25034752 bytes consed.
NIL
* (time (progn (coerce (bucketsort (coerce *v* 'list)) 'vector) nil))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 0.22 seconds of real time
 0.19 seconds of user run time
 0.01 seconds of system run time
 0 page faults and
 1198192 bytes consed.
NIL
*

Mais, on peut faire mieux. En effet, le problème de cette solution est la quantité de mémoire allouée (mais on remarque que sort alloue de la mémoire aussi). De plus, cette mémoire correspond à des cellules de listes, qui doivent être parcourues par le ramasse-miettes. Nous allons montrer comment s'en sortir avec deux vecteurs temporaires de la taille du domaine.

Pour comprendre cette technique, imaginons que le vecteur à trier soit celui indiqué dans la figure 24.5.

Figure 24.5: Exemple de vecteur à trier

Comme pour les listes, la première étape consiste à calculer le plus petit et le plus grand éléments. Dans notre exemple, le plus petit élément est 2 et le plus grand 7.

La deuxième étape calcule le nombre d'éléments de chaque valeur du domaine. Dans notre exemple, il y a $3$ éléments de valeur 2, $2$ éléments de valeur 3, $3$ éléments de valeur 4, $2$ éléments de valeur 5, $0$ éléments de valeur 6 et $2$ éléments de valeur 7.

Puis, on crée deux vecteurs de la taille du domaine qui indiquent autant d'intervalles que d'éléments du domaine. Chaque intervalle signifie le début et la fin des indices dans le vecteur où seront ultérieurement stockés les éléments correspondant à l'intervalle. La figure 24.6 montre ces deux vecteurs pour notre exemple.

Figure 24.6: Vecteurs indiquant les intervalles

Finalement, les éléments du vecteur sont déplacés vers leurs places définitives. Pour cela, chaque intervalle calculé pendant l'étape précédente est considéré à la fois comme un endroit où sont stockés des éléments non encore à leur place et comme un espace libre pour stocker les éléments à leur place définitive. À chaque itération de cette étape, un élément non encore à sa place est considéré. Sa place finale est calculée par le vecteur de gauche à l'indice donné par l'élément même. L'élément est échangé avec celui qui occupait sa place finale et le début de l'intervalle est incrémenté. Cette procédure se poursuit tant qu'il existe un intervalle non vide. Les premières itérations de cette étape sont illustrées par les figures 24.7 et 24.8.

Figure 24.7: Déplacement des éléments

Figure 24.8: Déplacement des éléments (suite)

La complexité de cet algorithme est clairement $O(n)$, car chaque itération est de complexité $O(1)$ et à chaque itération, un élément est positionné à sa place finale.

Voici le code :

triparcasier-vecteur.lisp

Afin d'apprécier la différence de performance, voici un exemple de tri d'un vecteur contenant un million d'éléments, d'abord avec la fonction sort prédéfinie, puis avec la fonction définie ci-dessus :

* (defparameter *v* (make-array '(1000000) :initial-element 5))

*V*
* (time (progn (sort *v* #'<) nil))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 56.94 seconds of real time
 53.3 seconds of user run time
 3.63 seconds of system run time
 [Run times include 17.98 seconds GC run time]
 0 page faults and
 302096984 bytes consed.
NIL
* (time (progn (bucketsort *v*) nil))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 4.97 seconds of real time
 4.93 seconds of user run time
 0.01 seconds of system run time
 15 page faults and
 0 bytes consed.
NIL
*

La fonction de tri linéaire est plus de $10$ fois plus rapide que la fonction sort prédéfinie.