Et plus sur les sortes

Je me risquerais à soulever à nouveau ce sujet. Je vais commencer par un lien vers un article de Mikhail Opanasenko (oms7) , qui est très impressionnant en termes de volume de travail, ainsi qu'en nombre de liens cités. Il a commencé à préparer son matériel, ne connaissant pas cette publication, qui par la suite, après familiarisation, a conduit à la nécessité de son traitement substantiel. Pour ceux qui ont déjà lu cet article, je vous informe que dans mon matériel, des types de données plus divers sont étudiés, en particulier, les chaînes et les nombres réels, les bibliothèques boost et bsd sont utilisées, et certains autres sujets manquants dans l'article sont mentionnés.

Il existe des dizaines de façons différentes d'organiser les éléments de données dans l'ordre. Parmi ceux-ci, il y a ceux qui fonctionnent rapidement, tels que, par exemple, ils peuvent trier n'importe quel tableau de données situé dans la RAM de l'ordinateur en un maximum de minutes. Plus précisément, on peut dire qu'un tri rapide organise un milliard d'entiers dans un bon ordinateur personnel moderne en moins de cent secondes. Si vous utilisez des méthodes primitives et non rapides, par exemple, le tri à bulles ou le tri par sélection, pour trier un plus grand nombre d'éléments, le temps consacré à ce traitement de données peut dépasser toutes les attentes - un tel «traitement» peut en fait prendre plusieurs jours, semaines et même des années. Cette grande différence est due au fait que le temps de tri par des méthodes rapides est approximativement proportionnel à N log N , et primitif - N ² . Avec l'augmentation de N, la différence entre les deux valeurs devient très sensible. Par conséquent, il est raisonnable d'utiliser des méthodes primitives uniquement pour travailler avec de petites données, par exemple, sur des ordinateurs modernes, jusqu'à plusieurs milliers d'éléments. Il est également naturel de les utiliser pour enseigner les bases de la programmation et de la pensée logique, car elles sont beaucoup plus simples que les méthodes rapides.

Je voudrais comprendre les méthodes de tri existant dans les bibliothèques standard actuelles. Découvrez l'ampleur de la différence entre eux en termes de caractéristiques principales, de vitesse de travail et de caractéristiques. De plus, nous considérerons en cours de comparaison et d'exercices pour l'esprit quelques méthodes qui ne sont pas difficiles à mettre en œuvre. Il convient également de noter que l'optimiseur du compilateur GCC et éventuellement d'autres bons compilateurs fonctionnent très bien avec les sortes, accélérant le code plusieurs fois (parfois même plus de 5 fois).

Commençons par la méthode de tri à bulles comme la plus simple et la plus lente. Selon cette méthode, vous devez parcourir le tableau de données encore et encore, comparer les éléments voisins et changer leur place si l'ordre entre eux est rompu. Après chaque passage, au moins un élément (le plus grand ou le plus petit - dépend de l'ordre sélectionné) est à sa place. En plus de la simplicité, cette méthode présente un autre avantage: elle ne nécessite pas de mémoire supplémentaire. Une autre caractéristique de la méthode des bulles peut être notée - elle traite très rapidement les données déjà commandées et, dans certains cas, en fait l'une des méthodes les plus rapides. Si les données ne sont que partiellement ordonnées, cette méthode fonctionne plus rapidement avec elles, mais dans la plupart des cas seulement très légèrement. Pour les tests, j'ai utilisé l' implémentation suivante.

Une autre méthode lente est le tri par sélection. Ici, à chaque passage, les éléments les plus grands et les plus petits des données sont d'abord trouvés, puis ces éléments sont placés dans les positions extrêmes correspondant à l'ordre sélectionné. À l'étape suivante, nous trions les données sans ces éléments extrêmes. Cette méthode est aussi simple que le tri à bulles et ne nécessite pas non plus de mémoire supplémentaire, mais elle est nettement plus rapide. De plus, le tri par cette méthode effectue un nombre minimum record de permutations d'éléments de données. Par conséquent, lorsque les permutations sont beaucoup plus lentes que les comparaisons, l'ordre par la méthode de sélection peut être acceptable si le nombre d'éléments de données est petit. Voici ma mise en œuvre . Le plus souvent ce tri est réalisé, ne mettant en place qu'un seul élément par passe. Le tri en tas (ou pyramidal), qui sera discuté plus loin, est la version la plus avancée du tri en question.

Le code de la dernière méthode lente considérée, le tri par insertion, est probablement le plus court de tous les codes qui implémentent le tri, donc cette méthode est parfois utilisée par des tris rapides complexes pour les cas où le nombre d'éléments à trier est petit (plusieurs dizaines). Il ressemble un peu au tri par bulle, car ici et là les éléments voisins sont successivement comparés. Mais le tri par insertions recherche l'élément suivant pour la position correcte dans la partie déjà triée des données, et ne pousse pas simplement l'élément extrême vers la position extrême. Avec cette approche, aucune mémoire supplémentaire n'est également nécessaire. Comme le tri à bulles, le tri par insertion est très rapide sur les données ordonnées et plus rapide sur les données partiellement ordonnées. Dans ce dernier cas, nettement plus rapide que la bulle. Le tri par insertions est généralement un peu plus rapide que le tri par sélection. Et contrairement à ce dernier, il, comme le tri à bulles, est stable. Pire encore, le tri par insertion fonctionne avec des données dans l'ordre inverse, avec lequel il devient parfois le plus lent des plus lents. Pour les tests, l' implémentation suivante a été utilisée. Il peut être un peu accéléré si vous n'utilisez pas la recherche linéaire, mais binaire, par exemple, en utilisant la fonction std :: bsearch. Une accélération significative peut être obtenue en utilisant une structure de type liste, l'insertion d'un élément dans laquelle est très rapide. Vous pouvez également remarquer qu'il s'agit du tri le plus naturel - par exemple, il est généralement utilisé de manière intuitive lors de la lecture de cartes.

