Mengapa java tidak menggunakan semacam radix pada primitif?

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) diimplementasikan sebagai 'tuned quicksort' daripada jenis radix.

Saya melakukan perbandingan kecepatan beberapa waktu lalu, dan dengan sesuatu seperti n> 10000, jenis radix selalu lebih cepat. Mengapa?

Saya akan berspekulasi bahwa:

• Array.sort diimplementasikan sebagai quicksort, karena quicksort dapat mengurutkan apa pun dalam waktu yang layak diberikan pembanding.
• Menyortir daftar 10.000 entri tidak begitu umum. Mengakses struktur data 10.000 atau lebih elemen agak umum. Jika Anda perlu menjaga ketertiban, pohon pencarian seimbang sering kali merupakan cara yang lebih baik daripada mengurutkan seluruh array Anda setiap kali Anda membutuhkan elemen terkecil.
• Menyortir primitif tidak begitu umum, meskipun apa yang diajarkan universitas.

Intinya adalah, ini bukan kasus penggunaan umum, bahwa optimasi itu perlu di perpustakaan standar. Jika Anda telah menulis aplikasi, yang memiliki masalah kinerja, di mana Anda menentukan melalui profiling bahwa menyortir array 10.000+ int sebenarnya adalah hambatan, maka Anda mungkin juga menulis penyortiran dengan tangan atau mempertimbangkan kembali pilihan struktur data Anda terlebih dahulu. tempat.

Back2dos telah mengatakan semuanya, saya hanya akan mencoba untuk lebih memperjelas poin yang menurut saya paling penting:

Radix sort hanya dapat mengurutkan nilai-nilai primitif aktual yang terkandung dalam array, berdasarkan pada pola digit binernya. Dalam skenario rekayasa perangkat lunak dunia nyata yang sebenarnya, kasus ini hampir tidak pernah ditemukan . Yang cenderung kita lakukan jauh lebih sering adalah mengurutkan array dari struktur data yang lebih kompleks (non-primitif), dan beberapa kali kita mengurutkan array indeks ke entitas lain.

Sekarang, array indeks ke entitas lain sebenarnya adalah array primitif, tetapi urutan sortir disediakan oleh antarmuka komparator (dan / atau delegasi dalam C #) yang membandingkan bukan indeks, tetapi entitas diindeks oleh indeks. Jadi, urutan semacam itu sama sekali tidak ada hubungannya dengan urutan nilai-nilai primitif, dan karena itu urutan radix sama sekali tidak berguna untuk skenario ini.

Sebuah contoh:

Kami memiliki serangkaian string: [0] = "Mike", [1] = "Albert", [2] = "Zoro". Kemudian kami mendeklarasikan array indeks untuk string-string itu: [0] = 0, [1] = 1, [2] = 2. Kemudian, kami mengurutkan susunan indeks, melewatinya pembanding yang tidak membandingkan indeks itu sendiri, tetapi string aktual yang dirujuk oleh indeks ini. Setelah mengurutkan, susunan indeks yang dihasilkan akan terlihat seperti ini: [0] = 1, [1] = 0, [2] = 2. Seperti yang Anda lihat, urutan ini tidak ada hubungannya dengan pola biner dari nilai-nilai yang terkandung dalam array, namun dengan melintasi array indeks ini dan mengambil setiap string yang sesuai, kami mengunjungi string dalam urutan diurutkan.