Tri de bibliothèque

Prenez un tableau en ordre inverse et appliquez-lui un tri avec de simples insertions .



Voyez avec quel grincement l'élément suivant est inséré au bon endroit. Pour cela, vous devez libérer le lieu d'insertion, à cause duquel vous devez déplacer tous les éléments précédemment insérés.

Et comme ce serait bien s'il y avait des espaces vides entre les éléments insérés plus tôt! Ensuite, il ne faudrait pas faire glisser les rangées d'éléments juste pour en insérer un.

En 2004, trois experts en informatique - Michael Bender, Martin Farah-Colton et Miguel Mostiro - ont décidé de modifier le tri avec de simples encarts de cette manière. Ils ont suggéré de former une partie ordonnée du réseau, en laissant des espaces entre les éléments insérés.

Le bibliothécaire a besoin que les livres soient classés par ordre alphabétique sur une longue étagère: en commençant à gauche de la lettre "A", les livres sont juste à côté les uns des autres jusqu'au "I" même. Si la bibliothèque a reçu un nouveau livre lié à la section "B", alors pour le mettre sur l'étagère au bon endroit, vous devez déplacer chaque livre, en commençant quelque part du milieu de la section "B" jusqu'au dernier "I". Il s'agit d'un tri par insertions simples. Cependant, si le bibliothécaire réservait l'espace libre dans chaque section, il lui suffisait de ne déplacer que quelques livres pour faire de la place aux nouveautés. C'est le principe de base du tri des bibliothèques.

Algorithme

• 1. Créez un tableau auxiliaire vide, plusieurs fois plus grand que le tableau principal.
• 2. Pour l'élément suivant, nous recherchons l'emplacement d'insertion dans le tableau auxiliaire.
  • 2.1. Si vous trouvez un endroit à insérer, transférez l'élément et revenez à l'étape 2.
  • 2.2. S'il n'y a pas de place pour l'insertion, rééquilibrez le réseau auxiliaire et revenez au point 2.
• 3. Après avoir traité tous les éléments, transférez-les à nouveau dans le tableau principal.

À première vue, il semble que le tri soit facile et simple. Pour dissiper cette illusion, nous considérons plus en détail les points clés de l'algorithme.

Taille de la baie auxiliaire

Bien qu'il n'y ait pas d'opinion établie, combien de fois le réseau auxiliaire doit être plus grand que le réseau principal.

Si vous en prenez trop, il y aura beaucoup d'espace entre les éléments, cependant, la recherche du site d'insertion et le rééquilibrage seront plus lents, en raison des grandes distances entre les éléments. Le rééquilibrage se produira moins souvent, mais ils devront y consacrer plus de ressources. Si vous en prenez trop peu, la recherche et le rééquilibrage seront moins chers, mais vous devrez reformater le tableau plus souvent. En général, il doit encore être testé avec différentes valeurs et la méthode de piquer scientifique détermine la meilleure option.

Si nous décidons combien de fois le tableau auxiliaire est plus grand que le tableau principal, alors la formule pour déterminer le nombre exact d'éléments pour lui ressemble à ceci:

NewSize = ε × (Taille + 1) - 1

NewSize - le nombre d'éléments dans le tableau auxiliaire
ε - combien de fois le tableau auxiliaire est plus grand que le tableau principal
Taille - le nombre d'éléments dans le tableau principal

Si nous multiplions simplement la taille par un facteur: NewSize = Size × ε , alors pour une distribution uniforme, nous n'aurons pas assez de cellules dans la quantité de ε - 1 pièces. Autrement dit, il est possible de les organiser uniformément, mais la première cellule remplie ou la dernière sera située près du bord du réseau auxiliaire. Et nous avons besoin que les espaces vides dans les cellules remplies soient réservés de tous les côtés - y compris avant le premier élément et après le dernier.



Cela semble être une bagatelle, mais en fait, il est important pour le rééquilibrage, pour garantir des emplacements libres pour l'insertion n'importe où, y compris lors du traitement des derniers éléments du tableau principal.

Rechercher le lieu d'insertion dans le réseau auxiliaire

Bien sûr, ici, vous avez besoin d'une recherche binaire. Cependant, l'implémentation classique ne fonctionnera pas pour nous.