Le tri par shell est le plus simple parmi les méthodes rapides et convient parfaitement aux étudiants qui commencent tout juste à apprendre la programmation. Ce n'est qu'une modification du tri des bulles. La seule différence entre eux est que dans le tri Shell, la distance entre les éléments comparés est prise en variant d'une allée à l'autre, du plus grand dans la première passe, à 1 dans la dernière, de sorte que la méthode Shell dégénère en un tri à bulles primitif dans ces dernières passes. Donald Shell a publié l'algorithme de tri de base qui a obtenu son nom en 1959. Ainsi, c'est l'un des premiers tri universels qui fonctionnent rapidement. À titre de comparaison, l'algorithme de tri rapide a été publié deux ans plus tard, et le tri populaire ou le tri introspectif de Tim n'est devenu connu que dans les années 90. Plusieurs problèmes mathématiques non résolus intéressants sont associés au tri de Shell, dont le principal est de savoir comment sélectionner de manière optimale les déplacements entre les éléments comparés. Certaines séquences d'enregistrement ont été trouvées, par exemple A102549 . De telles séquences sont trouvées par des calculs colossaux, donc elles ont une très courte longueur, A102549 n'est que de 8 éléments, ce qui ne suffit que pour des données jusqu'à environ 3000 éléments. Pour les mégadonnées, les suites doivent être considérées presque au hasard. Les valeurs utilisées proches des puissances de 2, e , 2,25 et 3. Les nombres premiers proches des puissances de 2 ont montré les pires résultats, nettement inférieurs aux meilleurs. Mais les trois autres options se sont avérées à peu près les mêmes en termes d'impact sur les performances et probablement très proches de l'optimale. De plus, dans ces trois cas, l'utilisation de nombres premiers n'a pas donné d'avantages tangibles. Il est curieux que les biais proposés sur Wikipédia (avec une base de 2,25) basés sur des références aux travaux correspondants n'aient pas montré les meilleurs résultats sur les tests, bien que leurs différences par rapport aux meilleurs soient très insignifiantes (pas plus de 5-10%). L'utilisation de A102549 comme point de départ n'a également donné aucun résultat notable. Mikhail Opanasenko a également tenté de démêler le tri de Shell et a obtenu un résultat intéressant que les déplacements sélectionnés par la formule s _{n + 1} = 10s _n / 3 donnent un très bon effet et peut-être même proche de l'idéal. Mes résultats le confirment. Dans de nombreux cas, ce sont ces biais qui ont donné le meilleur résultat, même si ce n'était pas toujours le cas et l'écart par rapport au résultat le plus proche était assez faible (environ 5%). Mon code pour implémenter les triages Shell utilise de petites tables avec des décalages, bien que si vous n'utilisez pas de nombres premiers, alors ces décalages pour les tables peuvent être calculés presque instantanément, comme cela a été fait dans la mise en œuvre d'une des variantes données de ce tri.

Il est intéressant de noter que si nous prenons des décalages proches des puissances des triplets d'une manière légèrement différente et que nous utilisons un algorithme légèrement différent (voir implémentation ), alors sur des nombres 32 bits nous obtiendrons des vitesses proches des meilleures, mais sur des nombres plus longs et sur les lignes nous obtiendrons un ralentissement significatif, parfois plus de 100%. Les résultats pour le meilleur algorithme utilisé par oms7 sont également dans le tableau ci-dessous, mais bien qu'il montre de bons résultats dans l'ordre, il est loin derrière les leaders en termes de valeurs absolues.

Y aura-t-il jamais un moyen de trouver les meilleurs compensations? Peut-être, mais j'ose suggérer que ce n'est pas pour bientôt. Le tri shell est utilisé dans le noyau Linux, et dans au moins une bibliothèque C, son code est utilisé pour la fonction qsort () standard. Il a été théoriquement prouvé que la vitesse de tri optimale de Shell dans l'ordre n'est que légèrement plus lente que les méthodes logarithmiques rapides «réelles». En effet, la dépendance du temps moyen de traitement des données à leur taille pour un tri optimal de Shell est décrite par la formule ∽ N (log N / log log N ) ² , qui même pour les très grands N est très proche de la formule ∽ N log N typique pour les autres méthodes rapides. Habituellement, le tri Shell est souvent encore plus rapide que les méthodes théoriquement plus rapides et ne commence à leur céder que légèrement lors du traitement de tableaux assez volumineux (de l'ordre de 10 millions d'éléments). Ce tri n'a absolument pas besoin de mémoire supplémentaire et il se comporte de manière stable pour une grande variété d'options de remplissage des données, se comparant favorablement aux tri rapides. La méthode Shell ne possède pas la propriété de stabilité.

Le tri rapide n'est que légèrement plus complexe que l'algorithme Shell et reste l'un des moyens les plus rapides d'organiser des données dispersées de manière aléatoire. Cependant, ce tri présente plusieurs inconvénients. Elle a besoin de mémoire supplémentaire et pour de très rares cas cela fonctionne extrêmement lentement, selon une dépendance quadratique. L'idée principale de cette méthode est de diviser les données en deux parties: les données dans une partie devraient être plus ou moins (dépend de l'ordre sélectionné) que dans l'autre. Il existe plusieurs méthodes pour cette séparation. Idéalement, avec chaque division, les deux parties devraient être à peu près de la même taille, et pire que tout, lorsqu'une des parties s'avère être composée d'un seul élément pendant la division. Considérons plusieurs implémentations d'algorithmes de tri rapide, en particulier la méthode Hoar , dans laquelle un élément de référence divisant les données en deux parties est sélectionné au milieu des données triées.

