sort - ordenar fechas java

¿Está Java 7 usando Tim Sort para las matrices de métodos? (3)

No puedo encontrar la documentación de Java 7, solo puedo encontrar información sobre Java 6, que todavía es rápido o se fusiona. ¿Alguien sabe cómo encontrar la documentación del método Arrays.sort en Java 7?

Sí, Java 7 usará Timsort para Arrays.sort. Aquí está el commit: http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79

¡Sí! ... y también no.

Resumen

En las implementaciones Open JDK ⁰ actuales, Tim Sort se usa generalmente para ordenar matrices de objetos (es decir, Arrays.sort(Object[]) y amigos), pero para matrices primitivas (el resto de los métodos Arrays.sort ) una variedad de otros métodos son usados.

Para los primitivos, los heurísticos eligen entre una variedad de métodos de clasificación como quicksort, merge sort, count sort ³ . dependiendo de los datos que se ordenan La mayoría de estas decisiones se basan simplemente en el tipo y el tamaño de la matriz que se está ordenando, pero para los elementos int y long la decisión es realmente adaptativa en función de la ordenación medida de la matriz. ¡Así que tienes adaptación / introspección (la heurística para elegir un algoritmo) además de la adaptación / introspección (TimSort o clasificación de fusión similar) en muchos casos!

Detalles

Tim Sort se utiliza para la mayoría de los tipos de objetos, como Arrays.sort(Object[] a) , a menos que el usuario haya solicitado específicamente el comportamiento heredado estableciendo la propiedad del sistema java.util.Arrays.useLegacyMergeSort en verdadero.

Para los primitivos, la situación es más compleja. Al menos a partir de JDK 8 (versión 1.8.0_111 ) se 1.8.0_111 una variedad de heurísticos dependiendo del tamaño de las matrices que se están ordenando, el tipo primitivo y la "clasificación" medida de la matriz. Aquí hay una descripción general:

Para todos los tipos primitivos distintos de los bytes ¹ , las matrices de menos de 47 elementos se clasifican simplemente utilizando la ordenación de inserción (consulte DualPivotQuicksort.INSERTION_SORT_THRESHOLD ). Este umbral también se usa cuando se ordenan sub-arrays que surgen cuando se usan merge o quicksort y el tamaño del subcampo cae por debajo del umbral. Por lo tanto, se utilizará algún tipo de ordenación por inserción en todos los órdenes, y para matrices pequeñas es el único algoritmo utilizado.
Para los tipos primitivos byte , short y char , se usa un tipo de recuento para matrices de gran tamaño. Este es un tipo simple que toma el tiempo O(n + range) , donde el range es el número total de valores de byte (256) o short / char (65536). El tipo implica asignar una matriz subyacente de valores de range , por lo que solo se usa cuando el número de elementos para ordenar es una fracción significativa del rango total. En particular, se utiliza para matrices de bytes mayores de 29 elementos (es decir, ~ 11% del rango) y matrices cortas / de caracteres mayores de 3200 elementos (~ 5% del rango).
Para las matrices de bytes, siempre se utiliza uno de los dos enfoques anteriores.
Para arreglos int y long encima del umbral de ordenación de inserción y para matrices short / char tanto por encima del umbral de clasificación de inserción como por debajo del umbral de ordenación de recuento, se puede usar uno de dos algoritmos: enlace dinámico doble o clasificación por fusión. El que se utiliza depende de una medida de la ordenación de la matriz: la entrada se divide en series de elementos ascendentes o descendentes. Si el número de dichas ejecuciones es mayor que 66, entonces la matriz se considera en su mayoría sin clasificar y se ordena con una conexión rápida de doble pivote. De lo contrario, la matriz se considera principalmente ordenada, y se usa mergesort (usando las carreras ya enumeradas como punto de partida).

La idea de encontrar carreras y luego usar mergesort para ordenarlas es de hecho muy similar a TimSort, aunque hay algunas diferencias. Por lo tanto, al menos para algunos parámetros, el JDK está utilizando un mergesort con reconocimiento de ejecución, pero para muchas otras combinaciones de parámetros está usando un algoritmo diferente, ¡y se usan al menos 5 algoritmos distintos en total!

Razón fundamental

El razonamiento detrás del comportamiento de ordenación diferente de Object[] frente a primitivo es probablemente al menos doble:

1) Las clases de Object[] deben ser estables : los objetos que se clasifican por igual aparecerán en el mismo orden que la entrada. Para las matrices primitivas, no existe tal concepto: las primitivas están completamente definidas por su valor, por lo que no existe distinción entre una clasificación estable y una inestable. Esto permite que los géneros primitivos prescindan de la necesidad de algoritmos estables a favor de la velocidad.

2) Sorts of Object[] necesita involucrar el método Object.compare() , que puede ser arbitrariamente complejo y costoso. Incluso si el método compare() es simple, generalmente habrá una sobrecarga de llamada de método a menos que todo el método de clasificación pueda estar en línea ² . Por lo tanto, los tipos de Object[] generalmente estarán predispuestos a minimizar las comparaciones totales, incluso a costa de alguna complejidad algorítmica adicional.

Las clases de matrices primitivas, por otro lado, solo comparan directamente valores primitivos que típicamente toman el orden de un ciclo o dos. En este caso, el algoritmo debería optimizarse teniendo en cuenta tanto el costo de las comparaciones como el algoritmo circundante, ya que es probable que sean de la misma magnitud.

⁰ Al menos para las versiones entre Java 7 y Java 9, y por supuesto, esto también incluye el JDK de Oracle ya que está basado en Open JDK. Es probable que otras implementaciones utilicen un enfoque similar, pero no lo he comprobado.

¹ Para las matrices de bytes, el umbral de clasificación de inserción es efectivamente de 29 elementos, ya que es el límite inferior por encima del cual se usa la clasificación de conteo.

² Esto parece poco probable, ya que es bastante grande.

^{3 El} ordenamiento de conteo solo se usa para valores con un rango relativamente limitado de 16 bits o menos: byte , short o char .

Java 7 utiliza Dual-Pivot Quicksort para primitivos y TimSort para objetos.

Según el documento de la API de Java 7 para primitivas:

Nota de implementación: el algoritmo de clasificación es un Quicksort Dual-Pivot de Vladimir Yaroslavskiy, Jon Bentley y Joshua Bloch. Este algoritmo ofrece el rendimiento O (n log (n)) en muchos conjuntos de datos que hacen que otras unidades rápidas se degraden a rendimiento cuadrático, y suele ser más rápido que las implementaciones tradicionales (de un solo pivote) Quicksort.

Según el documento de la API de Java 7 para objetos:

La implementación fue adaptada del tipo de lista de Tim Peters para Python (TimSort). Utiliza técnicas de la "Optimistic Sorting and Information Theoretic Complexity" de Peter McIlroy, en las Actas del Cuarto Simposio Anual ACM-SIAM sobre Algoritmos Discretos, pp 467-474, enero de 1993.

Timsort es una especie híbrida de "tipo de fusión e inserción".

No estoy seguro de si esto es muy diferente de lo que era en Java 6, for Arrays.sort JDK6:

un quicksort ajustado, adaptado de Jon L. Bentley y M. Douglas McIlroy, "Engineering a Sort Function", Software-Practice and Experience, vol. 23 (11) P. 1249-1265 (noviembre de 1993)

Para Objeto [] o colecciones (Collections.sort ()) se utiliza la ordenación por fusión.