J'ai étudié TimSort ~ Méthode de tri sophistiquée qui est implémentée en standard en Java et Python ~ (Partie 1)

Comment avez-vous commencé à étudier Tim Sort?

Au départ, je pensais trier une paire de deux éléments ($ m (m-1) / 2 $ paires) dans un ensemble de $ m $ éléments, et c'était déjà $ O (m ^ 2). Comme il y avait des paires $, j'ai pensé que cela prendrait du temps si je ne concevais pas de tri, alors j'ai implémenté et trié le tas par moi-même. (Le tri de tas est exécuté au pire $ O (n \ log n) \ sim O (m ^ 2 \ log m ^ 2) $. En revanche, le tri par bulle naïf et le tri par insertion sont $ O (n ^ 2) \ sim O ( Cela coûte m ^ 4) $. Ici, le nombre de paires est décrit comme $ n \ sim m ^ 2 $)

Cependant, en regardant en arrière, Java et Python évoluent de jour en jour, j'ai donc pensé que l'algorithme de tri utilisé dans l'implémentation standard devrait également évoluer, alors je l'ai étudié. Je ne voyais pas grand besoin de le garder comme une méthode simple comme le tri à bulles.

Comme prévu, il n'était consacré que tous les jours et implémentait un algorithme de tri très sophistiqué. Je m'appelle Tim Sort.

Langage de programme qui implémente TimSort

• Python (implémenté en tant que tri standard dans 2.3 et versions ultérieures)
• Java (implémentation standard pour les tableaux de type référence depuis SE7)
• Swift

TimSort aurait été implémenté pour la première fois en 2002 par Tim Peter en Python. Tim Peter est également connu comme l'auteur de "The Zen of Python", une collection bien connue de proverbes Python.

(Référence: Wikipedia https://en.wikipedia.org/wiki/Timsort)

De plus, Tim Sort est également utilisé dans la plate-forme Android, GNU Octave, V8, etc.

Présentation de Tim Sort

La vidéo expliquant Tim Sort par Gaurav Sen était très facile à comprendre. Référence: https://www.youtube.com/watch?v=emeME__917E Veuillez noter que l'anglais indien a une forte habitude. (Au contraire, l'anglais japonais semble être assez addictif pour les Indiens et ne peut être entendu.) Je voudrais résumer ici ce que j'ai étudié principalement en référence à cette vidéo.

Le pire moment de calcul de Tim Sort

• O(n\log n)

est. Ce n'est pas très différent du tri de tas et du tri par fusion ($ O (n \ log n)) $, mais c'est un peu mieux que ceux-ci.

En un mot, les caractéristiques de Tim Sort

Pour le dire grossièrement pour que vous puissiez facilement obtenir une image,

• ** Un bon algorithme qui passe naturellement à la meilleure méthode de tri possible dans certains cas **

Je pense que cela peut être dit.

Comme je l'ai dit plus tôt, il n'y a pas d'amélioration significative du temps de calcul dans le pire des cas, comme la comparaison entre le tri à bulles $ (O (n ^ 2)) $ et le tri en tas $ (O (n \ log n)) $. Cependant, on peut dire qu'il a été conçu pour être le meilleur dans tous les cas en combinant des algorithmes de tri améliorés. (Je ne pense pas que ce soit toujours le meilleur)

Dans certains cas, le choix de la meilleure méthode de tri devrait être le bienvenu dans ** lorsque divers cas d'utilisation tels que les langages de programmation sont attendus **. Si vous souhaitez couvrir une variété de cas d'utilisation, la quantité de données peut être grande ou petite. Je pense que le but est de fournir une méthode de tri plus rapide, même lorsqu'elle est petite.

Présentation de la procédure Tim Sort

Pour le dire très grossièrement

1. Regroupez les colonnes à trier en un ensemble de petites colonnes triées (exécutions). ● Utilisez le tri par insertion, qui est plus efficace que le tri par fusion pour les petites tailles, lors du regroupement en colonnes

2. Exécuter la fusion en utilisant le tri par fusion, mais dans ce cas ● Adoption de l'ordre de fusion des exécutions qui peut supprimer le nombre de fusions (pile en utilisant l'inégalité de relation proche du nombre de Fibonacci) ● Procédure de fusion efficace (dichotomie sans plage, mode galop, fusion de zones de mémoire adjacentes, etc.) Nous procéderons efficacement en utilisant.