Nous considérons également l' algorithme de Lomuto extrêmement compact, qui est parfois légèrement (environ 1%) plus rapide que la méthode Hoare considérée. Cependant, dans des cas particuliers typiques, par exemple sur des données ordonnées, inverses ou malovariantes, la méthode de Lomuto montre une lenteur extrême. De plus, parmi les options envisagées pour le tri rapide, celle-ci s'est avérée être la plus gourmande pour la taille de la pile lors des exécutions pratiques: lors du tri de tableaux relativement petits, seul ce type n'avait pas assez de 8 mégaoctets pour la pile, j'ai dû définir cette taille via ulimit more. Une telle avidité pour la pile entraîne de gros ralentissements lors du traitement des données volumineuses (des dizaines de millions de lignes), et j'ai du mal à appeler sa nature. Je peux seulement affirmer qu'il vaut mieux ne pas utiliser ce tri du paragraphe suivant avec de telles données.

La méthode Lomuto sélectionne le dernier élément comme élément de référence, mais il est possible d'implémenter un tri rapide sans aucun élément de support , plus précisément, la sélection d'un tel élément se produit ici à la suite d'une bissection de données déjà effectuée. Ce tri par caractéristiques de vitesse s'est avéré être proche de la méthode de Lomuto, bien qu'il soit généralement un peu plus rapide, et dans les cas extrêmes, il est sensiblement plus rapide que Lomuto, mais plus lent que Hoar.

En 2009, un algorithme de tri rapide à deux ancres a été publié, qui est devenu la norme pour le langage Java. Cet algorithme réduit le nombre de permutations de 20% par rapport aux meilleurs types, mais le nombre de comparaisons ne change pas. Son auteur est Vladimir Yaroslavsky. Cela fonctionne vraiment, en règle générale, plus rapidement que d'autres types rapides. Je l'ai optimisé un peu, en utilisant le fait connu depuis longtemps que sur l'architecture x86, le swap fonctionne généralement plus rapidement que l'affectation, et pour les chaînes C ++ c'est beaucoup, beaucoup plus rapide. Tous les tri rapides considérés jusqu'à présent n'ont pas la propriété de stabilité.

Une mémoire supplémentaire pour un tri rapide est nécessaire pour organiser les appels récursifs. Cependant, le deuxième appel de ce type peut être remplacé par une boucle, en optimisant la récursivité de queue , ce qui en termes de vitesse peut ne donner aucun gain, mais réduit considérablement la taille des données supplémentaires utilisées. J'ai implémenté l'option de tri Hoar avec cette optimisation. De plus, dans les programmes système, vous pouvez vérifier le pointeur de pile et s'il s'approche d'une valeur critique, vous pouvez simplement réinitialiser tous les appels récursifs et recommencer le tri - dans ce cas, il est évident que vous devez utiliser l'option de tri rapide qui ne ralentit pas sur les données presque ordonnées, par exemple , la version proposée ci-dessus de Hoar. La lutte contre l'utilisation de mémoire supplémentaire peut être considérée comme l'idée principale d'un tri rapide à partir de la bibliothèque de langage C standard dans GCC. Il a généralement abandonné la récursivité. Au lieu de cela, ils utilisent sa simulation, qui permet à un tiers de réduire la charge sur la pile. Le code s'est avéré assez gros, environ 150 lignes. À propos de ce tri, il y aura encore un peu de matériel ci-dessous.

Le tri par hachage peut être très rapide, proche de ∽ N. Cependant, il peut parfois fonctionner sur une dépendance quadratique. La vitesse de cette méthode de tri est très dépendante de l'entrée. Si les données sont réparties uniformément par la fonction de hachage sur le tableau auxiliaire, alors nous obtenons la relation linéaire la plus rapide. Et si toutes les données sont regroupées près de plusieurs "centres de masse" éloignés ou lorsqu'il existe de nombreux éléments de données identiques, c'est-à-dire lorsque de nombreuses collisions de hachage se produisent, alors nous obtenons le pire type de dépendance N ² . Comme pour le tri d'arbre, pour trier le hachage, vous avez besoin de beaucoup de données supplémentaires, dans la liste de codes ci-dessous, vous avez besoin, par exemple, de 12 octets supplémentaires pour chaque entier triable (int32, x86-64). Une propriété intéressante du tri par hachage est l'absence d'opérations de comparaison entre les éléments de données, ce qui distingue ce tri de tous ceux considérés ci-dessus. Plus précisément, ces opérations ne sont nécessaires que pour les collisions. Lorsque vous triez des données où la clé correspond à l'élément de données entier, vous pouvez utiliser un compteur supplémentaire pour le nombre d'éléments identiques, mais c'est plutôt une optimisation douteuse. Vous pouvez également utiliser l'arborescence binaire au lieu de la liste pour stocker les données de collision de hachage, ce qui accélère considérablement le travail pour des cas particuliers individuels lorsqu'il y a de nombreuses collisions, mais en général, lors de l'utilisation de l'arborescence binaire, dans de nombreux cas, il ralentit et cela malgré le fait que dans ce cas l'élément les données doivent stocker près de 100 octets d'informations supplémentaires. J'ai implémenté trois options de tri de hachage à l'aide d'un arbre binaire: l'une utilise un arbre non ordonné et les deux autres utilisent des arbres standard des bibliothèques std et boost. Le tri par hachage est pratiquement inapproprié pour trier les chaînes de texte, sauf pour les très courtes, car il est impossible de faire une bonne fonction de hachage pour ces données. Je n'ai pas pu adapter le hachage C ++ standard (unordered_multiset) pour le tri: j'ai essayé d'utiliser des fonctions de hachage monotones et des relations de classement au lieu de l'égalité - cela n'a pas fonctionné.

