Pourquoi Radix Sort n'est-il pas utilisé plus souvent?

Il est stable et a une complexité temporelle de O (n). Il devrait être plus rapide que les algorithmes comme Quicksort et Mergesort, mais je ne le vois presque jamais utilisé.

Contrairement au tri radix, le tri rapide est universel, tandis que le tri radix n'est utile que pour les clés entières de longueur fixe.

Vous devez également comprendre que O (f (n)) signifie vraiment dans l'ordre de K * f (n), où K est une constante arbitraire. Pour le tri radix, ce K se trouve être assez grand (au moins ordre de nombre de bits dans les entiers triés), d'autre part quicksort a l'un des K les plus bas parmi tous les algorithmes de tri et la complexité moyenne de n * log (n). Ainsi, dans un scénario réel, le tri rapide sera très souvent plus rapide que le tri radix.

La plupart des algorithmes de tri sont polyvalents. Étant donné une fonction de comparaison, ils fonctionnent sur n'importe quoi, et des algorithmes comme Quicksort et Heapsort trient avec O (1) de mémoire supplémentaire.

Le tri Radix est plus spécialisé. Vous avez besoin d'une clé spécifique qui est dans l'ordre lexicographique. Vous avez besoin d'un seau pour chaque symbole possible dans la clé, et les seaux doivent contenir de nombreux enregistrements. (Alternativement, vous avez besoin d'un grand tableau de compartiments qui contiendra toutes les valeurs de clés possibles.) Vous aurez probablement besoin de beaucoup plus de mémoire pour effectuer le tri radix, et vous allez l'utiliser de manière aléatoire. Rien de tout cela n'est bon pour les ordinateurs modernes, car vous risquez d'obtenir des erreurs de page comme Quicksort, il y aura des échecs de cache.

Enfin, les gens n'écrivent généralement plus leurs propres algorithmes de tri. La plupart des langues ont des bibliothèques pour trier, et la bonne chose à faire est normalement de les utiliser. Étant donné que le tri radix n'est pas universellement applicable, doit généralement être adapté à l'utilisation réelle et utilise beaucoup de mémoire supplémentaire, il est difficile de le mettre dans une fonction de bibliothèque ou un modèle.

Il est assez rare que les clés que vous triez soient en fait des entiers dans une plage connue et clairsemée. Habituellement, vous avez des champs alphabétiques, qui semblent prendre en charge le tri non comparatif, mais comme les chaînes du monde réel ne sont pas réparties uniformément dans l'alphabet, cela ne fonctionne pas aussi bien qu'il le devrait en théorie.