Je pense que ce sera. Ci-dessous, je vais regarder les détails de la procédure.

1. Divisez la colonne à trier en un ensemble de petites colonnes déjà triées, "run".

1-1. Petite colonne triée "run" (nombre d'éléments de 32 à 64)

Premièrement, lorsque nous recevons une colonne d'éléments à trier, nous visons à la trier dans un ensemble de petites colonnes triées «run».

Ici, pourquoi la taille 32 à 64? ** En effet, le tri par insertion est la taille maximale qui en fait l'algorithme de tri le plus rapide. ** **

1-2. Comparaison du tri des insertions et d'autres algorithmes

Le tableau ci-dessous résume ce qui peut être considéré comme la méthode de tri de base.

À première vue, il semble que la méthode $ O (n \ log n) $ à droite devrait être utilisée de manière unifiée, mais pourquoi utiliser le tri par insertion à gauche? (Je suis désolé pour ceux qui le comprennent.)

Il convient de garder à l'esprit que cette estimation du temps de calcul est valide lorsque ** $ n $ est suffisamment grand **. Lorsque les données sont volumineuses, le nombre de fois que le traitement typique de l'algorithme est répété est efficace, mais lorsque le nombre de données est petit, la complexité du traitement par l'algorithme est plus que le facteur dépendant du nombre de données. Ça va marcher. Cela est dû à la complexité du traitement spécifique à l'algorithme, qui ne dépend pas du nombre de données, et est un terme de $ O (1) $. En général, l'algorithme $ O (n ^ 2) $ a été développé plus tôt, et la procédure de traitement unique elle-même est simple, donc ces facteurs $ O (1) $ sont plus petits.

Qu'est-ce que cela veut dire? Le nombre de cette estimation est plus fin. $ O (1) $ coefficient coefficient $ c_ {i, b, s, m, q, h}, \ tilde {c} _ {i, b, s, m, q, h Pensons-y en incluant} $.

• $ O (n ^ 2) $ méthode --Tri par insertion: $ c_i n ^ 2 + \ tilde {c} _i n $

• Tri des bulles: $ c_b n ^ 2 + \ tilde {c} _b n $ --Tri sélectif: $ c_s n ^ 2 + \ tilde {c} _s n $

• $ O (n \ log n) $ méthode

• Tri par fusion: $ c_m n \ log n + \ tilde {c} _m n $ --Triage rapide: $ c_q n \ log n + \ tilde {c} _q n $ --Tri en tas: $ c_h n \ log n + \ tilde {c} _h n $

À partir de là, factorisez $ n $, qui est un facteur commun en lecture, pour simplifier la compétition pour le temps requis pour l'algorithme $ O (n \ log n) $ et l'algorithme $ O (n ^ 2) $. J'aimerais sortir et comparer. Dans ce cas, où $ n $ est petit, le comportement du pire moment $ f (n) $ que chacun prend est à peu près comme indiqué dans le graphique ci-dessous.

Lorsque la taille des données est petite, le facteur $ O (1) $ introduit plus tôt, qui n'a rien à voir avec la taille des données, est efficace dans le temps. Fondamentalement, le coefficient facteur $ \ tilde {c}, c_ {i, b, s} $ de l'algorithme $ O (n ^ 2) $ est meilleur que le $ c_ {de l'algorithme $ O (n \ log n) $. Il est plus petit que m, q, h} $, $ \ tilde {c} _ {m, q, h} $ car il est plus simple à traiter. Finalement, à mesure que les données deviennent plus grandes, le coefficient différentiel de $ \ log n $ devient plus petit et l'ordre est inversé, mais lorsque la taille des données est plus petite, le gradient de la fonction $ \ log n $ devient $ 1 / n. Je crois comprendre que l'algorithme $ O (n ^ 2) $ a un intervalle raisonnable avant qu'il ne s'agrandisse parce que $ n'est pas assez petit.

De cette manière, le coefficient $ O (1) $, qui est déterminé par la complexité de la procédure, est efficace dans la zone où les données sont petites. Ensuite, lorsque les données sont petites, vous devez adopter un algorithme qui effectue un traitement simple de sorte qu'un tel coefficient soit le plus petit. La réponse est ** insérer le tri **. (En tant que vue sans coefficient, les tris par insertion sont plus rapides que les tris par bulles et les tris sélectionnés dans certains cas, car ils peuvent réduire le nombre de comparaisons (ignorer). Actuellement, il s'agit de tris complets d'une colonne donnée, donc la pièce Le tri n'est pas pris en compte.)

Par conséquent, afin de créer la première exécution de sous-colonne triée, le tri par insertion est utilisé tant que le nombre de données est garanti pour être le plus rapide. On dit que le nombre d'éléments est d'environ 32 à 64. ** Par conséquent, le nombre d'éléments en cours d'exécution est défini sur 32 ~ 64.

1-3. Amélioration du tri des insertions

TimSort utilise le tri par insertion lorsque les données sont petites, comme je l'ai expliqué plus tôt, mais parce que je veux faire un tri par insertion encore plus rapide, j'utilise le ** tri par insertion à moitié **. Le tri par insertion par bisection est un algorithme amélioré de tri par insertion qui effectue une dichotomie pour trouver la position d'insertion.

1-4. Localité de l'élément qui génère l'exécution

Ici, lors de la formation d'une course, la course est gonflée en insérant et en triant uniquement les éléments qui existent à proximité dans la colonne d'origine donnée. Par conséquent, le tri par insertion ne recherche pas tous les éléments dans une colonne de taille $ n $ pour trouver les éléments à insérer dans l'analyse. Par conséquent, si le nombre d'éléments dans la colonne à trier est grand, $ n $, l'ordre de temps requis pour cette opération se terminera à environ $ O (n) $, qui est le nombre d'exécutions. Cet ordre est un petit terme par rapport au temps requis pour le tri par fusion qui apparaîtra plus tard, et il ne fonctionne pas pour la pire estimation de temps.

2. Fusionnez en utilisant le tri par fusion.

2-1 Comment combiner efficacement les sous-chaînes de tri?

Le débat est de savoir comment réduire le nombre de jointures pour former une colonne de la taille d'origine. Il permet, de manière surprenante, de profiter de la même régularité que la croissance des organismes vivants dans la nature. Il s'agit d'une séquence appelée ** séquence de Fibonacci **. Cette séquence de nombres est un modèle dans lequel les organismes, en particulier les plantes, se développent plus efficacement, et le fait qu'ils se développent régulièrement signifie que si cela est adopté, de grands agrégats peuvent être formés efficacement et en peu de temps.

La séquence de Fibonacci est décrite par l'équation graduelle suivante:

\begin{equation}
a_{m+2} = a_{m+1} + a_{m}
\end{equation}

Dans cette formule de graduation, le comportement lorsque $ m \ gg 1 $ lorsque le premier terme numérique est $ a_0 = 0, , a_1 = 1 $

\begin{equation}
a_{m} \sim \frac{\phi^m}{\sqrt{5}}, \hspace{2cm} \phi = \frac{\sqrt{5} + 1}{2} \sim 1.6 > 1
\end{equation}

Ce sera. À partir de là, nous pouvons voir qu'il peut croître par pas de $ m \ sim \ log n $ jusqu'à ce qu'il atteigne la taille cible $ n $.

En d'autres termes, l'intérêt de TimSort est que si vous effectuez un traitement de jointure d'exécution avec une structure proche de la séquence de Fibonacci, vous pourrez faire une liste finale avec le nombre de fusions de $ \ log n $.

Bien sûr, si vous faites une séquence de Fibonacci stricte, il faudra du temps et des efforts pour en faire une structure, et c'est du gaspillage. Je ne veux pas d'une séquence exacte de Fibonacci. Il s'agit donc de réaliser un processus de fusion raisonnablement proche d'une structure proche de la séquence de Fibonacci. Même si vous êtes loin de Fibonacci au début, vous pouvez vous rapprocher de ce nombre au fil du processus. L'estimation de la commande est une estimation approximative de $ n \ gg 1 $ (ce devrait être Fibonacci lorsque $ n $ grandit).

C'est "l'utilisation de la pile utilisant l'inégalité proche de la séquence de Fibonacci" expliquée ensuite.

2-2. Utilisation de pile avec inégalité proche de la séquence de Fibonacci

Fusionnez le run en le mettant sur la pile. (J'ajouterai le diagramme de pile plus tard si j'ai une certaine capacité de réserve, mais si vous pouvez vous y référer sur wikipedia pendant un moment et obtenir une image)

Référence (pile): https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF

La pile a essentiellement une structure comme un seau avec la même entrée et la même sortie, dans laquelle les nouvelles données sont placées par le haut et empilées par le haut. En bas se trouve la structure où sont placés les anciens membres. Lors de la récupération des données de la pile, elles sont extraites des données supérieures.

Ici, je le mets dans la pile et fusionne les colonnes dans la pile, mais quand j'ai fini de mettre toutes les données et que j'entre dans la procédure de la dernière étape de la fusion, le run qui est dans la pile Nous visons à conserver les relations de taille afin qu'elles satisfassent les relations de type miroir mochi suivantes. Ici, l'indice $ 0 $ indique l'élément supérieur en haut de la pile, et plus le nombre est élevé, plus les données sont basses. Ici, laissez le symbole représentant run être $ r_ {i} (i = 0, 1, \ cdots) $.

\begin{align}
r_{n+2} &> r_{n+1} + r_{n} \\
r_{n+1} &> r_{n}
\end{align}

Si vous regardez la toute première formule, cette relation n'est pas une séquence de Fibonacci, mais elle semble plus ou moins similaire et est une version détendue de la séquence de Fibonacci. Si ces deux inégalités sont satisfaites, le tableau de données sera dans la pile près de la colonne Fibonacci, et la procédure de fusion finale sera $ \ log n $.

La question qui reste est de savoir ce qu'il faut faire pour atteindre un tel état d'inégalité. C'est équivalent à faire ce qui suit dans le surnageant du vaisseau de la pile chaque fois que vous mettez des données dans la pile: (Java-ish, un faux algorithme est écrit ici) Nommez le tableau exécuté en tant qu'élément de la pile en tant qu'exécutions. Imaginez que l'index du tableau soit attaché par ordre croissant à partir du haut.

if(runs.length >= 2){
  if(runs[2].length > runs[1].length + runs[0].length){
    if(runs[1].length > runs[0].length){
       break;
    }
    else{
      merge(runs[0], runs[1]);
    }
 }
 else{
   merge(runs[1], min(runs[0], runs[2]));　//min est exécute[0]Et court[2]C'est la seule fausse notation qui représente la plus courte des
 }

}

Dans l'algorithme ci-dessus, l'opération de fusion est effectuée de sorte que la partie surnageante se rapproche de l'inégalité lorsque de nouvelles données sont placées dans la pile. Continuer à manipuler les données surnageantes comme celle-ci conduira finalement à la formation d'une colonne de courses de type Fibonacci.

Pour cela, une structure appelée pile, dans laquelle les données sont versées par le haut, est efficace. L'image ici est de verser petit à petit la pâte grumeleuse non fondue d'okonomiyaki sur la plaque de fer, et d'utiliser une spatule ou quelque chose de ce genre pour que la pâte inférieure occupe une plus grande surface que la pâte supérieure. Je pense que c'est similaire à faire. Dès le début du versement des données dans la pile, si vous continuez à verser en appuyant avec une "spatule" pour que le fond soit plus long pour que le surnageant seul soit stable, l'ancienne chaîne de données sans couler sera Puisqu'il est maintenu enfoncé par l'opération de fusion pendant une longue période, il devient une ligne meilleure et plus longue, et une ligne numérique de Fibonacci stable de lignes de tirage peut être formée naturellement. En d'autres termes, ** les anciennes données ont la propriété d'une pile qui stagne en bas, et l'exécution avec un grand nombre d'éléments qui a été exposée pendant longtemps à l'opération de fusion s'enfonce naturellement sous la pile. ** C'est la clé.

En construisant le jeu de données de l'exécution dans l'état fibonacci afin de ne pas en faire trop de cette manière, le nombre d'opérations de fusion peut être supprimé à $ \ log n $.

2-3. Méthode de tri par fusion et pire moment par tri par fusion

Après cela, le pire moment de calcul pour un tri de fusion devient important. En fait, grâce à cette exécution déjà triée, le temps d'exécution d'un tri par fusion par ** peut être maintenu à $ O (n) $. ** **

Dans le tri par fusion, la zone de mémoire qui stocke le tableau fusionné est d'abord conservée (la zone de mémoire continue utilisée à l'origine par les deux analyses) et la zone de mémoire est contenue dans les éléments combinés des deux analyses. Je vais les mettre en ordre à partir du plus petit. Tout d'abord, nommez les deux exécutions comme côté A à comparer et côté B à comparer. Premièrement, le côté de comparaison A prend un par un comme «éléments de A à comparer» dans l'ordre du plus petit. (** l'exécution est déjà triée, donc le temps qu'il faut pour ce ramassage est O (1) .) Cet élément est comparé dans l'ordre à partir du plus petit élément de B. ( Encore une fois, la récupération du plus petit élément ne prend pas beaucoup de temps car il est trié. ) Ici, la mémoire qui stocke le tableau avec le plus petit Je vais le mettre dans la région. Si l'élément de B est petit, "l'élément de A à comparer" est laissé tel quel, et le plus petit élément de B est inséré. Ensuite, le plus petit élément suivant de B est comparé à l'élément de A, et le plus petit élément de A ou B est stocké dans la zone de mémoire qui stocke également le tableau fusionné. Si "l'élément de A à comparer" est petit, stockez-le dans la zone mémoire et amenez le plus petit élément suivant de A. Ensuite, démarrez la comparaison à partir du plus petit élément de B qui n'est pas en mémoire. ( Les détails ici seront très longs, je vais donc vous expliquer à nouveau en utilisant des chiffres et des exemples concrets dans la suite. **) Le point ici est ** parce qu'il a déjà été trié. Le temps nécessaire est à peu près le nombre de comparaisons, qui est égal au nombre d'éléments dans la zone triée par fusion (car ils sont inclus en même temps que la comparaison). En d'autres termes, le temps qu'il faut au pire est O (n) **.