Le tri des tableaux est très similaire au précédent. Un tableau auxiliaire est également utilisé, où les valeurs sont entrées par la fonction de hachage. En cas de collision, il est nécessaire de déplacer le fragment continu des éléments occupés vers la position gauche ou droite, libérant ainsi la position indiquée par la fonction de hachage pour le nouvel élément. Pour obtenir une bonne vitesse, il est nécessaire que le réseau auxiliaire soit plusieurs fois (de 2-3) plus que celui d'origine. Avec une augmentation de la taille de la matrice auxiliaire, la vitesse n'augmente que jusqu'à une certaine limite, selon les données triées et la fonction de hachage qui leur est associée, puis (généralement de 4 à 5) diminue. La vitesse de fonctionnement est à peu près la même que celle du hachage, mais sur les bonnes données un peu plus rapide et sur les mauvaises données, elle est sensiblement plus lente. Ce type nécessite également beaucoup de mémoire supplémentaire. , , , , – 28 , , , , . . , .

, , , , , , , .

L'un des tri les plus rapides, qui n'utilisent jamais du tout de comparaison, est le tri au niveau du bit connu depuis le 19e siècle. (radix sort). – ( 8, 11 16 ). , . . ( LSD – Least Significant Digit), ( MSD – Most Significant Digit). . , : boost, ++, - ++. , , . , , , , . , , ( , ). , . ici , il est basé sur le code de l'article oms7 mentionné. L'option d'ordre des octets inversés est plus polyvalente et très bien adaptée au tri des chaînes. Cette option peut être implémentée sans utiliser de mémoire supplémentaire (le prix en est la perte de propriété de stabilité), comme cela se fait dans la fonction radixsort () de la bibliothèque bsd. Mon code oms7, , , , , sradixsort() bsd. , , , . - , , . « » . , , , ∽ N , mais le coefficient de proportionnalité dépend ici de la taille des éléments de données et pour les chaînes ou les nombres longs, il peut être assez visible.

Une option pour le tri MSD au niveau du bit est le tri par faisceau , une structure de données qui vous permet de placer efficacement les clés d'un tableau associatif. Mon implémentation , malgré l'optimisation de l'utilisation de la mémoire, s'est avérée très gourmande pour elle. Par vitesse, les meilleurs résultats ont été obtenus lors du tri des longues lignes.

De plus, nous considérerons certains tri qui peuvent être trouvés dans les bibliothèques standard.

Commençons par le rapide de la bibliothèque C standard (qsort, une variante de GCC), j'ai déjà écrit à ce sujet. Je peux seulement ajouter ici que ce tri ainsi que d'autres triages C (par exemple, les éléments suivants de la bibliothèque BSD) ne conviennent pas pour travailler avec des données d'objet, en particulier, des chaînes C ++, ce qui est dû au fait que ces données ne sont pas POD. Ayant la source, le problème peut être facilement résolu en remplaçant les opérations memcpy par des affectations régulières. Vous pouvez également remarquer que dans certaines bibliothèques C standard, ce tri n'est pas nécessairement rapide, il peut être remplacé par d'autres. Dans la version actuelle de GCC, ce tri a même la propriété de stabilité. Il y avait parfois des surprises avec les triages c mentionnés lors de la collecte de données, par exemple, lorsque vous travaillez avec le type std :: vector via un objet fonctionnel, cela pouvait créer des difficultés - je peux recommander de l'utiliser avec prudence avec les données d'objet. Selon les analyses, ce tri est parfois relativement lent: il est nettement inférieur en vitesse aux autres implémentations du tri rapide lorsque l'on travaille avec des nombres, mais quand on travaille avec des chaînes si c'est mieux, seul le tri avec deux points de contrôle le fait parfois avancer,mais sur de longues lignes, le qsort standard le dépasse presque toujours. La chose la plus intéressante a été découverte lorsque j'ai essayé de trier un milliard d'entiers avec son aide - il s'est avéré que le remplissage de type 7 conduit à une dépendance temporelle proche d'une loi quadratique, c'est-à-dire à un possible "traitement" pouvant durer plusieurs années (je n'ai pas attendu la fin et l'ai arrêté à 21 heures de course). Avec moins de données, ce tri peut généralement sélectionner des points d'ancrage avec lesquels il fonctionne rapidement.Avec moins de données, ce tri peut généralement sélectionner des points d'ancrage avec lesquels il fonctionne rapidement.Avec moins de données, ce tri peut généralement sélectionner des points d'ancrage avec lesquels il fonctionne rapidement.

Le tri introspectif est utilisé dans la bibliothèque standard C ++, bien que la méthode exacte utilisée dans std :: sort dépend de l'implémentation, à condition de fournir des informations uniquement sur GCC. Selon les essais, c'est le deuxième plus rapide après le tri par répartition lorsque vous travaillez avec des nombres, et l'avantage du tri par répartition est faible (de près de 0 à 30%), mais avec le tri par chaîne, tout est bien pire - il peut être 3 à 4 fois inférieur à celui des leaders . Il s'agit en fait d'un tri rapide, dans lequel deux cas particuliers sont pris en compte: 1) si le nombre de récursions est devenu trop important, alors le passage au tri par tas se produit; 2) si le nombre d'éléments à trier est petit, le passage au tri par insertions se produit.

