Tri de nombres entiers

From Wikipedia, the free encyclopedia

En informatique, le tri de nombres entiers est le problème algorithmique consistant à trier une collection d'éléments au moyen de clés numériques, chacune étant un nombre entier. Les algorithmes conçus pour le tri des nombres entiers peuvent également souvent être appliqués aux problèmes de tri dans lesquels les clés sont des nombres décimaux, des nombres rationnels ou des chaînes de texte^[1].

La possibilité d'effectuer une arithmétique sur les clés permet aux algorithmes de tri d'entiers d'être plus rapides que les algorithmes de tri par comparaison, en fonction du détail des opérations autorisées dans le modèle de calcul et de la taille des entiers à trier.

Les algorithmes de tri de nombres entiers, notamment le tri par paquets, le tri comptage et le tri par base, sont largement utilisés et pratiques.

D'autres algorithmes de tri de nombres entiers avec des limites de temps plus faibles dans le pire des cas ne sont pas considérés comme pratiques pour les architectures informatiques à 64 bits ou moins.

Beaucoup de ces algorithmes sont connus, les performances dépendant du nombre d'éléments à trier, du nombre de bits par clé et du nombre de bits par mot de l'ordinateur exécutant l'algorithme de tri.

Tri par rapport aux files de priorité d'entiers

La complexité temporelle des algorithmes de tri d’entiers dépend généralement de trois paramètres : le nombre $n$ de valeurs à trier, la magnitude $K$ de la clé la plus grande possible à trier et le nombre $w$ de bits pouvant être représentés dans un seul mot machine de l'ordinateur sur lequel l'algorithme doit être exécuté. Typiquement, on suppose que $w \geq log 2 (max(n, K))$ ; c'est-à-dire que les mots machine sont suffisamment grands pour représenter un index dans la séquence de données d'entrée, et également suffisamment grands pour représenter une clé unique^[2].

Les algorithmes de tri de nombres entiers sont généralement conçus pour fonctionner soit dans la machine à pointeur, soit dans la machine RAM. La principale différence entre ces deux modèles réside dans la manière dont la mémoire peut être adressée. La machine RAM permet à toute valeur stockée dans un registre d'être utilisée comme adresse des opérations de lecture et d'écriture en mémoire, avec un coût unitaire par opération. Cette capacité permet à certaines opérations complexes sur les données d'être rapidement mises en œuvre à l'aide de recherches dans les tables. En revanche, dans le modèle de pointeur, les opérations de lecture et d'écriture utilisent les adresses stockées dans les pointeurs et il est interdit d'effectuer des opérations arithmétiques sur ces pointeurs. Dans les deux modèles, des valeurs de données peuvent être ajoutées et des opérations booléennes au niveau du bit et des opérations de décalage binaire peuvent généralement également être effectuées sur ces unités, en unités de temps par opération. Différents algorithmes de tri de nombres entiers supposent différentes hypothèses, toutefois, quant à savoir si la multiplication de nombres entiers est également autorisée en tant qu'opération temporelle^[3]. D'autres modèles de calcul plus spécialisés, tels que la PRAM, ont également été envisagés^[4].

Andersson, Miltersen & Thorup (1999) ont montré que, dans certains cas, les multiplications ou les recherches dans les tables requises par certains algorithmes de tri d'entiers pourraient être remplacées par des opérations personnalisées qui seraient plus facilement implémentées dans le matériel, mais qui ne sont généralement pas disponibles sur des ordinateurs polyvalents. Thorup (2003) amélioré ceci en montrant comment remplacer ces opérations spéciales par les instructions de manipulation de champs de bits déjà disponibles sur les processeurs Pentium.

