Perbandingan Waktu dari Arrays.sort (Object) dan Arrays.sort (int)

1. Ikhtisar

Dalam tutorial singkat ini, kita akan membandingkan dua operasi pengurutan Arrays.sort (Object []) dan Arrays.sort (int []) .

Pertama, kami akan menjelaskan setiap metode secara terpisah. Setelah itu, kami akan menulis tes kinerja untuk mengukur waktu berjalannya.

2. Array.sort (Objek [])

Sebelum kita melanjutkan, penting untuk diingat bahwa Arrays.sort () berfungsi untuk array tipe primitif dan referensi.

Arrays.sort (Object []) menerima tipe referensi .

Misalnya, kami memiliki array objek Integer :

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

Untuk mengurutkan array, kita cukup menggunakan:

Arrays.sort(numbers);

Sekarang, larik angka memiliki semua elemennya dalam urutan naik:

[0, 5, 10, 22]

Arrays.sort (Object []) didasarkan pada algoritma TimSort, memberi kita kompleksitas waktu dari O (n log (n)) . Singkatnya, TimSort menggunakan jenis Penyisipan dan algoritma MergeSort. Namun, ini masih lebih lambat dibandingkan dengan algoritme pengurutan lainnya seperti beberapa implementasi QuickSort.

3. Array.sort (int [])

Di sisi lain, Arrays.sort (int []) bekerja dengan array int primitif .

Demikian pula, kita bisa mendefinisikan array int [] primitif:

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

Dan urutkan dengan implementasi lain dari Arrays.sort (int []) . Kali ini, menerima serangkaian primitif:

Arrays.sort(primitives);

Hasil operasi ini tidak akan berbeda dari contoh sebelumnya. Dan item dalam array primitif akan terlihat seperti:

[0, 5, 10, 22]

Di bawah kap, itu menggunakan algoritma Dual-Pivot Quicksort. Implementasi internalnya dari JDK 10 biasanya lebih cepat daripada Quicksort satu pivot tradisional.

Algoritma ini menawarkan kompleksitas waktu rata-rata O (n log (n)) . Itu adalah waktu penyortiran rata-rata yang bagus untuk dimiliki banyak koleksi. Selain itu, ia memiliki keuntungan karena berada pada tempatnya sepenuhnya, sehingga tidak memerlukan penyimpanan tambahan.

Padahal, dalam kasus terburuk, kompleksitas waktunya adalah O (n2) .

4. Perbandingan Waktu

Jadi, algoritma mana yang lebih cepat dan mengapa? Pertama mari kita lakukan beberapa teori, dan kemudian kita akan menjalankan beberapa tes konkret dengan JMH.

4.1. Analisis kualitatif

Arrays.sort (Object []) biasanya lebih lambat dibandingkan dengan Arrays.sort (int []) karena beberapa alasan berbeda.

Yang pertama adalah algoritma yang berbeda. QuickSort seringkali lebih cepat dari Timsort.

Kedua adalah bagaimana setiap metode membandingkan nilai.

Lihat, sejak Arrays.sort (Object []) kebutuhan untuk membandingkan satu objek terhadap yang lain, perlu untuk memanggil setiap elemen ini compareTo metode. Paling tidak, ini memerlukan pencarian metode dan mendorong panggilan ke stack selain operasi perbandingan apa pun yang sebenarnya.

Di sisi lain, Arrays.sort (int []) dapat dengan mudah menggunakan operator relasional primitif seperti < dan > , yang merupakan instruksi bytecode tunggal.

4.2. Parameter JMH

Terakhir, mari cari tahu metode pengurutan mana yang berjalan lebih cepat dengan data aktual . Untuk itu, kami akan menggunakan alat JMH (Java Microbenchmark Harness) untuk menulis pengujian benchmark kami.

Jadi, kami hanya akan melakukan benchmark yang sangat sederhana di sini. Ini tidak komprehensif tetapi akan memberi kita gambaran tentang bagaimana kita dapat mendekati membandingkan Arrays.sort (int []) dan Arrays.sort ( Integer [] ) metode pengurutan.

Di kelas benchmark kami, kami akan menggunakan anotasi konfigurasi:

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

Di sini, kami ingin mengukur waktu rata-rata untuk satu operasi ( Mode.AverageTime) dan menampilkan hasil kami dalam milidetik ( TimeUnit.MILLISECONDS) . Selain itu, dengan parameter batchSize , kami memberi tahu JMH untuk melakukan 100.000 iterasi untuk memastikan hasil kami memiliki presisi tinggi.

4.3. Tes Tolok Ukur

Sebelum menjalankan tes, kita perlu mendefinisikan wadah data yang ingin kita urutkan:

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

Mari kita pilih bilangan Integer [] dan array primitif int [] dari elemen primitif. The @State penjelasan menunjukkan bahwa variabel yang dideklarasikan di kelas tidak akan menjadi bagian dari menjalankan tes benchmark. Namun, kami kemudian dapat menggunakannya dalam metode benchmark kami.

Now, we're ready to add the first micro-benchmark for Arrays.sort(Integer[]):

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

Next, for Arrays.sort(int[]):

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

4.4. Test Results

Finally, we run our tests and compare the results:

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

From the results, we can see that Arrays.sort(int[]) method performed better than to Arrays.sort(Object[])in our test, likely for the earlier reasons we identified.

And even though the numbers appear to support our theory, though we'd need to do testing with a greater variety of inputs to get a better idea.

Also, keep in mind that the numbers we present here are just JMH benchmark results – so we should always test in the scope of our own system and runtime.

4.5. Why Timsort Then?

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

Pada artikel ini, kami membandingkan dua metode pengurutan yang tersedia di Java: Arrays.sort (int []) dan Arrays.sort ( Integer [] ) . Selain itu, kami membahas algoritme pengurutan yang digunakan dalam penerapannya.

Akhirnya, dengan bantuan tes kinerja benchmark, kami menunjukkan contoh run time masing-masingopsi penyortiran.

Seperti biasa, kode lengkap untuk artikel ini tersedia di GitHub.