Tri stable à partir de la bibliothèque standard C ++ ( std :: stable_sort), comme son nom l'indique, a la propriété de la stabilité - il préserve l'ordre relatif entre les éléments avec la même clé. Cette propriété est relativement rarement nécessaire, même si j'écris sur elle plutôt sans fondement, uniquement sur la base de ma propre expérience. Il peut utiliser de la mémoire supplémentaire, ce qui le rend plus rapide. Étonnamment, ce tri est souvent plus rapide que std :: sort.

Dans le langage super populaire python, le tri de Tim est utilisé en standard . Pour les tests, j'ai utilisé sa version depuis le dépôt github. Il montre de bons résultats records sur des données partiellement ordonnées, mais en moyenne, il est encore nettement plus lent que les leaders. Habituellement, sa vitesse est la moyenne entre le tri rapide et le tri Shell, bien que sur les lignes il soit parfois proche des leaders. Il a la propriété de la stabilité. Il implémente un algorithme relativement compliqué, dans l'implémentation standard dont une erreur a été découverte en 2015, qui nécessite cependant une situation plutôt irréaliste pour sa manifestation.

La bibliothèque BSD C a un tri au niveau du bit ( radixsort) et sa version stable (sradixsort). Malheureusement, ces deux types ne peuvent être utilisés que pour les chaînes C. Comme le montrent les données de test, c'est le moyen le plus rapide de trier les chaînes aujourd'hui, et il est donc surprenant qu'il n'y ait pas d'option standard pour les chaînes C ++.

La bibliothèque BSD C a plus de tri fusion ( le mergesort) Ce tri est connu comme l'un des plus rapides pour les données d'accès séquentiel (fichiers, listes) et est probablement utilisé dans la bibliothèque standard C ++ pour le tri des listes (std :: list et std :: forward_list). Soit dit en passant, elle était connue depuis 1948 et l'un de ses développeurs était un mathématicien très connu et spécialiste des premiers systèmes informatiques von Neumann. Parmi les méthodes rapides, ce tri ne se distingue pas par les meilleures caractéristiques, bien que, en règle générale, il soit quelque peu plus rapide que les méthodes Shell. Il nécessite une mémoire supplémentaire et est généralement implémenté de manière durable.

De plus, il y a toujours un tri par groupe(heapsort). Le tas est généralement utilisé pour une mise en file d'attente optimale avec des priorités, mais peut également être utilisé pour le tri. Les tas de tri ne nécessitent pas de mémoire supplémentaire, mais ils n'ont pas la propriété de stabilité. En vitesse pour les nombres, elle est significativement (jusqu'à 3-6 fois) plus lente que les méthodes Shell, mais pour les lignes de lignes pas très courtes, elle montre de très bons résultats, dépassant (avec l'augmentation de la longueur des lignes, l'avantage augmente).

Le tri en tas est également disponible dans la bibliothèque standard C ++. Un tel tri se fait en deux opérations: construire le tas (std :: make_heap) puis trier réellement ( std :: sort_heap) Ici, contrairement à la bibliothèque bsd, le tri n'est qu'une des opérations du tas. Habituellement, cette option de tri est légèrement plus rapide que la précédente (l'option bsd affiche de meilleurs résultats uniquement sur les numéros courts et les longues lignes s).

En utilisant la bibliothèque C ++ standard, vous pouvez trier l'arbre équilibré binaire (std :: multiset) - il suffit de remplir l'arbre et de faire le tour. Cette méthode peut être considérée comme un tri rapide non récursif. Un problème se pose dans le fait que l'allocateur de mémoire standard est remarquable pour être lent, donc pour les meilleurs résultats, vous devez utiliser votre propre allocateur, qui accélère d'environ 10-30%. On peut également noter qu'une telle méthode nécessite beaucoup de mémoire supplémentaire, avec g ++ pour chaque élément de données, en plus de cela, vous devez également stocker 32 octets (sur l'architecture x86-64) - il serait intéressant d'essayer de stocker un tel arbre sous forme de bouquet, c'est-à-dire sans supplémentaire octet Si vous utilisez boost :: container :: multiset, vous avez besoin de moins de mémoire: seulement 24 octets supplémentaires par élément de données. Cependant, comme boost,et la bibliothèque standard a montré une surprise désagréable - dans le processus, ils ont parfois nécessité plus de mémoire que nécessaire. Cela est peut-être dû à l'équilibrage des arbres binaires. Codes -ici .

La bibliothèque boost contient spreadsort , un algorithme inventé au 21e siècle. Il s'agit de la méthode globale la plus rapide disponible aujourd'hui dans des bibliothèques bien connues. Ce tri utilise des idées au niveau du bit et, comme lui, peut être assez morose quant au type d'arguments. Habituellement, ce tri montre des résultats records, parfois bien meilleurs que ceux des concurrents les plus proches. La seule exception est le tri des lignes C, où il est nettement inférieur aux méthodes au niveau du bit de la bibliothèque bsd. Lors du tri de longues lignes C, il peut être inférieur à d'autres méthodes, par exemple le tri par rotation ou le tri rapide avec deux points d'ancrage. Le tri des spreads (boost v1.62) a montré un problème très désagréable- lors du tri de petits tableaux de chaîne C (jusqu'à 1 000 éléments), cela fonctionne avec des erreurs.