Une file de priorité est une structure de données permettant de gérer un ensemble d'éléments munis de priorités numériques, comportant des opérations permettant de rechercher et de supprimer l'élément ayant la valeur de priorité minimale. Les files de priorité basées sur la comparaison, telles que le tas binaire, prennent un temps logarithmique par mise à jour, mais d'autres structures telles que l'arbre de van Emde Boas ou la file d'attente de compartiment peuvent être plus rapides pour les entrées dont les priorités sont de petits entiers. Ces structures de données peuvent être utilisées dans l'algorithme de tri par sélection, qui trie une collection d'éléments en recherchant et en supprimant de manière répétée le plus petit élément de la collection et en renvoyant les éléments dans l'ordre dans lequel ils ont été trouvés. Une file de priorité peut être utilisée pour gérer la collection d'éléments dans cet algorithme, et le temps pour cet algorithme sur une collection de $n$ éléments peut être limité par le temps nécessaire pour initialiser la file de priorité, puis pour effectuer $n$ opérations de recherche et suppression. Par exemple, l'utilisation d'un tas binaire comme file de priorité dans le tri par sélection conduit à l'algorithme de tri par tas, un algorithme de tri de comparaison de complexité temporelle en $O (n log n)$ . Au lieu de cela, l'utilisation du tri par sélection avec une file d’attente donne une forme de tri par casier et l’utilisation d’arbres de Van Emde Boas ou d’autres files d’attente avec priorité entière conduit à d’autres algorithmes de tri d’entiers rapides. ^[5]

Au lieu d'utiliser une file de priorité d'entiers dans un algorithme de tri, il est possible d'aller dans la direction opposée et d'utiliser les tris d'entiers comme sous-routine dans une structure de données de file de priorité d'entiers. Thorup (2007) a utilisé cette idée pour montrer que, s'il est possible de réaliser le tri d'entiers en temps linéaire par clé alors cette même complexité s'applique aux opérations d'insertion et de suppression dans une file de priorité. La réduction de Thorup est complexe et s’appuie cependant sur l'existence d'une multiplication rapide ou d'une recherche rapide dans une table mais il donne une file de priorité alternative utilisant l'addition et les opérations sur les booléens en temps $T (n) + T (log n) + T (log log n) + ...$ par opération, multipliant au plus le temps par un logarithme itéré.^[5]

Utilisabilité

Les algorithmes classiques de tri des nombres entiers de type tri pigeonhole, tri comptage et tri par base sont largement utilisés et pratiques^[6]. La plupart des recherches ultérieures sur les algorithmes de tri de nombres entiers ont été moins axées sur l'aspect pratique que sur les améliorations théoriques apportées à leur analyse des pires cas, et les algorithmes issus de cette ligne de recherche ne sont apparemment pas pratiques pour les architectures informatiques 64 bits actuelles, bien que des expériences ont montré que certaines de ces méthodes peuvent constituer une amélioration du tri de base pour les données de 128 bits ou plus par clé^[6]. De plus, pour les grands ensembles de données, le modèle d'accès mémoire quasi aléatoire de nombreux algorithmes de tri d'entiers peuvent les handicaper par rapport aux algorithmes de tri de comparaison conçus pour la hiérarchie de mémoire^[7].

Le tri de nombres entiers constitue l'un des six tests de performances en mathématiques discrètes de systèmes de calcul à haute productivité DARPA ^[8] et l'un des onze points de repère de la suite de tests de performances NAS .

Algorithmes pratiques

Le tri pigeonhole et le tri comptage peuvent tous les deux trier $n$ éléments de données dont les clés sont comprises entre $0$ et $K - 1$ dans le temps $O (n + K)$ . Dans le tri pigeonhole, les pointeurs vers les éléments de données sont distribués dans une table de compartiments, représentés comme des types de données de collection tels que des listes chaînées, en utilisant les clés comme indices dans la table. Ensuite, tous les compartiments sont concaténés ensemble pour former la liste de sortie^[9]. Le tri comptage utilise une table de compteurs à la place d'une table de compartiments, pour déterminer le nombre d'articles avec chaque clé. Ensuite, un calcul de somme de préfixes est utilisé pour déterminer la plage de positions dans la sortie triée à laquelle les valeurs de chaque clé doivent être placées. Enfin, lors d'un deuxième passage sur l'entrée, chaque élément est déplacé à la position de sa clé dans le tableau de sortie^[10]. Les deux algorithmes n'impliquent que de simples boucles sur les données d'entrée (prenant le temps $O (n)$ ) et sur l'ensemble des clés possibles (prenant le temps $O (K)$ ), donnant leur complexité temporelle en $O (n + K)$ .