D'autres fois, le critère n'est défini que de manière opérationnelle (compte tenu de deux enregistrements, vous pouvez décider lequel vient en premier, mais vous ne pouvez pas évaluer à quel point en bas de l'échelle un enregistrement isolé est). Ainsi, la méthode n'est souvent pas applicable, moins applicable que vous ne le pensez, ou tout simplement pas plus rapide que O (n * log (n)).

Je l'utilise tout le temps, en fait plus que des sortes basées sur des comparaisons, mais je suis certes une bizarrerie qui fonctionne plus avec des nombres qu'autre chose (je ne travaille presque jamais avec des chaînes, et elles sont généralement internées si c'est le cas à quel moment radix le tri peut être utile à nouveau pour filtrer les doublons et calculer les intersections d'ensembles; je ne fais pratiquement jamais de comparaisons lexicographiques).

Un exemple de base est les points de tri radix selon une dimension donnée dans le cadre d'une recherche ou d'un fractionnement médian ou un moyen rapide de détecter des points coïncidents, des fragments de tri en profondeur ou le tri radix d'un tableau d'index utilisé dans plusieurs boucles pour fournir un accès plus compatible avec le cache modèles (ne pas aller et venir en mémoire uniquement pour revenir en arrière et recharger la même mémoire dans une ligne de cache). Il y a une application très large au moins dans mon domaine (infographie) juste pour trier sur des touches numériques de taille fixe 32 bits et 64 bits.

Une chose que je voulais dire et dire, c'est que le tri radix peut fonctionner sur les nombres à virgule flottante et les négatifs, bien qu'il soit difficile d'écrire une version FP aussi portable que possible. De plus, alors qu'il s'agit de O (n * K), K doit simplement être le nombre d'octets de la taille de la clé (ex: un million d'entiers 32 bits prendrait généralement 4 passes de la taille d'un octet s'il y a 2 ^ 8 entrées dans le compartiment ). Le modèle d'accès à la mémoire a également tendance à être beaucoup plus convivial pour le cache que les triages rapides, même s'il a généralement besoin d'une matrice parallèle et d'une petite baie (le second peut généralement s'adapter parfaitement à la pile). QS pourrait effectuer 50 millions de swaps pour trier un tableau d'un million d'entiers avec des modèles d'accès aléatoire sporadiques. Le tri radix peut le faire en 4 passages linéaires compatibles avec le cache sur les données.

Cependant, le manque de conscience de pouvoir le faire avec un petit K, sur des nombres négatifs et en virgule flottante, pourrait très bien contribuer de manière significative au manque de popularité des sortes de radix.

Quant à mon opinion sur les raisons pour lesquelles les gens ne l'utilisent pas plus souvent, cela peut être dû à de nombreux domaines n'ayant généralement pas besoin de trier les numéros ou de les utiliser comme clés de recherche. Cependant, juste sur la base de mon expérience personnelle, beaucoup de mes anciens collègues ne l'ont pas non plus utilisé dans des cas où il convenait parfaitement, et en partie parce qu'ils ne savaient pas qu'il pouvait être fait pour fonctionner sur la PF et les négatifs. Donc, à part qu'il ne fonctionne que sur des types numériques, il est souvent considéré comme encore moins applicable qu'il ne l'est réellement. Je ne l'aurais pas autant utilisé non plus si je pensais que cela ne fonctionnait pas sur les nombres à virgule flottante et les entiers négatifs.

Quelques repères:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

Et c'est juste avec mon implémentation naïve ( mt_sort_intc'est aussi un tri radix mais avec une branche de code plus rapide étant donné qu'il peut supposer que la clé est un entier). Imaginez à quelle vitesse une implémentation standard écrite par des experts pourrait être.

Le seul cas où j'ai trouvé que le type de base est moins bon que la comparaison très rapide basée sur C ++ std::sortétait pour un très petit nombre d'éléments, disons 32, auquel moment je crois std::sortcommencer à utiliser des types mieux adaptés au plus petit nombre d'éléments comme les tas ou l'insertion trie, bien qu'à ce stade mon implémentation utilise simplement std::sort.

Une autre raison: le tri de nos jours est généralement implémenté avec une routine de tri fournie par l'utilisateur attachée à une logique de tri fournie par le compilateur. Avec un tri radix, cela serait considérablement plus complexe et s'aggrave encore lorsque la routine de tri agit sur plusieurs clés de longueur variable. (Dites, nom et date de naissance.)

Dans le monde réel , je l' ai effectivement mis en place une sorte de radix fois. C'était dans l'ancien temps où la mémoire était limitée, je ne pouvais pas mettre toutes mes données en mémoire à la fois. Cela signifiait que le nombre d'accès aux données était beaucoup plus important que O (n) vs O (n log n). J'ai fait un passage à travers les données en allouant chaque enregistrement à un bac (par une liste des enregistrements dans quels bacs, sans déplacer quoi que ce soit.) Pour chaque bac non vide (ma clé de tri était du texte, il y aurait beaucoup de bacs vides) J'ai vérifié si je pouvais réellement mettre les données en mémoire - si oui, apportez-les et utilisez le tri rapide. Si non, créez un fichier temporaire contenant uniquement les éléments dans le bac et appelez la routine récursivement. (En pratique, peu de casiers débordent.) Cela a provoqué deux lectures complètes et une écriture complète sur le stockage réseau et quelque chose comme 10% de cela sur le stockage local.

De nos jours, ces problèmes de big data sont beaucoup plus difficiles à rencontrer, je n'écrirai probablement plus jamais rien de ce genre. (Si j'étais confronté aux mêmes données ces jours-ci, je spécifierais simplement un système d'exploitation 64 bits, ajouter de la RAM si vous obtenez un thrashing dans cet éditeur.)

Si tous vos paramètres sont tous des entiers et si vous avez plus de 1024 paramètres d'entrée, le tri radix est toujours plus rapide.

Pourquoi?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

Le tri radix est donc plus rapide lorsque

log(n)> max num of digits

Le nombre entier maximal en Java est 2147483647. Ce qui est long de 10 chiffres

Le tri radix est donc toujours plus rapide

log(n)> 10

Par conséquent, le tri radix est toujours plus rapide lorsque n>1024