Premièrement, le réseau auxiliaire se compose principalement de vide. Par conséquent, en dichotomisant récursivement la structure, nous rencontrerons pour la plupart des cellules non remplies. Dans ces cas, vous devez aller un peu à gauche ou à droite, jusqu'à la cellule non vide la plus proche. Ensuite, aux extrémités du segment, il y aura des éléments significatifs qui vous permettront de calculer la moyenne arithmétique et de poursuivre la recherche binaire en profondeur.

Deuxièmement, n'oubliez pas les bords. Si vous devez insérer un élément minimum ou maximum, une recherche binaire parmi les éléments insérés précédemment ne mènera à rien. Par conséquent, il vaut la peine de considérer les cas limites - vérifiez d'abord s'il est nécessaire de placer un élément près de la bordure gauche ou droite du tableau et sinon, utilisez la recherche binaire.

Troisièmement, compte tenu des spécificités de l'application, il convient de procéder à des modifications supplémentaires afin de minimiser le nombre de rééquilibrages de tableaux. Si l'élément inséré est égal à la valeur à l'une des extrémités du segment, vous ne devriez peut-être pas l'insérer au milieu du segment. Il est plus logique de placer à côté d'un élément de valeur égale à celui-ci. Cela remplira plus efficacement l'espace vide du tableau auxiliaire.

Quatrièmement, cinquième et ainsi de suite. La qualité de la recherche de l'emplacement d'insertion affecte directement la vitesse de tri, car la sélection des emplacements infructueux pour l'insertion entraîne un rééquilibrage inutile. Par exemple, il peut être utile de diviser les segments non pas exactement au milieu, mais plus près du bord gauche ou droit du segment, en fonction du bord auquel l'élément d'insertion est le plus proche en valeur?

L'algorithme de recherche binaire lui-même est semé d'embûches, et compte tenu des nuances supplémentaires susmentionnées, il ne devient finalement en aucun cas une tâche non triviale.

Rééquilibrage des baies

La recherche binaire n'est pas la chose la plus difficile à implémenter dans ce tri. Il y a toujours un rééquilibrage.

Lorsqu'il n'y a pas de place pour l'insertion (des éléments similaires ont été trouvés, mais il n'y avait pas de cellules libres entre eux), vous devez secouer le tableau auxiliaire pour libérer la place d'insertion. Cette secousse du tableau est un rééquilibrage.

De plus, le rééquilibrage est local ou complet .

Rééquilibrage local

Nous décalons autant d'éléments que nécessaire pour libérer le point d'insertion. La mise en œuvre d'un tel équilibrage est très simple, il vous suffit de trouver la cellule vide la plus proche du point d'insertion et de l'utiliser pour déplacer plusieurs éléments.

Il y a des nuances possibles. Par exemple, de quelle manière chercher la place vacante la plus proche? Afin d'éviter la situation où un décalage est impossible (c'est-à-dire si, d'un côté, toutes les cellules sont occupées jusqu'au bord du tableau), vous pouvez vous concentrer sur la position du point d'insertion par rapport au milieu du tableau. Si vous avez besoin d'insérer sur le côté gauche de la matrice, puis déplacez vers la droite, si à droite - vers la gauche. Si ε ≥ 2, cette approche élimine la situation dans laquelle un décalage est impossible (car dans la moitié du réseau auxiliaire, il y a plus qu'assez d'espace pour tous les éléments).

Dans l'interprétation de l'auteur de l'algorithme, un rééquilibrage local est implicite.

Rééquilibrage complet

Une alternative intéressante au local est un rééquilibrage complet. Autrement dit, dans le tableau auxiliaire, décaler tous les éléments disponibles afin qu'il y ait (presque) les mêmes espaces entre eux.



J'ai essayé les deux options et jusqu'à présent, j'observe qu'avec le rééquilibrage local, l'algorithme fonctionne 1,5 à 2 fois plus rapidement qu'avec une version complète. Cependant, un rééquilibrage complet peut toujours être utile. Par exemple, si vous devez effectuer un rééquilibrage local trop souvent, cela signifie que dans le réseau dans certaines régions, de nombreux «caillots de sang» se sont accumulés, ce qui inhibe l'ensemble du processus. Un rééquilibrage complet effectué une seule fois, vous permet de vous débarrasser de toute congestion locale d'un seul coup.