Il existe également un nouvel algorithme pdqsort qui améliore, comme l'a déclaré l'auteur, le tri introspectif. Ce nouvel algorithme, qui n'est pas encore décrit sur Wikipédia. Ses résultats - bien que pas mauvais, mais pas particulièrement impressionnants. Il est plus lent que std :: sort sur les entiers courts, mais plus rapide sur les chaînes et les entiers longs. Dans les deux cas, la différence est plutôt insignifiante. Les meilleurs résultats pour ce tri ont été obtenus pour les longues chaînes C ++ - ici, il est inférieur, bien que sensiblement, uniquement au leader, le tri par répartition.

Dans boost, vous pouvez toujours trouver spinsort. Il s'agit également d'un nouvel algorithme, qui, contrairement au précédent, a la propriété de stabilité et qui n'est pas encore décrit sur Wikipédia. Habituellement, il est proche du leader, mais avec un retard notable derrière lui. Il nécessite, mais pas trop, de la mémoire supplémentaire. Terminons

avec flat_stable_sort de la même bibliothèque de boost. Il s'agit d'un autre nouvel algorithme robuste qui n'est pas encore décrit sur Wikipedia. C'est de loin la méthode la plus rapide, mais légèrement inférieure à la plupart des autres méthodes de bibliothèque rapide. Il utilise très peu de mémoire supplémentaire (cependant, il a toujours besoin d'une table de taille fixe de 8 Ko) et est souvent nettement plus rapide que la méthode Shell.

Considérez le tableautemps (en ms) de fonctionnement de ces algorithmes sur un ordinateur avec 8 Go de RAM avec un processeur AMD Phenom ™ II X4 955 @ 3.214 MHz. L'ordinateur a fonctionné pendant plusieurs mois au total et la taille totale des données collectées dans deux fichiers json chargés avec des tables est de près de 400 Ko. Les timings sont donnés par la moyenne du nombre de runs; pour des tailles plus petites, ces runs étaient plus grands. Travailler avec le cache d'une manière assez compliquée change la vitesse des calculs, donc les résultats obtenus ne sont au mieux qu'approximatifs (je peux supposer que les imprécisions de synchronisation peuvent atteindre jusqu'à 20%). Je crois que sur les meilleurs processeurs modernes pour PC, le résultat peut être obtenu 2 à 3 fois plus rapidement, mais gardez à l'esprit que de nombreux processeurs plus modernes fonctionnent en basculant entre différentes fréquences et le résultat obtenu avec eux,sera encore plus approximatif.

Ceci et le tableau suivant sont interactifs. En plus des valeurs absolues des timings, vous pouvez également voir leurs valeurs par rapport à la moyenne, la médiane, le minimum et le maximum. Vous pouvez modifier la précision des caractères. Vous pouvez également obtenir des relations temporelles pour différents types de remplissages et types de données. Ce dernier, par exemple, peut montrer que le tri des chaînes C est sensiblement plus rapide que les chaînes C ++. À partir des méthodes de tri, vous pouvez également sélectionner et assembler une variété de sous-ensembles. Vous pouvez bien sûr définir le tri par n'importe quelle colonne. Malheureusement, je ne sais pas comment utiliser Javascript dans l'article sur le hub, donc les tableaux ne sont disponibles que par référence. Dans le cas où imtqy.com est surchargé, je donne également des liens de sauvegarde vers les première et deuxième tables.

Le temps est mesuré en millisecondes, mais dans la loi de la dépendance temporelle, afin d'éviter des coefficients trop petits, des formules pour les microsecondes sont données. Ainsi, si nous substituons la valeur de N dans la formule , le résultat doit également être divisé par 1000 pour obtenir un nombre proche de celui correspondant dans le tableau. La loi de la dépendance temporelle est dérivée sur la base des timings obtenus, à partir d'une comparaison de deux résultats (généralement les extrêmes sont pris). Vous pouvez vérifier la qualité de la loi dérivée en utilisant l'option d'écart relatif de la valeur réelle par rapport à la sortie.

Quelques conclusions générales des résultats de ce tableau:

• les meilleurs triages shell sur les données jusqu'à 10 millions d'éléments peuvent dépasser le tri temporel et même certains triages rapides;
• timsort est très proche de la vitesse qsort (clib), dépassant parfois quelque peu, et parfois vice-versa derrière;
• le tri sélectif et en particulier le tri des arbres ralentissent souvent sensiblement, mais dans le contexte d'une bulle ou même d'un choix, il est clair que ce sont encore des méthodes rapides. Fait intéressant, ces deux méthodes ont souvent des caractéristiques très similaires - elles construisent toutes deux des arbres. Il est facile de remarquer que les dépendances pour heapsort et treesort, bien que n'étant pas clairement quadratiques, ne sont évidemment pas N log N , mais bien pire - comparez avec le tri Shell, qui se comporte beaucoup mieux avec l'augmentation du volume de données que heapsort ou treesort, tandis que qu'elle est elle-même plus lente que N log N. Ainsi, les implémentations pratiques du tri des tas et des arbres ne correspondent pas à leurs spécifications théoriques;
• les données sur le tri des chaînes montrent que les lois des dépendances temporelles ici ne sont pas les mêmes que pour les nombres - les longueurs des chaînes qui sont triées sont en quelque sorte superposées à ces lois ici. Malheureusement, je ne connais pas les formules de tri connues qui donneraient des lois exactes de dépendances temporelles lors du travail avec des chaînes;
• il est intéressant de noter que la vitesse de travail avec des nombres réels est à peu près la même que celle des nombres entiers - ceci est une conséquence du fait que dans l'architecture x86 moderne, des optimisations très efficaces pour travailler avec la pile sont faites;
• hash_sort a montré des résultats assez médiocres, cela est possible du fait qu'en raison de l'utilisation de mémoire supplémentaire, les performances des caches de processeur diminuent fortement. Sur de petites données aléatoires (moins de cent mille éléments), le tri par hachage dépasse les meilleurs tris rapides. Vous pouvez également remarquer que cela est possible à nouveau en raison des caches, certains résultats de ce tri sont très étranges, par exemple, 10 ⁵ , 10 ⁶ et 10 ⁷ entiers 32 bits lors de l'utilisation du remplissage partiellement ordonné sont triés pour approximativement les mêmes le temps! Une sorte d'effets presque quantiques. :) Je suis sûr que si vous recherchez, vous pouvez trouver d'autres résultats difficiles à expliquer.

