Confronto temporale di Arrays.sort (Object) e Arrays.sort (int)

1. Panoramica

In questo breve tutorial, ci confrontiamo le due Arrays.sort (Object []) e Arrays.sort (int []) operazioni di smistamento .

Innanzitutto, descriveremo ciascun metodo separatamente. Successivamente, scriveremo test delle prestazioni per misurare i loro tempi di esecuzione.

2. Arrays.sort (Object [])

Prima di andare avanti, è importante tenere presente che Arrays.sort () funziona sia per gli array primitivi che per quelli di riferimento.

Arrays.sort (Object []) accetta tipi di riferimento .

Ad esempio, abbiamo un array di oggetti Integer :

Integer[] numbers = {5, 22, 10, 0};

Per ordinare l'array, possiamo semplicemente usare:

Arrays.sort(numbers);

Ora, l'array di numeri ha tutti i suoi elementi in ordine crescente:

[0, 5, 10, 22]

Arrays.sort (Object []) si basa sull'algoritmo TimSort, che ci fornisce una complessità temporale pari a O (n log (n)) . In breve, TimSort utilizza l'ordinamento di inserimento e gli algoritmi MergeSort. Tuttavia, è ancora più lento rispetto ad altri algoritmi di ordinamento come alcune delle implementazioni di QuickSort.

3. Arrays.sort (int [])

D'altra parte, Arrays.sort (int []) funziona con gli array int primitivi .

Allo stesso modo, possiamo definire un array int [] di primitive:

int[] primitives = {5, 22, 10, 0};

E ordinalo con un'altra implementazione di Arrays.sort (int []) . Questa volta, accettando una serie di primitive:

Arrays.sort(primitives);

Il risultato di questa operazione non sarà diverso dall'esempio precedente. E gli elementi nell'array delle primitive avranno il seguente aspetto:

[0, 5, 10, 22]

Sotto il cofano, utilizza un algoritmo Dual-Pivot Quicksort. La sua implementazione interna dal JDK 10 è in genere più veloce del tradizionale Quicksort a un perno.

Questo algoritmo offre una complessità temporale media O (n log (n)) . Questo è un ottimo tempo medio di ordinamento per molte raccolte. Inoltre, ha il vantaggio di essere completamente a posto, quindi non richiede alcuno spazio di archiviazione aggiuntivo.

Tuttavia, nel peggiore dei casi, la sua complessità temporale è O (n2) .

4. Confronto temporale

Allora, quale algoritmo è più veloce e perché? Facciamo prima un po 'di teoria e poi eseguiremo alcuni test concreti con JMH.

4.1. Analisi qualitativa

Arrays.sort (Object []) è in genere più lento rispetto a Arrays.sort (int []) per diversi motivi.

Il primo sono i diversi algoritmi. QuickSort è spesso più veloce di Timsort.

Il secondo è il modo in cui ogni metodo confronta i valori.

Vedete, poiché Arrays.sort (Object []) ha bisogno di confrontare un oggetto con un altro, ha bisogno di chiamare il metodo compareTo di ogni elemento . Per lo meno, ciò richiede una ricerca del metodo e l'inserimento di una chiamata nello stack oltre a qualunque operazione di confronto sia effettivamente.

D'altra parte, Arrays.sort (int []) può semplicemente usare operatori relazionali primitivi come < e > , che sono istruzioni a bytecode singolo.

4.2. Parametri JMH

Infine, scopriamo quale metodo di ordinamento funziona più velocemente con i dati effettivi . Per questo, utilizzeremo lo strumento JMH (Java Microbenchmark Harness) per scrivere i nostri test di benchmark.

Quindi, faremo solo un benchmark molto semplice qui. Non è esaustivo, ma ci darà un'idea di come possiamo affrontare il confronto tra i metodi di ordinamento Arrays.sort (int []) e Arrays.sort ( Integer [] ) .

Nella nostra classe benchmark useremo le annotazioni di configurazione:

@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) @Measurement(batchSize = 100000, iterations = 10) @Warmup(batchSize = 100000, iterations = 10) public class ArraySortBenchmark { }

Qui, vogliamo misurare il tempo medio per una singola operazione ( Mode.AverageTime) e visualizzare i nostri risultati in millisecondi ( TimeUnit.MILLISECONDS) . Inoltre, con il parametro batchSize , stiamo dicendo a JMH di eseguire 100.000 iterazioni per assicurarci che i nostri risultati abbiano un'elevata precisione.

4.3. Test di benchmark

Prima di eseguire i test, dobbiamo definire i contenitori di dati che vogliamo ordinare:

@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}; }

Scegliamo i numeri Integer [] e l' array primitive int [] di elementi primitivi. L' annotazione @State indica che le variabili dichiarate nella classe non faranno parte dell'esecuzione di test di benchmark. Tuttavia, possiamo quindi utilizzarli nei nostri metodi di benchmark.

Ora siamo pronti per aggiungere il primo micro-benchmark per Arrays.sort (Integer []) :

@Benchmark public Integer[] benchmarkArraysIntegerSort(ArraySortBenchmark.Initialize state) { Arrays.sort(state.numbers); return state.numbers; }

Successivamente, per Arrays.sort (int []) :

@Benchmark public int[] benchmarkArraysIntSort(ArraySortBenchmark.Initialize state) { Arrays.sort(state.primitives); return state.primitives; }

4.4. Risultati del test

Infine, eseguiamo i nostri test e confrontiamo i risultati:

Benchmark Mode Cnt Score Error Units benchmarkArraysIntSort      avgt   10  1.095 ± 0.022  ms/op benchmarkArraysIntegerSort  avgt   10  3.858 ± 0.060  ms/op

Dai risultati, possiamo vedere che il metodo Arrays.sort (int []) ha funzionato meglio di Arrays.sort (Object []) nel nostro test, probabilmente per i motivi che abbiamo identificato in precedenza.

E anche se i numeri sembrano supportare la nostra teoria, avremmo bisogno di fare dei test con una maggiore varietà di input per avere un'idea migliore.

Inoltre, tieni presente che i numeri che presentiamo qui sono solo risultati di benchmark JMH , quindi dovremmo sempre testare nell'ambito del nostro sistema e runtime.

4.5. Perché Timsort allora?

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

In questo articolo, abbiamo confrontato due metodi di ordinamento disponibili in Java: Arrays.sort (int []) e Arrays.sort ( Integer [] ) . Inoltre, abbiamo discusso gli algoritmi di ordinamento utilizzati nelle loro implementazioni.

Infine, con l'aiuto dei test delle prestazioni di benchmark, abbiamo mostrato un tempo di esecuzione campione di ciascunoopzione di ordinamento.

Come al solito, il codice completo di questo articolo è disponibile su GitHub.