Timsort - Timsort

Timsort

Classer	Algorithme de tri
Structure de données	Déployer
Performances dans le pire des cas	${\style d'affichage O(n\log n)}$
Le meilleur cas la performance	${\style d'affichage O(n)}$
Performances moyennes	${\style d'affichage O(n\log n)}$
Complexité spatiale dans le pire des cas	${\style d'affichage O(n)}$

Timsort est un algorithme de tri hybride stable , dérivé du tri par fusion et du tri par insertion , conçu pour fonctionner correctement sur de nombreux types de données du monde réel. Il a été implémenté par Tim Peters en 2002 pour être utilisé dans le langage de programmation Python . L'algorithme trouve les sous-séquences des données déjà ordonnées (exécutions) et les utilise pour trier le reste plus efficacement. Cela se fait en fusionnant les exécutions jusqu'à ce que certains critères soient remplis. Timsort est l'algorithme de tri standard de Python depuis la version 2.3. Il est également utilisé pour trier des tableaux de type non primitif dans Java SE 7 , sur la plate-forme Android , dans GNU Octave , sur V8 , Swift et Rust .

Il utilise des techniques de l'article de Peter McIlroy de 1993 "Tri optimiste et complexité théorique de l'information".

Opération

Timsort a été conçu pour tirer parti des exécutions d'éléments ordonnés consécutifs qui existent déjà dans la plupart des données du monde réel, les exécutions naturelles . Il itère sur les éléments de collecte de données en exécutions et en mettant simultanément ces exécutions dans une pile. Chaque fois que les exécutions en haut de la pile correspondent à un critère de fusion , elles sont fusionnées. Cela continue jusqu'à ce que toutes les données soient parcourues ; ensuite, tous les passages sont fusionnés deux à la fois et il ne reste qu'un seul passage trié. L'avantage de fusionner des exécutions ordonnées au lieu de fusionner des sous-listes de taille fixe (comme le fait le tri par fusion traditionnel) est que cela diminue le nombre total de comparaisons nécessaires pour trier la liste entière.

Chaque exécution a une taille minimale, qui est basée sur la taille de l'entrée et elle est définie au début de l'algorithme. Si une série est plus petite que cette taille de série minimale, le tri par insertion est utilisé pour ajouter plus d'éléments à la série jusqu'à ce que la taille de série minimale soit atteinte.

Fusionner les critères

Les pistes sont insérées dans une pile . Si | Z | | Y | + | X | , alors X et Y sont fusionnés et remplacés sur la pile. De cette façon, la fusion se poursuit jusqu'à ce que toutes les exécutions satisfassent i. | Z | > | Y | + | X | et ii. | Y | > | X | .

Timsort est un algorithme de tri stable (l'ordre des éléments avec la même clé est conservé) et s'efforce d'effectuer des fusions équilibrées (une fusion fusionne donc des séries de tailles similaires).

Afin d'obtenir la stabilité du tri, seules les séries consécutives sont fusionnées. Entre deux passages non consécutifs, il peut y avoir un élément avec la même clé à l'intérieur des passages. La fusion de ces deux exécutions changerait l'ordre des clés égales. Exemple de cette situation ([] sont des séquences ordonnées) : [1 2 2] 1 4 2 [0 1 2]

À la recherche de fusions équilibrées, Timsort considère trois exécutions au sommet de la pile, X , Y , Z , et maintient les invariants :

Si l'un de ces invariants est violé, Y est fusionné avec le plus petit de X ou Z et les invariants sont à nouveau vérifiés. Une fois les invariants maintenus, la recherche d'un nouveau run dans les données peut commencer. Ces invariants maintiennent les fusions comme étant approximativement équilibrées tout en maintenant un compromis entre le retard de la fusion pour l'équilibre, l'exploitation d'une nouvelle occurrence d'exécutions dans la mémoire cache et la simplification des décisions de fusion.

Fusionner l'espace au-dessus

Pour fusionner, Timsort copie les éléments du plus petit tableau (X dans cette illustration) dans la mémoire temporaire, puis trie et remplit les éléments dans l'ordre final dans l'espace combiné de X et Y.

L'implémentation de tri par fusion d'origine n'est pas en place et elle a une surcharge d'espace de N (taille des données). Des implémentations de tri de fusion sur place existent, mais elles ont une surcharge de temps élevée. Afin d'atteindre un moyen terme, Timsort effectue un tri par fusion avec un temps et un espace plus petit que N.

Tout d'abord, Timsort effectue une recherche binaire pour trouver l'emplacement où le premier élément de la deuxième exécution serait inséré dans la première exécution ordonnée, en le gardant ordonné. Ensuite, il exécute le même algorithme pour trouver l'emplacement où le dernier élément de la première exécution serait inséré dans la deuxième exécution ordonnée, en le gardant ordonné. Les éléments avant et après ces emplacements sont déjà à leur place correcte et n'ont pas besoin d'être fusionnés. Ensuite, le plus petit des éléments restants des deux exécutions est copié dans la mémoire temporaire et les éléments sont fusionnés avec l'exécution la plus grande dans l'espace désormais libre. Si la première exécution est plus petite, la fusion commence au début ; si le second est plus petit, la fusion commence à la fin. Cette optimisation réduit le nombre de mouvements d'éléments requis, le temps d'exécution et le surcoût d'espace temporaire dans le cas général.

Exemple : deux exécutions [1, 2, 3, 6, 10] et [4, 5, 7, 9, 12, 14, 17] doivent être fusionnées. Notez que les deux séries sont déjà triées individuellement. Le plus petit élément du deuxième passage est 4 et il devrait être ajouté à la quatrième position du premier passage afin de préserver son ordre (en supposant que la première position d'un passage est 1). Le plus grand élément du premier passage est 10 et il faudrait l'ajouter à la cinquième position du deuxième passage afin de préserver son ordre. Par conséquent, [1, 2, 3] et [12, 14, 17] sont déjà dans leurs positions finales et les pistes dans lesquelles des mouvements d'éléments sont requis sont [6, 10] et [4, 5, 7, 9]. Avec cette connaissance, il suffit d'allouer un buffer temporaire de taille 2 au lieu de 5.

Direction de fusion

La fusion peut se faire dans les deux sens : de gauche à droite, comme dans le mergesort traditionnel, ou de droite à gauche.

Mode galop pendant la fusion

Les éléments (indiqués par la flèche bleue) sont comparés et le plus petit élément est déplacé vers sa position finale (indiqué par la flèche rouge).

Une fusion individuelle des séries R1 et R2 conserve le nombre d'éléments consécutifs sélectionnés à partir d'une série. Lorsque ce nombre atteint le seuil de galop minimum ( min_gallop ), Timsort considère qu'il est probable que de nombreux éléments consécutifs puissent encore être sélectionnés à partir de cette course et passe en mode galop. Supposons que R1 soit responsable de son déclenchement. Dans ce mode, l'algorithme effectue une recherche exponentielle , également connue sous le nom de recherche au galop, pour l'élément suivant x du parcours R2 dans le parcours R1. Cela se fait en deux étapes : la première trouve la plage (2 ^k − 1, 2 ^k+1 - 1) où x est. La deuxième étape effectue une recherche binaire de l'élément x dans la plage trouvée dans la première étape. Le mode galop est une tentative d'adaptation de l'algorithme de fusion au modèle d'intervalles entre les éléments dans les courses.

Tous les éléments rouges sont plus petits que bleus (ici, 21). Ainsi, ils peuvent être déplacés en bloc vers le tableau final.

Le galop n'est pas toujours efficace. Dans certains cas, le mode galop nécessite plus de comparaisons qu'une simple recherche linéaire . Selon les benchmarks effectués par le développeur, le galop n'est bénéfique que lorsque l'élément initial d'une manche n'est pas l'un des sept premiers éléments de l'autre manche. Ceci implique un seuil initial de 7. Pour éviter les inconvénients du mode galop, deux actions sont entreprises : (1) Lorsque le galop s'avère moins efficace que la recherche binaire , le mode galop est quitté. (2) Le succès ou l'échec du galop est utilisé pour ajuster min_gallop . Si l'élément sélectionné est issu du même tableau qui a renvoyé un élément précédemment, min_gallop est réduit de un, favorisant ainsi le retour au mode galop. Sinon, la valeur est incrémentée de un, décourageant ainsi un retour en mode galop. Dans le cas de données aléatoires, la valeur de min_gallop devient si grande que le mode galop ne se reproduit jamais.

Descente

Afin de tirer également parti des données triées par ordre décroissant, Timsort inverse les exécutions strictement descendantes lorsqu'il les trouve et les ajoute à la pile d'exécutions. Étant donné que les exécutions descendantes sont ensuite inversées aveuglément, l'exclusion des exécutions avec des éléments égaux maintient la stabilité de l'algorithme ; c'est-à-dire que les éléments égaux ne seront pas inversés.

Taille minimale d'exécution

L'algorithme Timsort recherche des séquences ordonnées de taille minimale, minruns, pour effectuer son tri.

Parce que la fusion est plus efficace lorsque le nombre d'exécutions est égal ou légèrement inférieur à une puissance de deux, et notamment moins efficace lorsque le nombre d'exécutions est légèrement supérieur à une puissance de deux, Timsort choisit minrun pour essayer de garantir la état antérieur.

Minrun est choisi dans la plage 32 à 64 inclus, de telle sorte que la taille des données, divisée par minrun , soit égale ou légèrement inférieure à une puissance de deux. L'algorithme final prend les six bits les plus significatifs de la taille du tableau, en ajoute un si l'un des bits restants est défini et utilise ce résultat comme minrun . Cet algorithme fonctionne pour tous les tableaux, y compris ceux inférieurs à 64 ; pour les tableaux de taille 63 ou moins, cela définit minrun égal à la taille du tableau et Timsort se réduit à un tri par insertion.

Une analyse

Dans le pire des cas , Timsort effectue des comparaisons pour trier un tableau de n éléments. Dans le meilleur des cas, qui se produit lorsque l'entrée est déjà triée, elle s'exécute en temps linéaire, ce qui signifie qu'il s'agit d'un algorithme de tri adaptatif . ${\style d'affichage O(n\log n)}$

Il est avantageux par rapport à Quicksort pour trier les références d'objets ou les pointeurs car ceux-ci nécessitent une indirection de mémoire coûteuse pour accéder aux données et effectuer des comparaisons et les avantages de la cohérence du cache de Quicksort sont considérablement réduits.

Vérification formelle

En 2015, des chercheurs néerlandais et allemands du projet européen FP7 ENVISAGE ont découvert un bogue dans la mise en œuvre standard de Timsort.

Plus précisément, les invariants sur les tailles d'exécution empilées assurent une limite supérieure serrée sur la taille maximale de la pile requise. L'implémentation a préalloué une pile suffisante pour trier 2 ⁶⁴ octets d'entrée et a évité d'autres contrôles de débordement.

Cependant, la garantie exige que les invariants s'appliquent à chaque groupe de trois exécutions consécutives, mais l'implémentation ne l'a vérifié que pour les trois premiers. En utilisant l' outil Key pour la vérification formelle du logiciel Java, les chercheurs ont constaté que cette vérification n'était pas suffisante, et ils ont pu trouver des longueurs d'exécution (et des entrées qui ont généré ces longueurs d'exécution) qui entraîneraient une violation des invariants plus profondément dans la pile. après que le sommet de la pile a été fusionné.

Par conséquent, pour certaines entrées, la taille allouée n'est pas suffisante pour contenir toutes les exécutions non fusionnées. En Java, cela génère pour ces entrées une exception array-out-of-bound. La plus petite entrée qui déclenche cette exception dans Java et Android v7 est de taille67 108 864 (2 ²⁶ ). (Les anciennes versions d'Android déclenchaient déjà cette exception pour certaines entrées de taille65 536 (2 ¹⁶ ))

L'implémentation Java a été corrigée en augmentant la taille de la pile préallouée sur la base d'une analyse du pire des cas mise à jour. L'article a également montré par des méthodes formelles comment établir l'invariant voulu en vérifiant que les quatre premières exécutions de la pile satisfont aux deux règles ci-dessus. Cette approche a été adoptée par Python et Android.

Les références

Lectures complémentaires

• Auger, Nicolas; Nicaud, Cyrille ; Pivoteau, Carine (2015). « Stratégies de fusion : du tri par fusion à TimSort » . hal-01212839 .
• Auger, Jugé, Nicaud, Pivoteau (2018). "Sur la complexité du pire des cas de TimSort" . ESA 2018.
• Sam Buss, Alexander Knop. "Stratégies pour un tri par fusion stable." SODA 2019.

Liens externes

• timsort.txt – explication originale de Tim Peters