J'ajouterai quelques conclusions supplémentaires sur certains cas particuliers:

• certains types de remplissage des données révèlent des faiblesses dans les triages rapides. Cependant, le choix d'un élément de support de manière compliquée rend la probabilité de tomber dans une mauvaise séquence de tri pratiquement nulle. Vous pouvez également sélectionner un élément de support à chaque passage de différentes manières ou au hasard. Peut-être le font-ils dans qsort (clib). La méthode de Hoare considérée ne fonctionne très lentement que sur des séquences spécialement conçues, rencontrées par hasard lors de travaux pratiques - c'est un cas avec une probabilité de 2 ^{N -3} / N ^N , c'est-à-dire un événement presque absolument impossible. Bien que si nous considérons les séquences sur lesquelles la méthode Hoar ne fonctionne pas aussi lentement que possible, mais uniquement avec un ralentissement significatif, il y a beaucoup plus de tels cas, ce qui laisse cependant la probabilité qu'un cas de traitement des données trop lent soit toujours pratiquement insignifiant, bien que très ennuyeux dans son zéro. Il est également presque impossible d'obtenir accidentellement des données sur lesquelles un tri rapide avec deux points de contrôle fonctionnera lentement, selon la loi quadratique. Les options de tri rapide de Lomuto sans et sans élément de support affichent de très mauvais résultats sur presque tous les cas de remplissage particuliers;
• dans certains cas particuliers, le tri le plus lent des «bulles» donne d'excellents résultats et certains des triages les plus rapides et les plus rapides, au contraire, sont très mauvais;
• Le tri par hachage a montré un très mauvais résultat sur les remplissages de types 8 et 9, car la séquence monotone est tirée de valeurs consécutives, en commençant par la plus petite, et 1% de nombres aléatoires est pris de la plage de la valeur la plus basse à la valeur maximale, ce qui alésage tous 99% consécutifs des données en un seul élément de hachage. Ce cas illustre très bien les problèmes qui peuvent survenir lors de l'utilisation de ce tri ou du tri avec un tableau avec des données inconnues;
• le tri par sélection se comporte de manière très stable sur tous les types de remplissage, les tri par tas et par arbre sont également assez stables, sans pics ni creux évidents. Cela est vrai, bien sûr, pour les tris Shell, ainsi que pour la plupart des autres méthodes rapides des bibliothèques standard.

Il est maintenant temps de parler des types de données utilisés avec les algorithmes de tri:

1. entiers signés 32 bits (int32_t), mais seuls des caractères non négatifs ont été utilisés. D'autres données numériques ont également été prises uniquement à titre non négatif - cela ne réduit pas la généralité des résultats, mais facilite leur obtention pour certains algorithmes;
2. entiers, signés 64 bits (int64_t);
3. entiers, signés sur 128 bits (__int128 - pris en charge par au moins GCC);
4. structures de cinq entiers (int32_t), dont l'un est utilisé comme clé (INT1P4). Lors du tri de ces données, le nombre de permutations commence à affecter le temps de calcul de manière plus significative; par conséquent, les méthodes avec moins de permutations gagnent un certain avantage;
5. nombres réels tels que double précision, double (nombres flottants);
6. des chaînes courtes C ++ et C. Des chaînes de 1 à 16 ont été prises (chaînes courtes et chaînes c courtes);
7. les chaînes C et C ++ de longueur moyenne, dont la longueur est de 1 à 256 (chaînes et chaînes c);
8. de longues lignes C et C ++, dont la longueur est de 1 à 2 ²⁰ (c'est un peu plus d'un million), et les lignes sont sélectionnées de sorte que leur longueur moyenne ne dépasse pas 512, de sorte que les lignes ont été sélectionnées uniquement pour un remplissage aléatoire, pour les autres cas, les lignes ont simplement été prises longueurs de 1 à 512 (cordes longues et cordes c longues).

Et aussi sur la façon de remplir le tableau source pour le tri:

1. par hasard;
2. strictement ascendant (ordonné);
3. strictement décroissant (ordre inverse, inversé);
4. valeurs aléatoires comprises entre 0 et 99 (petite variation, faible variation 100);
5. séquence aléatoire de 0 et 1 (petite variation, faible variation 2);
6. constante 0 (petite dispersion, faible variation 1);
7. la séquence menant la version qsort (Hoare) à l'exécution la plus lente. Il est curieux qu'il existe exactement 2 ^{N -3 de} telles séquences parmi toutes les séquences de longueur N ;
8. strictement ascendant, avec insertion de 1% de nombres aléatoires (partiellement ordonnés);
9. strictement décroissant, avec une insertion de 1% de variables aléatoires (partiellement inversées).

Il convient de souligner que les données aléatoires sont le cas le plus typique de remplissage d'un tableau, toutes les autres méthodes sont extrêmement rares et même presque impossibles pendant le fonctionnement normal d'un particulier.

