Java 7 utilise-t-il Tim Sort pour le tableau des méthodes.

Je ne trouve pas la documentation de Java 7, je ne peux que trouver sur Java 6, qui est toujours rapide ou fusionne. Est-ce que quelqu’un sait comment trouver la documentation de la méthode Arrays.sort dans Java 7?

Java 7 utilise un Quicksort à double pivot pour les primitives et TimSort pour les objects.

Selon la documentation de Java 7 API pour les primitives:

Note d’implémentation: L’algorithme de sorting est un Quicksort à double pivot par Vladimir Yaroslavskiy, Jon Bentley et Joshua Bloch. Cet algorithme offre des performances O (n log (n)) sur de nombreux ensembles de données qui entraînent une dégradation des autres Quicksorts en performances quadratiques et sont généralement plus rapides que les implémentations Quicksort traditionnelles (à un pivot).

Selon la documentation de l’API Java 7 pour les objects:

L’implémentation a été adaptée de la liste de sorting de Tim Peters pour Python (TimSort). Il utilise les techniques de Peter McIlroy “Optimistic Sorting and Information Theoretic Complexity”, dans Actes du quasortingème symposium annuel ACM-SIAM sur les algorithmes discrets, pp 467-474, janvier 1993.

Timsort est un sorting hybride “sorting et insertion”.

Je ne suis pas sûr que ce soit très différent de ce qu’il était dans Java 6, pour Arrays.sort JDK6:

une mesure rapide, adaptée de “Engineering a Sort Function” de Jon L. Bentley et M. Douglas McIlroy, pratique du logiciel et expérience, vol. 23 (11) P. 1249-1265 (novembre 1993)

Pour Object [] ou collections (Collections.sort ()), le sorting par fusion est utilisé.

Oui, Java 7 utilisera Timsort pour Arrays.sort. Voici le commit: http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79

Oui! … et aussi non.

Résumé

Dans les implémentations Open JDK 0 actuelles, Tim Sort est généralement utilisé pour sortinger les tableaux d’objects (par exemple, Arrays.sort(Object[]) et friends) – mais pour les tableaux primitifs (le rest des méthodes Arrays.sort ), diverses autres méthodes sont utilisés.

Pour les primitives, les heuristiques choisissent parmi une variété de méthodes de sorting telles que le sorting rapide, le sorting par fusion, le sorting par comptage 3 . en fonction des données en cours de sorting. La plupart de ces décisions sont simplement sockets en compte en fonction du type et de la taille du tableau en cours de sorting, mais pour long éléments int et long , la décision est en fait adaptative en fonction du sorting mesuré du tableau. Donc, vous avez l’adaptation / introspection (l’heuristique pour choisir un algorithme) en plus de l’adaptation / introspection (TimSort ou un sorting de fusion similaire) dans de nombreux cas!

Détails

Tim Sort est utilisé pour la plupart des objects, tels que Arrays.sort(Object[] a) , sauf si l’utilisateur a spécifiquement demandé le comportement hérité en définissant la propriété système java.util.Arrays.useLegacyMergeSort sur true.

Pour les primitifs, la situation est plus complexe. Au moins à partir de JDK 8 (version 1.8.0_111 ), diverses heurstics sont utilisées en fonction de la taille des tableaux sortingés, du type primitif et du «sorting» mesuré du tableau. Voici un aperçu:

  • Pour tous les types primitifs autres que les octets 1 , les tableaux de moins de 47 éléments sont simplement sortingés à l’aide du sorting par insertion (voir DualPivotQuicksort.INSERTION_SORT_THRESHOLD ). Ce seuil est également utilisé lors du sorting des sous-tableaux qui apparaissent lorsque la fusion ou le sorting rapide sont utilisés et que la taille du sous-tableau est inférieure au seuil. Ainsi, une sorte de sorting par insertion sera utilisée dans tous les types, et pour les petits tableaux, c’est le seul algorithme utilisé.
  • Pour les types primitifs byte , short et char , un sorting de comptage est utilisé pour les tableaux de grande taille. C’est un sorting simple qui prend le temps O(n + range) , où range représente le nombre total d’octets (256) ou les valeurs short / char (65536). Le sorting implique l’allocation d’un tableau sous-jacent de valeurs de range . Il n’est donc utilisé que lorsque le nombre d’éléments à sortinger représente une fraction significative de la plage totale. En particulier, il est utilisé pour les tableaux d’octets supérieurs à 29 éléments (soit ~ 11% de la plage) et les tableaux courts / caractères supérieurs à 3200 éléments (~ 5% de la plage).
  • Pour les tableaux d’octets, l’une des deux approches ci-dessus est toujours utilisée.
  • Pour long tableaux int et long au-dessus du seuil de sorting par insertion et pour short tableaux short / char au-dessus du seuil de sorting d’insertion et au-dessous du seuil de sorting, l’un des deux algorithmes suivants peut être utilisé: La méthode utilisée dépend de la mesure du sorting du tableau: l’entrée est divisée en séries d’éléments ascendants ou descendants. Si le nombre de ces exécutions est supérieur à 66, le tableau est considéré comme essentiellement non sortingé et sortingé avec un sorting rapide à double pivot. Sinon, le tableau est considéré comme étant principalement sortingé et la fusion est utilisée (en utilisant les exécutions déjà énumérées comme sharepoint départ).

L’ idée de trouver des exécutions et d’utiliser fusesort pour les sortinger est en fait très similaire à TimSort, bien qu’il y ait des différences. Donc, au moins pour certains parameters, le JDK utilise un fusionneur compatible avec l’exécution, mais pour beaucoup d’autres combinaisons de parameters, il utilise un algorithme différent, et au moins 5 algorithmes distincts sont utilisés au total!

Raisonnement

Le raisonnement derrière les différents comportements de sorting d’ Object[] versus primitif est probablement au moins double:

1) Les sortings de Object[] doivent être stables : les objects sortingés de la même manière apparaîtront dans le même ordre que l’entrée. Pour les tableaux primitifs, ce concept n’existe pas: les primitives sont entièrement définies par leur valeur, il n’y a donc pas de distinction entre un sorting stable et un sorting instable. Cela permet aux sortes primitives de se passer des algorithmes stables en faveur de la vitesse.

2) Les classes d’ Object[] doivent impliquer la méthode Object.compare() , qui peut être complexe et coûteuse. Même si la méthode compare() est simple, il y aura généralement une surcharge de méthode à moins que la méthode de sorting complète ne soit intégrée 2 . Donc, des sortes d’ Object[] seront généralement orientées vers la minimisation des comparaisons totales, même au prix d’une complexité algorithmique supplémentaire.

Les séries de tableaux primitifs, d’un autre côté, comparent simplement les valeurs primitives qui sont généralement de l’ordre d’un cycle ou deux. Dans ce cas, l’algorithme doit être optimisé en tenant compte à la fois du coût des comparaisons et de l’algorithme qui les entoure, étant donné qu’ils sont susceptibles d’avoir la même ampleur.


0 Au moins pour les versions entre Java 7 et Java 9, et bien sûr, cela inclut également le JDK d’Oracle car il est basé sur Open JDK. Il est probable que d’autres implémentations utilisent une approche similaire, mais je n’ai pas vérifié.

1 Pour les tableaux d’octets, le seuil de sorting par insertion est effectivement de 29 éléments, car il s’agit de la limite inférieure au-dessus de laquelle le sorting par comptage est utilisé.

2 Cela semble peu probable, car il est assez grand.

3 Le sorting par comptage n’est utilisé que pour les valeurs avec une plage relativement limitée de 16 bits ou moins: byte , short ou caractère.