D'après ces calculs, le pire temps de calcul de TimSort est d'environ $ O (n \ log n) $ en multipliant le temps de calcul $ O (n) $ par temps par le nombre de jointures $ O (\ log n) $. Je pense que ce sera.

2-3-1 Ne devrions-nous pas utiliser la dichotomie?

L'explication ci-dessus est expliquée par la recherche linéaire, et je pense qu'il y a une ruée vers le fait qu'elle n'est peut-être pas très efficace. Cependant, ** ceci est au cas par cas et, dans certains cas, une dichotomie peut prendre plus de temps. ** Par exemple, si deux pistes sont de taille similaire et qu'un élément et l'autre élément sont proches l'un de l'autre. Dans un tel cas, si vous effectuez une dichotomie, vous comparerez également avec des adversaires de tailles complètement différentes afin de ne pas avoir à considérer du tout la relation de grandeur, et $ \ log n $ pour un élément. Nous effectuerons le nombre de fois. Si vous faites cela pour tous les éléments, cela vous coûtera $ O (n \ log n) $ dans le pire des cas. Par conséquent, il vaut mieux ne pas effectuer ** de dichotomie facile. ** Si vous faites cela, la recherche linéaire est plus efficace lors de la fusion d'exécutions déjà triées.

Cependant, au contraire, si la taille des deux passages est biaisée ou si la distribution de la taille des éléments est biaisée, il y a évidemment des recherches inutiles même si la recherche linéaire est effectuée. Naturellement, je pense qu'il vaut mieux sauter. Par exemple, s'il y a de nombreux éléments dans l'exécution B qui sont plus petits que la valeur minimale a de l'exécution A, il est inutile de comparer les amplitudes de la valeur minimale a de l'exécution A et les éléments de l'exécution B dans l'ordre à partir de la valeur minimale. Par conséquent, une méthode pour effectuer une sorte de saut est nécessaire.

