Luminy 98

D Goffinet

9 rue de la république 42000 St-Etienne 04 77 25 40 30

goffinet@anais.aurecvideo.fr

flashsort, un tri par classements

une idée à retenir: ne plus confondre trier et classer

encore un tri!

Dans tout cours sur le tri (en particulier dans chacun de nos cours) se rencontrent deux ingrédients: la preuve de la minoration de complexité par O(n.ln(n)) et l’exemple du paquet de 52 cartes qui se trie en 52 placements (dès que la table sur laquelle on les étale est assez grande), cette apparente contradiction étant expliquée par nos soins en termes “d’informations supplémentaires”. En revanche, quand on doit ranger 1000 entiers à 6 chiffres on déconseille de les ranger directement dans 10^{6} cases car le “ramassage” des emplacements occupés va être trop coûteux

En Février 98, Karl-Dietrich Neubert publie dans DrDobb’s Journal les idées de l’algorithme flashsort: lui, il est allé bien plus loin que les ronronnements que je racontais dans le paragraphe précédent, il a trouvé un algorithme de tri en O(n) , les cas nécessitant O(n.ln(n)) apparaissent comme des pathologies.

Programmé en caml, flashsort est environ 1 à 2 fois plus rapide que le sort de la librairie caml (que ci-dessous je nommerai camlsort), le code que j’ai écrit étant pourtant encombré de re-calculs, de tests et d’affichages; qui plus est, il permet de trier des données environ 4 à 10 fois plus grosses (le sort de caml est (serait) un mergesort qui utilise de la place de recopie, flashsort est très économe, le facteur variable de 4 à 10 m’a laissé perplexe)

les idées

L’idée de flashsort garde ce qui est bon dans celle du rangement du paquet de cartes: on va regarder où chaque terme va aller. Pour prévoir approximativement les destinations de nos N termes, on détermine le plus petit (p) et le plus grand (g), on décide de diviser l’intervalle [p,g] en M morceaux égaux (on fixera ultérieurement M), et on parcourt nos N termes pour savoir combien d’entre eux vont aller dans le k-ième de ces M morceaux.

Une fois cela fait, on dispose de (n_{1}, n_{2}, ..., n_{M}) liste des cardinaux des images réciproques des M morceaux de [p,g]. En cumulant ces nombres on obtient (c_{0}, c_{0}, c_{2}, ...c_{n})=(0 ou 1, n_{1}, n_{1} + n_{2}, ... ∑ n_{k} = N) qui nous déterminent les intervalles de classement de nos termes.

On parcourt alors de nouveau notre ensemble: on prend le premier terme, on re-calcule sa classe, on retire celui qui est à l’endroit voulu et on range le premier dans ce trou, puis on examine celui qui vient d’être retiré, on re-calcule sa classe on retire celui qui est à l’endroit voulu et on range ... tout cela finira quand on rangera dans l’emplacement vide laissé par le premier de tous, celui que l’on avait retiré au début.

A ce stade, on a effectué un premier cycle de permutations mais le classement n’est pas fini, on cherche alors le premier des éléments non rangés dans leur classe de destination et on recommence

Une fois ce classement effectué, on a des classes d’effectifs “aux environs” de N/M qui restent à trier. On utilise alors un tri classique de petit ensemble pour les classer et le tour est joué

des expérimentations

Les expérimentations m’ont fait découvrir plein de chose

• quand je trie avec des entiers à 2 ou 4 chiffres flashsort gagne sur camlsort

• avec des entiers à 10 chiffres flashsort perd! comme c’est le coût des comparaisons qui devait favoriser flashsort, j’en ai “déduit” (?) que camlsort devait faire appel à une librairie non invoquée lors d’un appel à une comparaison.

• contrairement à ce que j’aurais imaginé, avec des tableaux de taille 20 000 ou plus, les durées de tri (pour la même taille et le même type) varient d’une fois à l’autre de 20 à 100 %. Avec camlsort c’est un peu plausible (cela dépend de l’ordre initial) avec Flashsort les variations sont plutôt de 20% mais c’est quand même invraisemblable, en dehors des mini-tris de la fin rien ne dépend de l’ordre

