Mengapa Radix Sort tidak digunakan lebih sering?

Ini stabil dan memiliki kompleksitas waktu O (n). Seharusnya lebih cepat daripada algoritma seperti Quicksort dan Mergesort, namun saya jarang melihatnya menggunakannya.

Tidak seperti radix sort, quicksort bersifat universal, sedangkan radix sort hanya berguna untuk memperbaiki kunci integer panjang.

Anda juga harus mengerti, bahwa O (f (n)) benar-benar berarti dalam urutan K * f (n), di mana K adalah konstanta arbitrer. Untuk radix sort K ini cukup besar (setidaknya urutan jumlah bit dalam integer yang diurutkan), di sisi lain quicksort memiliki salah satu K terendah di antara semua algoritma pengurutan dan kompleksitas rata-rata n * log (n). Jadi dalam skenario kehidupan nyata quicksort akan sangat sering lebih cepat daripada jenis radix.

Sebagian besar algoritma penyortiran adalah untuk tujuan umum. Diberikan fungsi perbandingan, mereka bekerja pada apa saja, dan algoritma seperti Quicksort dan Heapsort akan mengurutkan dengan O (1) memori tambahan.

Penyortiran radix lebih terspesialisasi. Anda memerlukan kunci khusus yang berada dalam urutan leksikografis. Anda perlu satu ember untuk setiap simbol yang mungkin ada di kunci, dan ember harus menyimpan banyak catatan. (Secara bergantian, Anda membutuhkan satu set besar ember yang akan menampung setiap nilai kunci yang mungkin.) Anda cenderung membutuhkan lebih banyak memori untuk melakukan radix sort, dan Anda akan menggunakannya secara acak. Tidak satu pun dari ini baik untuk komputer modern, karena Anda kemungkinan akan mendapatkan kesalahan halaman seperti Quicksort akan mendapatkan cache miss.

Akhirnya, orang-orang pada umumnya tidak menulis algoritma sorting mereka sendiri lagi. Sebagian besar bahasa memiliki fasilitas perpustakaan untuk disortir, dan hal yang benar untuk dilakukan adalah menggunakannya. Karena radix sort tidak dapat diterapkan secara universal, biasanya harus disesuaikan dengan penggunaan aktual, dan menggunakan banyak memori tambahan, sulit untuk memasukkannya ke fungsi pustaka atau templat.

Sangat jarang bahwa kunci yang Anda sortir sebenarnya adalah bilangan bulat dalam rentang yang dikenal dan jarang. Biasanya Anda memiliki bidang abjad, yang terlihat seperti mereka akan mendukung penyortiran non-komparatif, tetapi karena string dunia nyata tidak terdistribusi secara merata di seluruh alfabet, ini tidak bekerja sebagai baik sebagaimana mestinya dalam teori.

Di lain waktu, kriteria didefinisikan hanya secara operasional (diberikan dua catatan, Anda dapat memutuskan mana yang lebih dulu, tetapi Anda tidak dapat menilai seberapa jauh 'skala' dari catatan yang terisolasi itu). Jadi metode ini sering tidak berlaku, kurang berlaku dari yang Anda yakini, atau tidak lebih cepat dari O (n * log (n)).

Saya menggunakannya sepanjang waktu, sebenarnya lebih dari jenis berbasis perbandingan, tapi saya diakui orang aneh yang bekerja lebih banyak dengan angka daripada yang lain (saya hampir tidak pernah bekerja dengan string, dan mereka umumnya diinternir jika demikian pada titik mana radix pengurutan dapat berguna lagi untuk memfilter duplikat dan menghitung set persimpangan; Saya praktis tidak pernah melakukan perbandingan leksikografis).

Contoh dasar adalah titik penyortiran radix oleh dimensi yang diberikan sebagai bagian dari pencarian atau median split atau cara cepat untuk mendeteksi titik bertepatan, fragmen penyortiran kedalaman, atau penyortiran radix array indeks yang digunakan dalam banyak loop untuk memberikan akses yang lebih ramah terhadap cache pola (tidak bolak-balik dalam memori hanya untuk kembali lagi dan memuat kembali memori yang sama ke dalam garis cache). Ada aplikasi yang sangat luas setidaknya di domain saya (grafik komputer) hanya untuk mengurutkan pada tombol numerik 32-bit dan 64-bit berukuran tetap.