** La dichotomie non organisée ** le fait efficacement. Cela permet de combler le cas où la recherche linéaire est plus efficace et la recherche dichotomique est plus efficace car les éléments sont moins biaisés.

2-3-2. Aucune recherche de bissection de plage

En anglais, on l'appelle recherche exponentielle ou recherche galopante, mais c'est comme suit.

Ici, les deux exécutions à fusionner sont A et B, et le plus petit élément non fusionné de A est $ A [0] $. Nous comparerons cela avec l'élément $ B [i] , (i = 0, 1,2,3,4, \ cdots) $ de l'exécution B.

1. Augmentez $ B [0], B [1], B [3], B [7], B [15], \ cdots B [2 ^ {n} --1] $ et l'intervalle de 2 exposants Découvrez où $ A [0] $ se situe dans la plage $ (B [2 ^ {n}] \ sim B [2 ^ {n + 1} -1]) $.

2. Trouvez où va $ A [0] $ en dichotomisant avec $ (B [2 ^ {n}] \ sim B [2 ^ {n + 1} -1]) $ dans cette plage Faire

Cela devient la procédure.

Voici quelques-uns des avantages de cette approche: Dans la combinaison de deux exécutions avec moins de biais qui rend fondamentalement la recherche linéaire plus efficace, premièrement, dans la recherche ci-dessus, elle se situe approximativement entre $ B [0] \ sim B [1] $ et $ B [1]. ] \ sim B [3] $ a tendance à être inséré entre des plages étroites de $ A [0] $. Dans un tel cas, $ A [0] $ sera pris tôt dans la plage de recherche et vous empêchera de chercher loin en vain. (Le plus gros inconvénient de la recherche de bissection) De plus, puisque la plage de $ B [i] $ qui est la cible après avoir été capturée est étroite, il n'y a pas de grande différence entre la recherche linéaire et la recherche par dichotomie à partir de là. En revanche, si la dichotomie est meilleure, c'est un intervalle assez grand $ (B [2 ^ {n}] \ sim B [2 ^ {n + 1} -1]) (n \ gg 1) $ $ A [0] $ devrait être inclus dans, donc dans un tel cas, la dichotomie est naturellement plus efficace. De cette manière, on peut dire que la dichotomie sans rang considère les deux cas de manière bien équilibrée.