• Mes expérimentations m’ont également fait découvrir que camlsort était ... lui aussi linéaire, l’épaisseur du mystère croît

• pour pouvoir quand même faire gagner flashsort de façon nette, j’ai recommencé avec des réels et là cela semble moins irrégulier:

– à partir de 5000 flashsort gagne en vitesse sur camlsort

– camlsort ne dépasse pas 81920 (je partais de 20 et je doublais la taille à chaque fois), au delà on

    a droit à Out_of_memory

– flashsort trie joyeusement (?) des tableaux de 1 310 720 réels

• voici le résultat bien net en floatants :

pour taille =81920   durée de camlsort:    26.97
pour taille =81920   durée de flashsort:   12.41

le programme

Je l’ai essayé avec des float et des int, le type étant machin vect, la fonction de calcul de la classe d’un terme utilisant des float_of_int et des int_of_float

Je passe sur des classiques: recherche du min et du max en 3N/2, générations de tests et autres affichages. J’ai décidé de prendre M=N/tas, avec tas entre 5 et 10 et j’ai donc écrit la fonction de classement qui suit (la version ci-dessous a été extirpée de la fonction globale et modifiée)

let classifie_int gros = (* version pour le type int *)
     let long_gros=vect_length gros in
     let long_court=long_gros / tas in
     let mini=init_vect (fun n->(ref 0)) (long_court) in
     let (min,max)=pp_pg gros in (* calcul des valeurs extr^emes *)
     let echelle=(float_of_int (long_court-1) /. float_of_int(max- min)) in
let place val=(int_of_float (float_of_int( val - min)*.echelle)) in
for k=0 to (vect_length gros -1) do
           incr mini.(place gros.(k))done;
;;

Ce qui précède apparaît bien sûr comme sous fonction de la fonction de classement

La fonction cumule que vous devinez transforme alors la liste “vectorielle” de taille de classes en la liste “affine” des abscisse de bouts de classes, il ne reste plus qu’à effectuer les permutations

Le premier élément à être rangé est tout simplement le premier du tableau, chaque rangement va être effectué à la dernière position libre de sa classe: quand donc on aura à ranger un terme dans la classe 1, on ne le rangera pas dans le trou initial, mais à l’autre bout de ladite classe, si bien que quand on en arrivera à ranger un élément dans le trou initial on saura avoir épuisé la première classe. Pour trouver le premier de ceux qui restent encore à classer, il suffit de parcourir le tableau jusqu’à trouver un élément qui n’est pas dans sa classe: on reprend alors un cycle permuteur

Les “difficultés” de programmation: comme pour Quicksort il faut être soigneux avec les cas d’extrémités d’intervalles, c’est plus facile que Quicksort

Quand tous les éléments sont classés, un tri par insertion les range rapidement

questions de complexité

un résultat expérimental qui m’a étonné Avec des vecteurs de 200 000 int, le premier des cycles de permutations décrit ci-dessus range

environ 199 900 termes. Parfois les 200 000 sont rangés, le “pire cas” m’a laissé avec 2000 termes non classés. Bien sûr, j’ai tout fait pour en rangeant dans la queue de mes classes après avoir enlevé l’élément de tête, mais j’étais loins de m’attendre à cela!

les mauvais cas de flashsort Toute l’idée est que les termes vont sagement à peu près s’équirépartir dans les classes, mais on peut

bien sur prendre un ensemble avec un très petit terme, un très grand, tous les autres tassés dans l’une des classes, le classement aura alors été une perte de temps. On pourra alors recommencer flashsort sur la classe récalcitrante, mais elle pourra bien sûr avoir elle aussi été choisie selon ce mode de répartition: le pire cas de flashsort est un fractal choisi en fonction des N et M, c’est hélas fréquent

