/ ?
Comment comparer des fichiers de deux twigs différentes?
Comment puis-je sélectionner toutes les autres lignes comportant plusieurs curseurs dans Sublime Text?
PostgreSQL ‘NOT IN’ et sous-requête
Est-il possible de concaténer des valeurs dans les options angulars ng
Vérifiez si l’énumération existe en Java
Comment obtenir l’identifiant unique d’un object qui remplace hashCode ()?
Expressions régulières multi-lignes dans Visual Studio
La création de fichiers de classe Java est-elle déterministe?
Regexp Java pour la validation du mot de passe
Case à cocher pour un booléen nullable
Je veux faire ma demande uniquement dans le paysage dans Android
Obtenir le nombre de lignes avec une requête GROUP BY
Comment activer le bouton “Partager” dans l’application Android?
Regex pour correspondre à des chaînes spécifiques sans préfixe donné
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.
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!
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:
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é. 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). 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!
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.