Fondamentalement, Tim Sort a l'ambiance d'effectuer un basculement naturel entre la recherche linéaire et la dichotomie par le biais d'une «dichotomie sans rang». Il semble que l'indice de commutation y est appelé ** Seuil du mode galop **. Le seuil semble être fixé à ** 7 **. Ceci est basé sur le nombre d'éléments consécutifs depuis le début (la fin) d'une exécution à fusionner qui peuvent être copiés dans le tableau fusionné dans cet ordre. S'il y a plus de copies consécutives que cette valeur ** 7 **, il semble que la dichotomie soit activement réalisée en disant ** Mode galop **. La norme pour ce nombre ** 7 ** semble provenir des résultats jusqu'à présent que la recherche linéaire est plus rapide si elle est de 7 ou moins.

En arrière-plan de la définition d'un tel mode, s'il y a une tendance de ces deux courses près de la valeur minimale et de la valeur maximale de l'élément, la séquence des autres éléments de taille intermédiaire des deux exécutions Il semble qu'il soit défini car il y aura une tendance similaire.

2-4. Mémoire de copie des colonnes utilisées pour le tri par fusion

Lors de la fusion de deux colonnes avec un tri par fusion, réservez une copie de l'une des colonnes en mémoire. Fondamentalement, pour effectuer un tri par fusion avec le nombre d'éléments $ O (n) $, il est nécessaire de sécuriser une zone mémoire de $ O (n) $. L'allocation de cette zone mémoire est une surcharge du tri par fusion. Pour réduire cette surcharge et effectuer des tris de fusion plus rapidement, essayez de réduire cette zone d'allocation de mémoire.