Regardons les résultats du test, où les triages fonctionnent avec toutes les séquences de données possibles. Le nombre de ces séquences est égal à la factorielle de leur longueur, ainsi, pour les séquences de longueur 12, il existe 479'001'600 variantes - un bon PC moderne calculera leur nombre en moins d'une minute. Si nous prenons des séquences de longueur 14, nous obtenons déjà 87'178'291'200 variantes pour plusieurs heures de fonctionnement informatique. Par conséquent, le tableau suivant montre le temps moyen (en cycles de processeur obtenus via l'instruction RDTSC ) d'un tri lors du tri de toutes les permutations jusqu'à seulement 12. Dans les données, les types numériques précédents et les chaînes courtes sont pris. Bien sûr, on pourrait remarquer que les séquences avec des éléments répétitifs ne sont pas prises en compte. Cependant, j'ose suggérer que leur présence ne changerait pas qualitativement les résultats, mais pourrait ralentir considérablement leur réception.

Les résultats pour de si petites données ne sont pas très représentatifs, et surtout pour les méthodes de tri complexes, mais ils complètent encore l'idée du comportement de tri. Certaines sortes, pour autant que je sache, remplacent leur algorithme principal par un autre lorsque vous travaillez avec de petits tableaux - ce sont des sortes étalées, rapides avec deux points d'ancrage et radix_msd (les deux derniers utilisent des insertions). Et certains triages (flat_stable et radix) utilisent de petites tables, mais avec de petites tailles de données, ces tables s'avèrent être beaucoup plus grandes que les données elles-mêmes, ce qui ralentit considérablement ces méthodes par rapport aux autres et produit des résultats étranges. Des résultats étranges sont également obtenus avec d'autres triages au niveau du bit et avec des triages de hachage et de tableau. Ces résultats inhabituels s'expliquent facilement par le fait que le temps de préparation des données avant le tri pour ces méthodes pour les petites données est plus long que le temps de tri lui-même. Bien sûr, lors de la mesure de ces petits intervalles de temps (nanosecondes), l'influence de diverses erreurs sur la loi affichée est beaucoup plus élevée que dans le tableau précédent. Par conséquent, les lois se sont avérées très approximatives, souvent «avec une dérive» vers des valeurs exagérées. Ce dernier s'explique en partie par le fait que lorsque l'on travaille avec de petites données, le temps de tri lui-même devient comparable au temps d'appel de la fonction de tri et à plusieurs opérations auxiliaires nécessaires pour mesurer le temps. Le programme essaie de soustraire la surcharge nommée de la sortie, mais cela se fait plutôt approximativement. Avec tout cela, j'ose supposer qu'en comparant les résultats pour différents types de données et en tenant compte des commentaires émis, vous pouvez parfois faire des hypothèses qui ne sont pas très loin d'être exactes.

En conclusion, un autre tableau qui montre combien de méthodes de test différentes sont nécessaires pour trier la mémoire supplémentaire. Évidemment, cette valeur dépend du système. Dans mes tests, comme je l'ai déjà écrit, c'est x86-64, GCC. La lettre T signifie la taille du type en octets (la longueur de la chaîne n'est pas incluse dans cette taille: pour les lignes C c'est la taille du pointeur, pour les lignes C ++ c'est la taille du descripteur, 32 octets pour x86-64 GCC), la lettre L est le milieu la longueur du type en octets (pour les nombres c'est T et pour les chaînes c'est la longueur moyenne de la chaîne), la lettre A peut être 1 ou 0 - c'est l'alignement sur la bordure 64 bits, et la lettre M est l'alignement de l'allocateur de mémoire standard (c'est supposé s'aligne sur une limite de 32 octets). Le symbole ^* signifie que les données pour ce type de tri ont été obtenues uniquement sur la base de l'analyse de la lecture du champ VmRSS à partir de / proc / PID / status (le champ mentionné est la taille du programme de traitement).


Il existe bien sûr d'autres méthodes de tri, à la fois primitives et rapides. La bibliothèque boost possède des algorithmes parallèles qui vous permettent de profiter de la présence de cœurs de processeur supplémentaires dans le système. Vous pouvez également utiliser le conteneur auto-ordonné boost :: container :: flat_multiset au lieu de std :: multiset, mais cela fonctionne très lentement.

J'en profite pour dire quelques commentaires sur la bibliothèque boost en général. Je recommande de ne pas passer. Même les fonctionnalités qui sont dans la bibliothèque standard de boost, en règle générale, sont mieux implémentées et parfois (comme les expressions régulières, par exemple) sont bien meilleures. Si nous parlons de conteneurs, alors en boost ils sont sensiblement plus grands, et ceux qui coïncident avec les standards sont parfois un peu plus rapides et ont souvent de petites mais belles améliorations. Boost vérifie les types de manière plus approfondie, ce qui peut parfois aider à détecter des erreurs presque insaisissables qui ne se manifestent généralement pas, mais peuvent dans certains cas être activées de manière inattendue. Les inconvénients de boost incluent inconditionnellement complètement illisibles et des messages volumineux sur les erreurs de compilation sur de nombreuses constructions de cette bibliothèque - cela, bien que dans une moindre mesure, s'applique à la bibliothèque standard. Il est temps que les développeurs C ++ fassent quelque chose à ce sujet.

Tous les fichiers contenant des tests et d'autres documents connexes peuvent être extraits de mon référentiel . Si quelqu'un s'intéresse aux données source brutes, vous pouvez les obtenir ici (1,4 Mo). Je serai heureux de tout commentaire, critique et ajout.