Voyons comment rééquilibrer complètement.

Vous devez d'abord calculer le nombre maximal de cellules que nous pouvons allouer pour chaque élément du tableau auxiliaire. Il ne faut pas oublier que les cellules vides doivent se trouver à la fois avant la première et après la dernière cellule remplie. La formule est:



M - le nombre de cellules pouvant être allouées à chaque élément
NewSize - taille du tableau auxiliaire
Count - le nombre actuel d'éléments non vides dans le tableau auxiliaire

Cette fraction doit être réduite à une valeur entière (c'est-à-dire arrondie vers le bas). Il est évident d'après la formule que plus il y a d'éléments transférés dans le réseau auxiliaire, moins nous pouvons sélectionner de cellules pour le voisinage de chaque élément.

Connaissant M , nous obtenons facilement la position exacte de chaque élément non vide dans le réseau auxiliaire sur lequel il devrait être situé une fois le rééquilibrage terminé.

NewPos = Nombre × M

NewPos - nouvelle position d'article après rééquilibrage
Number - quel est l'élément non vide dans le tableau auxiliaire (1 ≤ Number ≤ Count)
M - le nombre de cellules allouées à chaque élément

De nouvelles positions sont connues, pouvez-vous simplement trier les éléments non vides dans le tableau auxiliaire et les transférer vers d'autres endroits? Oh non, ne vous précipitez pas. Il n'est pas seulement nécessaire de transférer des éléments, il est important de maintenir leur ordre. Et à la suite de la recherche et de l'insertion binaires, les éléments peuvent s'avérer beaucoup à gauche et à droite de la position dans laquelle ils devraient être après le rééquilibrage. Et à l'endroit où vous souhaitez vous déplacer, il peut y avoir un autre élément qui doit également être attaché quelque part. De plus, vous ne pouvez pas transférer un élément s'il y a d'autres éléments entre ses anciennes et nouvelles positions dans le tableau auxiliaire - sinon les éléments se mélangeront, et il est extrêmement important pour nous de ne pas mélanger l'ordre.

Par conséquent, pour rééquilibrer, il ne suffira pas de passer par le cycle habituel et de simplement déplacer chaque élément d'une poche à l'autre. Il faut toujours utiliser la récursivité. Si un élément ne peut pas être déplacé vers un nouvel endroit (d'autres éléments sont apparus entre ses anciennes et nouvelles positions), alors vous devez d'abord comprendre (récursivement) ces invités non invités. Et puis tout sera arrangé correctement.

Cas dégénéré

Pour la plupart des tri par insertions, un tableau en ordre inverse est la pire situation. Et le tri d'un bibliothécaire, hélas, ne fait pas exception.



Les éléments tendent vers le bord gauche du réseau auxiliaire, ce qui fait que les espaces vides s'épuisent rapidement. Vous devez rééquilibrer le tableau très souvent.

Soit dit en passant, si nous prenons un tableau presque ordonné (le meilleur cas pour le tri par de simples insertions), alors nous obtenons le même problème. Les éléments nouvellement arrivés n'obstrueront pas la gauche, mais le côté droit du réseau auxiliaire, ce qui entraînera également un rééquilibrage trop fréquent.

Le tri de bibliothèque gère efficacement les ensembles de données aléatoires. La commande partielle (directe et inverse) nuit aux performances de vitesse.

Complexité algorithmique

Sur de grands ensembles de données aléatoires, l'algorithme donne la complexité temporelle O ( n log n ). Pas mal du tout!

Sur des ensembles de données aléatoires uniques (ou principalement uniques) avec la sélection correcte du coefficient ε et la mise en œuvre réussie de la recherche binaire, le nombre de rééquilibres peut être minimisé, voire évité. On peut faire valoir que l'algorithme a la meilleure complexité temporelle O ( n ).

Un pourcentage important de données se répétant en valeur, ainsi que la présence dans le tableau de sous-séquences ordonnées (dans l'ordre direct ou inverse) conduit à un rééquilibrage fréquent du tableau auxiliaire et, par conséquent, à une dégradation de la complexité temporelle en O (n ² ) dans les cas les plus défavorables.

Le moins de l'algorithme, bien sûr, est que le réseau auxiliaire nécessite O ( n ) de mémoire supplémentaire.

Possibilités d'amélioration

Bien que l'algorithme lui-même soit instructif et efficace sur des données aléatoires, en une décennie et demie, peu s'y sont intéressés.

Si vous recherchez sur Google la «tri par bibliothèque», vous trouverez un article superficiel sur Wikipedia anglais, le PDF de l’auteur (dont on comprend peu) et une rare ré-publication de ces maigres informations. De plus, il existe une bonne visualisation sur YouTube, où les tableaux principal et auxiliaire ont été initialement combinés. Tous les liens se trouvent à la fin de l'article.

La recherche de «tri de bibliothèque» est encore plus amusante - dans l'exemple, vous découvrirez les différents tri inclus dans différentes bibliothèques, cependant, ces algorithmes ne seront pas liés au tri de bibliothèque authentique .

Et il y a quelque chose à améliorer:

1. Sélection empirique du coefficient optimal ε .
2. Modification (en tenant compte des spécificités de l'algorithme général) de la recherche binaire pour la détermination la plus efficace du point d'insertion.
3. Minimiser les coûts de rééquilibrage.

Si vous polissez ces endroits, alors peut-être que le tri de la bibliothèque en vitesse est égal au tri rapide?

Code source

Je n'ai pas réussi à préparer l'implémentation en Python, il existe une version fonctionnelle en PHP.








J'ai dû coder moi-même à partir de zéro, sur la base d'une description générale de la méthode. Je n'ai pas vu de vitesse proche du tri rapide; mon option de tri de bibliothèque trie 10 à 20 fois plus lentement que le tri rapide. Mais la raison, bien sûr, est que ma mise en œuvre est trop grossière, beaucoup n'a pas été prise en compte.

J'aimerais voir une version des créateurs de l'algorithme. J'écrirai aujourd'hui aux auteurs (et leur jetterai un lien vers cet habrastatu), ils vont tout à coup répondre. Bien que ... je me souviens, j'ai essayé de contacter Allen Beachich ( tri ABC ) et Jason Morrison ( tri J ), mais le résultat était le même que si j'écrivais dans Sportloto.

UPD Martin Farah-Colton m'a répondu qu'ils n'avaient jamais fait l'implémentation:

Je crains que nous n'ayons jamais implémenté ces algorithmes.

L'essentiel est l'idée :)

Caractéristiques de l'algorithme

Les références

Tri de bibliothèque

Visualisation de l'algorithme de tri de bibliothèque

Le tri par insertion est O (n log n)

Auteurs de l'algorithme:

Michael A. Bender
Martin Farah-Colton
Miguel Mostiro

Articles de série:

• Application Excel AlgoLab.xlsm
• Exchange Sorts
• Tri d'insertion
  • Tri bibliothécaire
  • Tri solitaire
  • Trier "Tour de Hanoi"
  • Tri des jeunes tables
  • Inverser le tri
  • Insérer une comparaison de tri
• Trier par sélection
• Fusionner les tris
• Trier par distribution
• Tri hybride

Tri ajouté à AlgoLab. Vous pouvez donc expérimenter avec de petits ensembles de données.

Dans ce cas, vous pouvez décider combien de fois le tableau auxiliaire est plus grand que le tableau principal. Pour sélectionner le coefficient ε, vous pouvez cliquer avec le bouton droit sur la cellule avec «Tri de bibliothèque» et sélectionner «Modifier la note». Et dans la note, définissez soigneusement la valeur entière pour e de 2 à 5. Si vous entrez autre chose à la place de ces nombres, la valeur par défaut = 2 sera utilisée.

Vous pouvez également sélectionner le type de rééquilibrage. Si vous définissez local = 1, le rééquilibrage local sera utilisé. Si local = 0 - complet.

Et n'oubliez pas de définir l'échelle optimale pour la feuille de processus avant de commencer la visualisation, sinon la matrice auxiliaire ne rentrera pas sur l'écran.