Dans TimSort, s'il y a deux exécutions, ** faites une copie de l'analyse avec le plus petit nombre d'éléments. ** Cependant, dans le cas de run, puisqu'il s'agit d'une colonne qui a déjà été triée, il est possible de réduire encore l'allocation de la zone mémoire. Comment faire?

Tout d'abord, faites attention à la plus grande des valeurs minimales des deux essais. Soit A celui avec l'élément le plus grand. Si des éléments avec des valeurs plus petites sont alignés consécutivement dans l'exécution B, qui n'est pas A, la sous-colonne peut être laissée là sans aucune altération. (Comme décrit ci-dessous, il est efficace de fusionner des zones de mémoire consécutives.) Cette quantité peut être triée par fusion ou laissée telle qu'elle était auparavant, elle est donc exclue de la cible. De plus, nous ferons de même pour le plus gros. Cela réduira la taille de l'exécution effective qui sera triée par fusion.

Lorsque vous recherchez une colonne continue comme celle ci-dessus, effectuez la «dichotomie sans rang» mentionnée précédemment.

Par conséquent, la zone de mémoire requise pour la copie peut être réduite du nombre d'éléments minimum consécutifs et d'éléments maximum qui sont copiés en continu dans le tableau fusionné **. De cette façon, il semble que la surcharge est réduite et la vitesse est augmentée.

