%  flashsort: Version pour Luminy 98

\documentclass[11pt,twoside]{report}
\usepackage[latin1]{inputenc}
\input cours_00.tex
\setlength{\textwidth}{18cm}
\hoffset = -2.5cm
\oddsidemargin = 1.5cm
\evensidemargin = 1.5cm
\homot{1}

\newcommand{\para}[1]{\vspace*{2mm}\hspace*{1cm}{\bf #1}}

\begin{document}

\vspace*{-1.5cm}
\setcounter{section}{0} \thispagestyle{empty}
\bc
{\bf \Large
\makebox[19cm]
{\begin{minipage}[t]{7cm}
Luminy 98  \end{minipage}
\hfill
\begin{minipage}[t]{10cm}
\begin{flushright} D Goffinet \\ 9 rue de la république \\ 42000 St-Etienne \\04 77 25 40 30 \\ goffinet@anais.aurecvideo.fr \end{flushright}
\end{minipage}
}}
\ec

\vspace*{1cm}
\bc {\LARGE \bf flashsort, un tri par classements} \ec

\vspace*{1cm} une idée à retenir: ne plus confondre trier et
classer \vspace*{1cm}

{\bf\Large 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 \og
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 \og 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 \fbox{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 \verb°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
\verb°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)

\vspace*{5mm}{\bf\Large 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,... \sum 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 \og 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é


\vspace*{5mm}{\bf\Large des expérimentations}

        Les expérimentations m'ont fait découvrir plein de chose
\begin{itemize}
\item quand je trie avec des entiers à 2 ou 4 chiffres flashsort
gagne sur camlsort
\item avec des entiers à 10 chiffres flashsort
perd! comme c'est le coût des comparaisons qui devait favoriser
flashsort, j'en ai \og déduit" (?) que camlsort devait faire appel
à une librairie non invoquée lors d'un appel à \emph{une}
comparaison.

\item 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

\item  Mes expérimentations m'ont également fait découvrir
que camlsort était ... lui aussi linéaire, l'épaisseur du mystère
croît
\item 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:
        \bi \item à partir de 5000 flashsort gagne en vitesse
                sur camlsort
                \item camlsort ne dépasse pas 81920 (je partais
de 20 et je doublais la taille à chaque fois), au delà on a droit
à \verb°Out_of_memory°
                \item flashsort trie joyeusement (?) des tableaux
de 1 310 720 réels
        \ei


\item voici le résultat bien net en floatants :

        \verb°pour taille =81920   durée de camlsort:    26.97°

        \verb°pour taille =81920   durée de flashsort:   12.41°

\end{itemize}

\vspace*{5mm}{\bf\Large le programme}

        Je l'ai essayé avec des float et des int, le type étant
\verb°machin vect°, la fonction de calcul de la classe d'un terme
utilisant des \verb°float_of_int° et des \verb°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)

\begin{verbatim}
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êmes *)
          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;
;;
\end{verbatim}

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

        La fonction \verb°cumule° que vous devinez transforme alors
la liste \og vectorielle" de taille de classes en la liste \og
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 à \emph{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 \og 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

\vspace*{5mm}{\bf\Large questions de complexité}

\para{un résultat expérimental qui m'a étonné}

Avec des vecteurs de 200 000 int, {\bf le premier des cycles} de
permutations décrit ci-dessus range environ 199 900 termes.
Parfois les 200 000 sont rangés, le \og 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!

\vspace*{5mm}\para{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

\vspace*{5mm}\para{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é:

\bi \item 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 {\bf un} recalcul et on aura
2N opérations floatantes
\item la fonction cumule: M opérations entières
\item 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
\item le tri par insertion de la fin M$\frac{(N/M)^2}{2}$
(je mesure ici avec le pire cas) \ei

Le temps de calcul est ainsi de la forme $\a N+\b M+ \g 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{\b/\g}$: \b\ c'est
le coût d'additions (plus un reliquat de gestion de la
classification), \g\ (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 \og être au
moins sûr de gagner en espace par rapport à camlsort" j'avais pris
5

\vspace*{5mm}{\bf\Large les défauts}

\vspace*{5mm}\para{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 \verb°float_of_int° et \verb°int_of_float° et en
calculant en rationnels (?)

\vspace*{5mm}\para{contraintes de type}

        flashsort peu enclin au polymorphisme ...

        La classification ne compare pas les termes entre eux
 elle utilise une \og valeur" des termes qui est numérique.
 Ci-dessus j'ai pris comme fonction \og 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?

\vspace*{5mm}  \para{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 \og boîte noire" comme
camlsort ou ceux utilisés dans les tableurs ou les logiciels de
calcul formel


\vspace*{1cm}{\bf\Large le travail qui reste à faire}

\vspace*{5mm} \para{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

\vspace*{5mm} \para{déterminer le rapport N/M}

de façon adaptative selon les types triés

\vspace*{5mm} \para{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

\vspace*{5mm} \para{ce que j'ai oublié}

        merci de me le dire
\end{document}
