Pourquoi Java n'utilise-t-il pas un tri Radix sur les primitives?

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) est implémenté comme un «tri rapide réglé» plutôt que comme un tri radix.

J'ai fait une comparaison de vitesse il y a quelque temps, et avec quelque chose comme n> 10000, le tri radix était toujours plus rapide. Pourquoi?

Je suppose que:

• Array.sort est implémenté comme quicksort, car quicksort peut trier n'importe quoi en un temps décent avec un comparateur.
• Le tri d'une liste de 10 000 entrées n'est pas si courant. L'accès à une structure de données de 10000 éléments ou plus est assez courant. Si vous devez maintenir l'ordre, un arbre de recherche équilibré est souvent une meilleure façon de procéder que de trier l'ensemble de votre tableau chaque fois que vous avez besoin du plus petit élément.
• Le tri des primitives n'est pas si courant, malgré ce que l'université peut enseigner.

Le fait est que ce n'est pas un cas d'utilisation si courant que son optimisation doit être dans la bibliothèque standard. Si vous avez écrit une application, qui a des problèmes de performances, où vous déterminez par le profilage que le tri d'un tableau de plus de 10000 pouces est en fait le goulot d'étranglement, alors vous pourriez aussi bien écrire le tri à la main ou reconsidérer votre choix de structure de données dans le premier endroit.

Back2dos a tout dit, je vais juste essayer de clarifier davantage le point qui, selon moi, est le plus important:

Le tri Radix ne peut trier que les valeurs primitives réelles contenues dans le tableau, en fonction de leurs modèles de chiffres binaires. Dans des scénarios réels d'ingénierie logicielle du monde réel, ce cas n'est presque jamais rencontré . Ce que nous avons tendance à faire beaucoup plus souvent est de trier des tableaux de structures de données plus complexes (non primitives), et parfois nous trions des tableaux d'index vers d'autres entités.

Maintenant, un tableau d'index à d'autres entités est en fait un tableau de primitives, mais l'ordre de tri est fourni par l'interface de comparateur (et / ou délégué en C #) qui compare non pas les index, mais les entités indexées par les index. Ainsi, l'ordre de tri n'a absolument aucun rapport avec l'ordre des valeurs des primitives, et donc le tri radix est absolument inutile pour ce scénario.

Un exemple:

Nous avons un tableau de chaînes: [0] = "Mike", [1] = "Albert", [2] = "Zoro". Ensuite, nous déclarons un tableau d'index à ces chaînes: [0] = 0, [1] = 1, [2] = 2. Ensuite, nous trions le tableau d'index, en lui passant un comparateur qui compare non pas les index eux-mêmes, mais les chaînes réelles référencées par ces index. Après le tri, le tableau d'index résultant ressemblera à ceci: [0] = 1, [1] = 0, [2] = 2. Comme vous pouvez le voir, cet ordre de tri n'a rien à voir avec les modèles binaires des valeurs contenues dans le tableau, et pourtant en parcourant ce tableau d'index et en récupérant chaque chaîne correspondante, nous visitons les chaînes dans l'ordre trié.