Le tri par base est un algorithme de tri qui fonctionne pour des clés plus grandes que le tri pigeonhole ou le tri comptage en effectuant plusieurs parcours des données. Chaque parcours trie l'entrée en utilisant uniquement une partie des clés, en utilisant un algorithme de tri différent (tel que le tri pigeonhole ou le tri de comptage) qui ne convient qu'aux petites clés. Pour diviser les clés en parties, l'algorithme de tri par base calcule la notation positionnelle pour chaque clé, en fonction de certaines bases choisies; ensuite, la partie de la clé utilisée pour la $i$ ème passe de l'algorithme est le $i$ ème chiffre dans la notation positionnelle pour la clé complète, en partant du chiffre le moins significatif et en progressant vers le plus significatif. Pour que cet algorithme fonctionne correctement, l'algorithme de tri utilisé à chaque parcours des données doit être stable : les éléments avec des chiffres égaux ne doivent pas changer de position les uns avec les autres. Pour une plus grande efficacité, la base doit être choisie pour être proche du nombre d'éléments de données, $n$ . De plus, l'utilisation d'une puissance de deux près de $n$ comme base permet de calculer rapidement les clés de chaque parcours en utilisant uniquement des opérations rapides de décalage binaire et de masque. Avec ces choix, et avec le tri pigeonhole ou le tri par comptage comme algorithme de base, l'algorithme de tri par base peut trier $n$ éléments de données ayant des clés dans la plage de $0$ à $K - 1$ dans le temps $O (n log n K)$ ^[11].

Algorithmes théoriques

De nombreux algorithmes de tri d'entiers ont été développés dont l'analyse théorique montre qu'ils se comportent mieux que le tri par comparaison, le tri pigeonhole ou le tri par base pour des combinaisons suffisamment grandes de paramètres définissant le nombre d'éléments à trier, la plage de clés et la taille du mot machine. La performance d'un algorithme dépend des valeurs de ces paramètres. Cependant, malgré leurs avantages théoriques, ces algorithmes ne sont pas une amélioration pour les plages typiques de ces paramètres qui se posent dans des problèmes de tri pratiques.

Algorithmes pour les petites clés

Un arbre de Van Emde Boas peut être utilisé comme file de priorité pour trier un ensemble de $n$ clés, chacune dans la plage de $0$ à $K - 1$ , dans le temps $O (n log log K)$ . Il s'agit d'une amélioration théorique par rapport au tri par base lorsque $K$ est suffisamment grand. Cependant, pour utiliser un arbre de Van Emde Boas, il faut soit une mémoire directement accessible de $K$ mots, soit il faut la simuler à l'aide d'une table de hachage, en réduisant l'espace à une structure linéaire mais en rendant l'algorithme aléatoire.

Kirkpatrick & Reisch (1984) ont développé une technique plus sophistiquée, assez similaire et avec de meilleures performances théoriques. Ils ont observé que chaque lecture des données dans le tri par base peut être interprétée comme une technique de réduction de plage qui, en temps linéaire, réduit la taille de clé maximale d'un facteur de $n$ ; au lieu de cela, leur technique réduit la taille de la clé à la racine carrée de sa valeur précédente (divisant par deux le nombre de bits nécessaires pour représenter une clé), toujours en temps linéaire. Comme dans le tri par base, ils interprètent les clés comme des nombres en base $b$ de 2 chiffres pour une valeur de $b$ qui est approximativement $\sqrt K$ Ils regroupent ensuite les éléments à trier en compartiments en fonction de leurs chiffres élevés, en temps linéaire, à l'aide d'une grande mémoire directement accessible mais non initialisée ou d'une table de hachage. Chaque compartiment a un représentant, l'article dans le compartiment avec la plus grande clé; ils trient ensuite la liste des éléments en utilisant comme clés les chiffres hauts pour les représentants et les chiffres bas pour les non-représentants. En regroupant à nouveau les éléments de cette liste dans des compartiments, chaque compartiment peut être placé dans un ordre trié, et en extrayant les représentants de la liste triée, les compartiments peuvent être concaténés ensemble dans un ordre trié. Ainsi, en temps linéaire, le problème de tri est réduit à un autre problème de tri récursif dans lequel les clés sont beaucoup plus petites, la racine carrée de leur amplitude précédente. La répétition de cette réduction de plage jusqu'à ce que les clés soient suffisamment petites pour trier le compartiment conduit à un algorithme avec le temps d'exécution $O(n log log n K)$ .

