1. Información general
En este rápido tutorial, vamos a comparar las dos Arrays.sort (Object []) y Arrays.sort (int []) operaciones de clasificación .
Primero, describiremos cada método por separado. Después de eso, escribiremos pruebas de rendimiento para medir sus tiempos de ejecución.
2. Arrays.sort (Objeto [])
Antes de seguir adelante, es importante tener en cuenta que Arrays.sort () funciona tanto para matrices de tipo primitivo como de referencia.
Arrays.sort (Object []) acepta tipos de referencia .
Por ejemplo, tenemos una matriz de objetos Integer :
Integer[] numbers = {5, 22, 10, 0};Para ordenar la matriz, simplemente podemos usar:
Arrays.sort(numbers);Ahora, la matriz de números tiene todos sus elementos en orden ascendente:
[0, 5, 10, 22]Arrays.sort (Object []) se basa en el algoritmo TimSort, lo que nos da una complejidad de tiempo de O (n log (n)) . En resumen, TimSort hace uso de la ordenación por inserción y los algoritmos MergeSort. Sin embargo, sigue siendo más lento en comparación con otros algoritmos de clasificación como algunas de las implementaciones de QuickSort.
3. Arrays.sort (int [])
Por otro lado, Arrays.sort (int []) trabaja con matrices int primitivas .
De manera similar, podemos definir una matriz int [] de primitivas:
int[] primitives = {5, 22, 10, 0};Y ordénelo con otra implementación de Arrays.sort (int []) . Esta vez, aceptando una serie de primitivas:
Arrays.sort(primitives);El resultado de esta operación no será diferente del ejemplo anterior. Y los elementos de la matriz de primitivas se verán así:
[0, 5, 10, 22]Debajo del capó, utiliza un algoritmo de ordenación rápida de doble pivote. Su implementación interna desde el JDK 10 suele ser más rápida que el Quicksort tradicional de un pivote.
Este algoritmo ofrece una complejidad de tiempo promedio O (n log (n)) . Ese es un gran tiempo de clasificación promedio para muchas colecciones. Además, tiene la ventaja de estar completamente en su lugar, por lo que no requiere almacenamiento adicional.
Aunque, en el peor de los casos, su complejidad temporal es O (n2) .
4. Comparación de tiempos
Entonces, ¿qué algoritmo es más rápido y por qué? Primero hagamos algo de teoría, y luego haremos algunas pruebas concretas con JMH.
4.1. Analisis cualitativo
Arrays.sort (Object []) suele ser más lento en comparación con Arrays.sort (int []) por varias razones diferentes.
El primero son los diferentes algoritmos. QuickSort suele ser más rápido que Timsort.
El segundo es cómo cada método compara los valores.
Vea, dado que Arrays.sort (Object []) necesita comparar un objeto con otro, necesita llamar al método compareTo de cada elemento . Como mínimo, esto requiere una búsqueda de método y empujar una llamada a la pila además de lo que sea realmente la operación de comparación.
Por otro lado, Arrays.sort (int []) puede simplemente usar operadores relacionales primitivos como < y > , que son instrucciones de código de un solo byte.
4.2. Parámetros JMH
Finalmente, averigüemos qué método de clasificación se ejecuta más rápido con los datos reales . Para eso, usaremos la herramienta JMH (Java Microbenchmark Harness) para escribir nuestras pruebas de referencia.
Entonces, vamos a hacer aquí un punto de referencia muy simple. No es exhaustivo, pero nos dará una idea de cómo podemos abordar la comparación de los métodos de clasificación Arrays.sort (int []) y Arrays.sort ( Integer [] ) .
En nuestra clase de referencia usaremos anotaciones de configuración:
@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Measurement(batchSize = 100000, iterations = 10) @Warmup(batchSize = 100000, iterations = 10) public class ArraySortBenchmark { }Aquí, queremos medir el tiempo promedio para una sola operación ( Mode.AverageTime) y mostrar nuestros resultados en milisegundos ( TimeUnit.MILLISECONDS) . Además, con el parámetro batchSize , le decimos a JMH que realice 100.000 iteraciones para asegurarnos de que nuestros resultados tengan una alta precisión.
4.3. Pruebas comparativas
Antes de ejecutar las pruebas, necesitamos definir los contenedores de datos que queremos ordenar:
@State(Scope.Thread) public static class Initialize { Integer[] numbers = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167 }; int[] primitives = {-769214442, -1283881723, 1504158300, -1260321086, -1800976432, 1278262737, 1863224321, 1895424914, 2062768552, -1051922993, 751605209, -1500919212, 2094856518, -1014488489, -931226326, -1677121986, -2080561705, 562424208, -1233745158, 41308167}; }Vamos a elegir los números enteros [] y la int [] primitivas conjunto de elementos primitivos. La anotación @State indica que las variables declaradas en la clase no serán parte de la ejecución de pruebas comparativas. Sin embargo, luego podemos usarlos en nuestros métodos de referencia.
Ahora, estamos listos para agregar el primer micro-benchmark para Arrays.sort (Integer []) :
@Benchmark public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) { Arrays.sort(state.numbers); return state.numbers; }A continuación, para Arrays.sort (int []) :
@Benchmark public int[] benchmarkArraysIntSort(ArraySortBenchmark.Initialize state) { Arrays.sort(state.primitives); return state.primitives; }4.4. Resultados de la prueba
Finalmente, ejecutamos nuestras pruebas y comparamos los resultados:
Benchmark Mode Cnt Score Error Units benchmarkArraysIntSort avgt 10 1.095 ± 0.022 ms/op benchmarkArraysIntegerSort avgt 10 3.858 ± 0.060 ms/opDe los resultados, podemos ver que el método Arrays.sort (int []) funcionó mejor que Arrays.sort (Object []) en nuestra prueba, probablemente por las razones anteriores que identificamos.
Y aunque los números parecen respaldar nuestra teoría, necesitaríamos hacer pruebas con una mayor variedad de entradas para tener una mejor idea.
Además, tenga en cuenta que los números que presentamos aquí son solo resultados de referencia de JMH , por lo que siempre debemos probar en el alcance de nuestro propio sistema y tiempo de ejecución.
4.5. ¿Por qué Timsort entonces?
We should probably ask ourselves a question, then. If QuickSort is faster, why not use it for both implementations?
See, QuickSort isn't stable, so we can't use it to sort Objects. Basically, if two ints are equal, it doesn't matter that their relative order stays the same since one 2 is no different from another 2. With objects though, we can sort by one attribute and then another, making the starting order matter.
5. Conclusion
En este artículo, comparamos dos métodos de clasificación disponibles en Java: Arrays.sort (int []) y Arrays.sort ( Integer [] ) . Además, discutimos los algoritmos de clasificación utilizados en sus implementaciones.
Finalmente, con la ayuda de las pruebas de rendimiento de referencia, mostramos un tiempo de ejecución de muestra de cadaopción de clasificación.
Como de costumbre, el código completo de este artículo está disponible en GitHub.