Perbandingan Masa Arrays.sort (Object) dan Arrays.sort (int)

1. Gambaran keseluruhan

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

Pertama, kami akan menerangkan setiap kaedah secara berasingan. Selepas itu, kami akan menulis ujian prestasi untuk mengukur masa berjalannya.

2. Arrays.sort (Objek [])

Sebelum kita melangkah maju, penting untuk diingat bahawa Arrays.sort () berfungsi untuk array jenis primitif dan rujukan.

Arrays.sort (Object []) menerima jenis rujukan .

Sebagai contoh, kami mempunyai pelbagai objek Integer :

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

Untuk menyusun susunan, kita hanya boleh menggunakan:

Arrays.sort(numbers);

Sekarang, susunan nombor mempunyai semua elemennya dalam urutan menaik:

[0, 5, 10, 22]

Arrays.sort (Object []) didasarkan pada algoritma TimSort, memberi kita kerumitan masa O (n log (n)) . Ringkasnya, TimSort menggunakan jenis penyisipan dan algoritma MergeSort. Walau bagaimanapun, ia masih lebih perlahan berbanding dengan algoritma penyortiran lain seperti beberapa pelaksanaan QuickSort.

3. Arrays.sort (int [])

Sebaliknya, Arrays.sort (int []) berfungsi dengan array int primitif .

Begitu juga, kita dapat menentukan susunan primitif int [] :

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

Dan urutkan dengan pelaksanaan Arrays.sort (int []) yang lain . Kali ini, menerima pelbagai primitif:

Arrays.sort(primitives);

Hasil operasi ini tidak akan berbeza dengan contoh sebelumnya. Item dalam susunan primitif akan kelihatan seperti:

[0, 5, 10, 22]

Di bawah tudung, ia menggunakan algoritma Dual-Pivot Quicksort. Pelaksanaan dalamannya dari JDK 10 biasanya lebih pantas daripada Quicksort satu-pivot tradisional.

Algoritma ini menawarkan O (n log (n)) kerumitan masa purata . Itu adalah masa penyortiran purata yang bagus untuk banyak koleksi. Lebih-lebih lagi, ia mempunyai kelebihan untuk berada di tempatnya sepenuhnya, jadi ia tidak memerlukan penyimpanan tambahan.

Walaupun, dalam keadaan terburuk, kerumitan waktunya adalah O (n2) .

4. Perbandingan Masa

Jadi, algoritma mana yang lebih cepat dan mengapa? Mari kita buat teori terlebih dahulu, dan kemudian kita akan menjalankan beberapa ujian konkrit dengan JMH.

4.1. Analisis Kualitatif

Arrays.sort (Object []) biasanya lebih lambat berbanding Arrays.sort (int []) kerana beberapa sebab yang berbeza.

Yang pertama adalah algoritma yang berbeza. QuickSort selalunya lebih pantas daripada Timsort.

Kedua adalah bagaimana setiap kaedah membandingkan nilai.

Lihat, kerana Arrays.sort (Object []) perlu membandingkan satu objek dengan yang lain, ia perlu memanggil kaedah membandingkan elemen setiap elemen . Paling tidak, ini memerlukan pencarian kaedah dan mendorong panggilan ke timbunan di samping apa sahaja operasi perbandingan sebenarnya.

Sebaliknya, Arrays.sort (int []) hanya boleh menggunakan pengendali hubungan primitif seperti < dan > , yang merupakan arahan bytecode tunggal.

4.2. Parameter JMH

Akhirnya, mari kita ketahui kaedah penyortiran yang berjalan lebih pantas dengan data sebenar . Untuk itu, kami akan menggunakan alat JMH (Java Microbenchmark Harness) untuk menulis ujian penanda aras kami.

Oleh itu, kita hanya akan membuat penanda aras yang sangat mudah di sini. Itu tidak menyeluruh tetapi akan memberi kita idea bagaimana kita boleh mendekati membandingkan kaedah menyusun Arrays.sort (int []) dan Arrays.sort ( Integer [] ) .

Di kelas penanda aras 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 masa purata untuk satu operasi ( Mode.AverageTime) dan memaparkan hasil kami dalam milisaat ( TimeUnit.MILLISECONDS) . Selanjutnya, dengan parameter batchSize , kami memberitahu JMH untuk melakukan 100,000 lelaran untuk memastikan hasil kami mempunyai ketepatan yang tinggi.

4.3. Ujian Penanda Aras

Sebelum menjalankan ujian, kita perlu menentukan wadah data yang ingin kita susun:

@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 pilih nombor Integer [] dan susunan primitif int [] elemen primitif. The @State anotasi menunjukkan bahawa pembolehubah diisytiharkan dalam kelas tidak akan menjadi sebahagian daripada menjalankan ujian penanda aras. Walau bagaimanapun, kami kemudian dapat menggunakannya dalam kaedah penanda aras kami.

Sekarang, kami bersedia untuk menambahkan penanda aras mikro pertama untuk Arrays.sort (Integer []) :

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

Seterusnya, untuk Arrays.sort (int []) :

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

4.4. Keputusan ujian

Akhirnya, kami menjalankan ujian dan membandingkan hasilnya:

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

Dari hasilnya, kita dapat melihat bahawa kaedah Arrays.sort (int []) berkinerja lebih baik daripada Arrays.sort (Object []) dalam ujian kami, mungkin atas sebab-sebab sebelumnya yang kami kenal pasti.

Dan walaupun angka nampaknya menyokong teori kami, namun kami perlu melakukan pengujian dengan pelbagai input untuk mendapatkan idea yang lebih baik.

Juga, ingat bahawa nombor yang kami tunjukkan di sini hanyalah hasil penanda aras JMH - jadi kami harus selalu menguji dalam skop sistem dan waktu operasi kami sendiri.

4.5. Mengapa Timsort Kemudian?

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

Dalam artikel ini, kami membandingkan dua kaedah penyortiran yang tersedia di Java: Arrays.sort (int []) dan Arrays.sort ( Integer [] ) . Selain itu, kami membincangkan algoritma penyortiran yang digunakan dalam pelaksanaannya.

Akhirnya, dengan bantuan ujian prestasi penanda aras, kami menunjukkan contoh masa berjalan masing-masingpilihan menyusun.

Seperti biasa, kod lengkap untuk artikel ini terdapat di GitHub.