Pertanyaan Mengapa Collections.sort menggunakan gabungan semacam alih-alih quicksort? [Tutup]


Kita tahu bahwa quick sort adalah algoritma pengurutan tercepat.

Collections.sort digunakan menggabungkan algoritma sortir alih-alih semacam cepat. Tapi Arrays.sort menggunakan sortir cepat.

Apa alasan Collections.sort menggunakan gabungan semacam alih-alih cepat?


76
2018-03-01 09:12


asal


Jawaban:


Sangat mungkin dari Josh Bloch §:

Saya memang menulis metode ini, jadi saya kira saya memenuhi syarat untuk menjawab. ini   benar bahwa tidak ada algoritma penyortiran tunggal terbaik. QuickSort memiliki   dua defisiensi utama jika dibandingkan dengan mergesort:

  1. Ini tidak stabil (seperti dicatat parsifal).

  2. Tidak menjamin n kinerja n log; itu dapat menurunkan ke kinerja kuadrat pada input patologis.

Stabilitas bukanlah masalah untuk tipe primitif, karena tidak ada gagasan tentang   identitas sebagai berbeda dari (nilai) kesetaraan. Dan kemungkinan   Perilaku kuadrat dianggap tidak menjadi masalah dalam prakteknya   Implementasi Bentely dan McIlroy (atau selanjutnya untuk Pivot Ganda   Quicksort), itulah sebabnya mengapa varian QuickSort ini digunakan untuk   jenis primitif.

Stabilitas adalah masalah besar ketika menyortir objek sewenang-wenang. Sebagai contoh,   misalkan Anda memiliki objek yang mewakili pesan email, dan Anda mengurutkan   mereka terlebih dahulu berdasarkan tanggal, kemudian oleh pengirim. Anda mengharapkan mereka diurutkan berdasarkan   tanggal dalam setiap pengirim, tetapi itu hanya akan benar jika semacam itu   stabil. Itu sebabnya kami memilih untuk menyediakan semacam stabil (Merge Sort)   untuk mengurutkan referensi objek. (Secara teknis berbicara, beberapa berurutan   jenis stabil menghasilkan pemesanan leksikografi pada tombol di   urutan terbalik semacam itu: jenis terakhir yang paling menentukan   subkunci yang signifikan.)

Ini adalah manfaat sampingan yang bagus yang Merge Sort jaminan n log n (waktu)   kinerja tidak peduli apa pun inputnya. Tentu saja ada sisi bawah:   semacam cepat adalah "di tempat" semacam: itu hanya memerlukan kembali log n ruang eksternal   (untuk mempertahankan panggilan stack). Gabungkan, sortir, di sisi lain,   membutuhkan O (n) ruang eksternal. Varian TimSort (diperkenalkan di Java   SE 6) membutuhkan ruang yang jauh lebih sedikit (O (k)) jika array input   hampir disortir.

Juga berikut relevan:

Algoritma yang digunakan oleh java.util.Arrays.sort dan (secara tidak langsung) oleh   java.util.Collections.sort untuk mengurutkan referensi objek adalah "diubah   mergesort (di mana gabungan dihilangkan jika elemen tertinggi dalam   sublist rendah kurang dari elemen terendah dalam sublist tinggi). "Ini   adalah semacam stabil yang cukup cepat yang menjamin O (n log n)   kinerja dan membutuhkan O (n) ruang ekstra. Pada zamannya (itu ditulis   pada tahun 1997 oleh Joshua Bloch), itu adalah pilihan yang bagus, tetapi hari ini tetapi kita bisa   lakukan jauh lebih baik.

Sejak 2003, daftar semacam Python telah menggunakan algoritma yang dikenal sebagai timsort   (Setelah Tim Peters, siapa yang menulisnya). Ini adalah stabil, adaptif, iteratif   mergesort yang membutuhkan jauh lebih sedikit dari n log (n) perbandingan kapan   berjalan pada array yang sebagian disortir, sambil menawarkan kinerja   sebanding dengan mergesort tradisional ketika dijalankan pada array acak. Seperti   semua mergesorts timsort yang tepat stabil dan berjalan dalam waktu O (n log n)   (kasus terburuk). Dalam kasus terburuk, timsort membutuhkan penyimpanan sementara   ruang untuk referensi objek n / 2; dalam kasus terbaik, hanya membutuhkan a   jumlah ruang konstan kecil. Bandingkan ini dengan arus   implementasi, yang selalu membutuhkan ruang ekstra untuk n objek   referensi, dan mengalahkan n log n hanya pada daftar hampir disortir.

Timsort dijelaskan secara rinci di sini:    http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

Implementasi asli Tim Peters ditulis dalam C. Joshua Bloch   memindahkannya dari C ke Java dan mengakhiri pengujian, benchmark, dan menyetel   menghasilkan kode secara ekstensif. Kode yang dihasilkan adalah drop-in   pengganti java.util.Arrays.sort. Pada data yang sangat teratur, ini   kode dapat berjalan hingga 25 kali lebih cepat dari implementasi saat ini (aktif   server HotSpot VM). Pada data acak, kecepatan yang lama dan baru   implementasi sebanding. Untuk daftar yang sangat pendek, yang baru   implementasi secara substansial lebih cepat daripada yang lama bahkan secara acak   data (karena menghindari penyalinan data yang tidak perlu).

Juga, lihat Apakah Java 7 menggunakan Tim Sortir untuk Method Arrays.Sort?.

Tidak ada satu pun pilihan "terbaik". Seperti banyak hal lainnya, ini tentang pengorbanan.


156
2018-03-01 09:20