Un algorithme aléatoire compliqué de Han & Thorup (2002) dans le modèle de calcul "RAM de mots" permet de réduire encore plus ces limites de temps, à $O(n \sqrt log log K)$ .

Algorithmes pour les grands mots

Un algorithme de tri d'entiers est dit non conservateur s'il nécessite une taille de mot $w$ qui est significativement plus grande que $log max(n, K)$ ^[12]. Un exemple extrême, si $w \geq K$ , et que toutes les clés sont distinctes, alors l'ensemble des clés peut être trié en temps linéaire en le représentant comme un tableau de bits, avec un bit à la position $i$ lorsque $i$ est l'une des clés d'entrée, puis en supprimant à plusieurs reprises le bit le moins significatif^[13].

L'algorithme de tri condensé non conservateur d' Albers & Hagerup (1997) utilise un sous-programme, basé sur le tri bitonique de Ken Batcher, pour fusionner deux séquences de clés triées suffisamment courtes pour être regroupées dans un seul mot machine. L'entrée de l'algorithme de tri condensés, une séquence d'articles stockés un par mot, est transformée en une forme condensés, une séquence de mots contenant chacun plusieurs éléments dans un ordre trié ; en utilisant ce sous-programme à plusieurs reprises pour doubler le nombre d'éléments condensés dans chacun mot. Une fois la séquence sous forme compactée, Albers et Hagerup utilisent une forme de tri fusion pour la trier. Lorsque deux séquences sont fusionnées pour former une seule séquence plus longue, le même sous-programme de tri bitonique peut être utilisé pour extraire à plusieurs reprises des mots condensés constitués des plus petits éléments restants des deux séquences. Cet algorithme gagne suffisamment d'accélération de sa représentation condensée pour trier son entrée en temps linéaire chaque fois qu'il est possible qu'un seul mot contienne des clés $Ω(log n log log n)$ ; c'est-à-dire, lorsque $log K log n log log n \leq cw$ pour une constante $c > 0$ .

Algorithmes pour quelques éléments

Le tri pigeonhole, le tri par comptage, le tri par base et le tri par arbre Van Emde Boas fonctionnent tous mieux lorsque la taille de la clé est petite; pour les clés suffisamment grandes, elles deviennent plus lentes que les algorithmes de tri comparatif. Cependant, lorsque la taille de la clé ou la taille du mot est très grande par rapport au nombre d'éléments (ou de manière équivalente lorsque le nombre d'éléments est petit), il peut de nouveau devenir possible de trier rapidement, en utilisant différents algorithmes qui tirent parti du parallélisme inhérent dans la capacité d'effectuer des opérations arithmétiques sur de gros mots.

Un premier résultat dans cette direction a été fourni par Ajtai, Fredman & Komlós (1984) en utilisant le modèle de calcul à sonde cellulaire (un modèle artificiel dans lequel la complexité d'un algorithme n'est mesurée que par le nombre d'accès à la mémoire qu'il effectue). S'appuyant sur leurs travaux, Fredman & Willard (1994) ont décrit deux structures de données, le tas Q et le tas atomique, qui peuvent être implémentées sur une machine à accès aléatoire. Le segment Q est une version bit parallèle d'un tri binaire, et permet à la fois des opérations de file de priorité et des requêtes de successeur et prédécesseur à effectuer en temps constant pour des ensembles d'éléments de taille $O ((log N) 1/4)$ , où $N \leq 2 w$ est la taille des tables précalculées nécessaires pour implémenter la structure de données. Le tas atomique est un B-arbre dans lequel chaque nœud d'arbre est représenté comme un tas Q; il permet des opérations de file de priorité en temps constant (et donc un tri) pour des ensembles d'éléments de taille $(log N) O (1)$ .