Satu hal yang ingin saya sampaikan dan katakan adalah bahwa radix sort dapat bekerja pada angka floating-point dan negatif, meskipun sulit untuk menulis versi FP yang se portable mungkin. Juga saat O (n * K), K hanya harus menjadi jumlah byte dari ukuran kunci (mis: sejuta bilangan bulat 32-bit biasanya akan mengambil lintasan berukuran 4 byte jika ada 2 ^ 8 entri dalam bucket ). Pola akses memori juga cenderung jauh lebih ramah-cache daripada quicksort meskipun itu membutuhkan array paralel dan array ember kecil biasanya (yang kedua biasanya dapat masuk dengan baik pada stack). QS mungkin melakukan 50 juta swap untuk mengurutkan array sejuta bilangan bulat dengan pola akses acak sporadis. Urutan radix dapat melakukan itu dalam 4 linier, cache-friendly melewati data.

Namun, kurangnya kesadaran untuk dapat melakukan ini dengan K kecil, pada bilangan negatif bersama dengan floating-point, mungkin sangat berkontribusi signifikan terhadap kurangnya popularitas jenis radix.

Adapun pendapat saya tentang mengapa orang tidak menggunakannya lebih sering, mungkin ada hubungannya dengan banyak domain yang umumnya tidak memiliki kebutuhan untuk mengurutkan angka atau menggunakannya sebagai kunci pencarian. Namun, hanya berdasarkan pengalaman pribadi saya, banyak mantan rekan kerja saya juga tidak menggunakannya dalam kasus-kasus di mana itu sangat cocok, dan sebagian karena mereka tidak sadar bahwa itu dapat dilakukan untuk bekerja pada FP dan negatif. Jadi selain itu hanya bekerja pada jenis numerik, sering dianggap lebih umum berlaku daripada yang sebenarnya. Saya tidak akan memiliki banyak gunanya jika saya pikir itu tidak bekerja pada angka floating-point dan bilangan bulat negatif.

Beberapa tolok ukur:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

Dan itu hanya dengan implementasi naif saya ( mt_sort_intjuga penyortiran radix tetapi dengan cabang kode yang lebih cepat mengingat dapat menganggap kuncinya adalah integer). Bayangkan seberapa cepat implementasi standar yang ditulis oleh para ahli mungkin.

Satu-satunya kasus di mana saya menemukan jenis radix lebih buruk daripada perbandingan berbasis C ++ yang sangat cepat std::sortadalah untuk sejumlah kecil elemen, katakanlah 32, pada titik mana saya percaya std::sortmulai menggunakan jenis yang lebih cocok untuk sejumlah kecil elemen seperti heapsort atau jenis penyisipan, meskipun pada saat itu implementasi saya hanya menggunakan std::sort.

Satu lagi alasan: Penyortiran hari-hari ini biasanya diimplementasikan dengan rutin penyortiran yang disediakan oleh pengguna yang dilampirkan pada logika penyortiran yang disediakan oleh kompiler. Dengan radix sort, ini akan menjadi jauh lebih kompleks dan semakin buruk ketika rutin sortir bekerja pada beberapa kunci dengan panjang variabel. (Katakan, nama, dan tanggal lahir.)

Di dunia nyata saya benar-benar telah menerapkan jenis radix sekali. Ini adalah masa lalu ketika memori terbatas, saya tidak bisa membawa semua data saya ke memori sekaligus. Itu berarti bahwa jumlah akses ke data jauh lebih penting daripada O (n) vs O (n log n). Saya membuat satu lintasan melintasi data yang mengalokasikan setiap catatan ke nampan (dengan daftar yang berisi catatan di mana nampan, tidak benar-benar memindahkan apa pun.) Untuk setiap nampan kosong (kunci pengurutan saya adalah teks, akan ada banyak bins kosong) Saya memeriksa apakah saya benar-benar bisa membawa data ke dalam memori - jika ya, bawa dan gunakan quicksort. Jika tidak, buat file temp yang hanya berisi item dalam nampan dan panggil rutinnya secara rekursif. (Dalam praktiknya, beberapa tempat sampah akan meluap.) Ini menyebabkan dua pembacaan lengkap dan satu penulisan lengkap untuk penyimpanan jaringan dan sekitar 10% dari ini untuk penyimpanan lokal.

Saat ini masalah big-data seperti itu jauh lebih sulit untuk dihadapi, saya mungkin tidak akan pernah menulis hal seperti itu lagi. (Jika saya dihadapkan dengan data yang sama hari ini saya hanya akan menentukan OS 64-bit, tambahkan RAM jika Anda meronta-ronta di editor itu.)

Jika semua parameter Anda adalah bilangan bulat dan jika Anda memiliki lebih dari 1024 parameter input, maka jenis radix selalu lebih cepat.

Mengapa?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

Jadi radix sort lebih cepat ketika

log(n)> max num of digits

Bilangan bulat maks di Jawa adalah 2147483647. Panjangnya 10 digit

Jadi radix sort selalu lebih cepat kapan

log(n)> 10

Oleh karena itu jenis radix selalu lebih cepat ketika n>1024