le choix de M Peut fort bien être dicté par la place mémoire: on utilisera au total N+M places mémoires, les valeurs

que nous allons trouver optimales fournissent M aux environs de N/5, je suppose qu’il y a effectivement N/5 rangements d’entiers disponibles

Si on dispose de plus de place mémoire (plus de 2N), tous les recalculs d’adresse que j’ai mentionnés ci-dessus sont inutiles: on peut stocker les adresses avec les termes. Si on a un peu de place (entre 1.1N et 2N) on stocke un booléen qui dit si un terme est rangé: cela évitera de recalculer sa classe. Dans la version que j’ai programmée je recalcule tout à chaque fois.

Passons a l’analyse de complexité:

• le coût de la classification: si la classe n’est calculée qu’une fois, le coût est de N opérations floatantes, si on doit en recalculer, le pire sera un recalcul et on aura 2N opérations floatantes

• la fonction cumule: M opérations entières

• les permutations: comme j’ai déjà compté ci-dessus les calculs et éventuels recalculs de classe, il ne reste plus que N copies de termes du type que l’on trie

• le tri par insertion de la fin M\frac{(N/M)^{2}}{2} (je mesure ici avec le pire cas)

Le temps de calcul est ainsi de la forme αN + βM + γN^{2}/M. Quand, pour un N donné je cherche le meilleur M, je cherche le minimum de la fonction précédente, N/M = \sqrt{β/γ}: β c’est le coût d’additions (plus un reliquat de gestion de la classification), γ (une estimation moyenne du tri par insertion) a été estimé par Wirth et Sedgewick comme 3/8 (Neubert dixit, je n’ai pas vérifié). Tout cela fait choisir un rapport N/M aux alentours de 3 ou 4. Pour économiser de la place et “être au moins sûr de gagner en espace par rapport à camlsort” j’avais pris 5

les défauts

détails de la façon dont est programmée la fonction de classement, la dernière classe n’a qu’une valeur, il

faudrait arranger cela, mais si on doit faire un test d’égalité à chaque fois, on y perd, alors on va dire que la dernière classe a un rôle de sentinelle

pour la version en entiers, on irait peut-être plus vite en éliminant les float_of_int et int_of_float et en calculant en rationnels (?)

contraintes de type flashsort peu enclin au polymorphisme ... La classification ne compare pas les termes entre eux elle utilise une “valeur” des termes qui est

numérique. Ci-dessus j’ai pris comme fonction “valeur” l’identité, on peut imaginer d’autres cas (attributions de valeurs aux chaînes de caractères, codage lexicographique d’arbres ou d’expressions rationnelles) mais bizarrement (ou, peut être, bien sûr?) ils semblent spontanément engendrer un caractère fractal dans l’ensemble de données. L’usage humain de données est il automatiquement fractal?

Je ne ferai pas confiance à flashsort pour trier les mots d’un texte dans une analyse syntaxique ou dans une recherche d’égalité de deux formules. Un pré-hachage traduisant le biaisage humain des données suffirait-il?

usage éventuel J’imagine qu’une implantation possible comporterait un rappel automatique avertissant l’utilisateur

du danger des données fractales et lui proposant d’opter pour un robuste tri par tas en cas de danger décelé par une non quasi-équirépartition des effectifs de classe .

On est loin d’un confortable tri “boîte noire” comme camlsort ou ceux utilisés dans les tableurs ou les logiciels de calcul formel

le travail qui reste à faire

essayer de déceler les fractals en une passe c’est bien optimiste! On peut par contre surveiller les effectifs des classes et au delà d’un seuil

d’anomalie (?) passer la main a un tri robuste

déterminer le rapport N/M de façon adaptative selon les types triés

améliorer le petit tri final J.P.Barani et M.Pages se sont intéressés aux tris minimaux de petits ensembles, il doit y avoir moyen

d’associer tout cela

ce que j’ai oublié merci de me le dire