2-4-1. Les exécutions dans les zones de mémoire adjacentes sont combinées

Fondamentalement, lorsque vous mettez une course dans la pile, mettez-la dans l'ordre des camarades adjacents dans la zone de mémoire. Comme vous pouvez le voir à partir du faux algorithme de fusion ci-dessus, l'exécution à fusionner sera fusionnée l'une à côté de l'autre dans la pile. Si vous continuez ce type de fusion, les éléments que vous souhaitez fusionner seront fusionnés entre les zones de mémoire adjacentes.

C'est très pratique. Les variables de type référence telles que les tableaux pointent ou ne pointent pas vers des pointeurs sans changer la structure de la mémoire elle-même. De plus, lors de leur fusion, supprimez simplement le pointeur central supplémentaire et modifiez la taille à gérer, et il sera facile à gérer comme un seul tableau. (Étant donné que les types des éléments du tableau à trier sont les mêmes depuis le début), on peut s'attendre à ce qu'un tableau de grande taille puisse être facilement créé et que l'opération du tableau puisse être facilement effectuée. (Veuillez vous précipiter ici.)

Et encore mieux, parce que run est un tableau déjà trié, vous pouvez faire les commodités suivantes:

--S'il y a un sous-tableau composé d'éléments plus petits que le début du tableau arrière dans le tableau dans la zone avant la mémoire, le sous-tableau est complété comme un état trié sans vraiment rien faire.

• À l'inverse, s'il y a un sous-tableau constitué d'éléments plus grands que le dernier élément du tableau précédent dans le tableau dans la zone derrière la mémoire, le sous-tableau sera créé comme un état trié sans rien faire. Il y a.

De cette manière, on peut lire que la nature triée de l'analyse et la nature adjacente de la mémoire sauveront efficacement les opérations inutiles.

finalement

J'ai essayé de l'expliquer avec beaucoup de mots sensuels et de calculs intuitifs pour pouvoir me mettre en colère et comprendre moi-même TimSort. Cela peut avoir été un article fronçant les sourcils pour ceux qui sont très stricts et préfèrent la précision. D'un autre côté, même si j'avais peur de faire des erreurs et que je ne pouvais pas entrer dans le cœur de la construction de ma compréhension, ce serait une liste de termes techniques enveloppés de fumée, de sorte que je ne serais pas satisfait. Je sens que je suis devenu.

Certaines personnes peuvent se plaindre d'articles qui ne sont pas très précis, mais comme je les ai écrits, cela a pris du temps et des efforts, et des expressions plus précises sont disponibles dans la suite et la deuxième édition et les suivantes. J'apprécierais que vous me pardonniez le fait que j'ai accumulé de la force physique.

De plus, il a fallu un certain temps pour comprendre et avoir faim, et je pense que certaines parties ont été complètement mal comprises en raison d'un manque de compréhension. Si vous trouvez un tel point, nous vous serions reconnaissants si vous pouviez le signaler et nous donner des conseils.