Andersson et al. (1998) fournissent un algorithme aléatoire appelé tri par signature qui permet un tri linéaire dans le temps d'ensembles jusqu'à $2 O ((log w) 1/2 - ε)$ éléments à la fois, pour toute constante $ε > 0$ . Comme dans l'algorithme de Kirkpatrick et Reisch, ils effectuent une réduction de plage en utilisant une représentation des clés sous forme de nombres dans la base $b$ pour un choix judicieux de $b$ . Leur algorithme de réduction de plage remplace chaque chiffre par une signature, qui est une valeur hachée avec $O (log n)$ bits de sorte que différentes valeurs de chiffre ont des signatures différentes. Si $n$ est suffisamment petit, les nombres formés par ce processus de remplacement seront significativement plus petits que les clés d'origine, permettant à l'algorithme de tri condensé non conservateur d' Albers & Hagerup (1997) de trier les nombres remplacés en temps linéaire. À partir de la liste triée des nombres remplacés, il est possible de former un tri condensé des clés en temps linéaire, et les enfants de chaque nœud du tri peuvent être triés récursivement en utilisant uniquement des clés de taille $b$ , après quoi un parcours d'arbre produit l'ordre trié des articles.

Algorithmes trans-dichotomiques

Fredman & Willard (1993) ont présenté le modèle d'analyse transdichotomique pour les algorithmes de tri d'entiers, dans lequel rien n'est supposé sur la plage des clés entières et il faut limiter les performances de l'algorithme en fonction du nombre de valeurs de données uniquement. Alternativement, dans ce modèle, le temps d'exécution d'un algorithme sur un ensemble de $n$ éléments est supposé être le temps d'exécution du pire cas pour toute combinaison possible de valeurs de $K$ et $w$ . Le premier algorithme de ce type était l'algorithme de tri des arbres de fusion de Fredman et Willard, qui s'exécute dans le temps $O(n log n / log log n)$ ; il s'agit d'une amélioration par rapport au tri par comparaison pour tout choix de $K$ et $w$ . Une version alternative de leur algorithme qui inclut l'utilisation de nombres aléatoires et d'opérations de division entière améliore cela à $O(n \sqrt log n)$ .

Depuis leur travail, des algorithmes encore meilleurs ont été développés. Par exemple, en appliquant à plusieurs reprises la technique de réduction de la plage Kirkpatrick - Reisch jusqu'à ce que les clés soient suffisamment petites pour appliquer l'algorithme de tri condensé Albers – Hagerup, il est possible de trier dans le temps $O (n log log n)$ ; cependant, la partie réduction de plage de cet algorithme nécessite soit une grande mémoire (proportionnelle à $\sqrt K$ ), soit une randomisation sous forme de tables de hachage^[14].

Han & Thorup (2002) ont montré comment trier en temps aléatoire $O(n \sqrt log log n)$ . Leur technique consiste à utiliser des idées liées au tri des signatures pour partitionner les données en de nombreuses petites sous-listes, d'une taille suffisamment petite pour que le tri des signatures puisse trier chacune d'elles efficacement. Il est également possible d'utiliser des idées similaires pour trier les entiers de manière déterministe dans le temps $O (n log log n)$ et en mémoire linéaire^[15]. En utilisant uniquement des opérations arithmétiques simples (pas de multiplications ou de recherches de table), il est possible de trier dans le temps aléatoire attendu $O (n log log n)$ ^[16] ou de manière déterministe dans le temps $O (n (log log n) 1 + ε)$ pour toute constante $ε > 0$ .