1. Pengantar penyortiran ember
Bucket Sort adalah algoritma penyortiran berbasis hitungan. Prinsip kerja adalah untuk membagi data menjadi sejumlah ember terbatas, dan kemudian setiap ember diurutkan secara terpisah (dimungkinkan untuk menggunakan algoritma penyortiran lainnya atau terus mengurutkan dengan cara yang berulang). Ketika nilai -nilai dalam data yang akan diurutkan didistribusikan secara merata, kompleksitas waktu penyortiran ember adalah θ (n). Penyortiran bucket berbeda dari penyortiran cepat, ini bukan penyortiran perbandingan, dan tidak terpengaruh oleh batas kompleksitas waktu yang lebih rendah (nlogn).
Penyortiran ember dilakukan dalam 4 langkah berikut:
(1) Tetapkan jumlah tetap ember kosong.
(2) Masukkan data ke dalam ember yang sesuai.
(3) Urutkan data di setiap ember yang tidak kosong.
(4) Sambungkan data dari ember yang tidak kosong untuk mendapatkan hasilnya.
Penyortiran bucket terutama cocok untuk data integer jarak kecil, dan didistribusikan secara independen dan merata. Jumlah data yang dapat dihitung besar dan memenuhi waktu yang diharapkan linier.
2. Demonstrasi algoritma penyortiran ember
Misalnya, sekarang ada satu set data [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]. Bagaimana cara mengurutkannya dari yang kecil ke besar?
Langkah Operasi:
(1) Atur jumlah ember ke 5 ember kosong, temukan nilai maksimum 110 dan nilai minimum 7, dan kisaran setiap ember adalah 20,8 = (110-7+1)/5.
(2) melintasi data asli, masukkan ke dalam ember yang sesuai dengan struktur daftar tertaut. Angka 7, nilai indeks bucket adalah 0, rumus perhitungan adalah lantai ((7 7) / 20.8), angka 36, nilai indeks bucket adalah 1, lantai rumus perhitungan ((36 7) / 20.8).
(3) Saat memasukkan data ke ember dengan indeks yang sama untuk kedua kalinya, tentukan ukuran angka yang ada dan angka yang baru dimasukkan ke dalam ember, dan masukkan mereka agar dari kiri ke kanan, dari kecil ke besar. Sebagai contoh: Ketika ember dengan indeks 2 dimasukkan, ketika memasukkan 63, sudah ada 4 angka 56, 59, 60, dan 65 dalam ember, dan kemudian angka 63 dimasukkan ke kiri 65.
(4) Gabungkan ember yang tidak kosong, gabungkan 0, 1, 2, 3, dan 4 ember di kiri ke kanan.
(5) Dapatkan struktur jenis ember
3. Implementasi Program NodeJS
Tidak sulit untuk mengimplementasikan algoritma matang seperti penyortiran bucket. Menurut ide -ide di atas, saya menulis program sederhana untuk mengimplementasikannya. Saya merasa bahwa bagian yang paling merepotkan adalah menggunakan JavaScript untuk memanipulasi daftar tertaut.
Kode sebenarnya adalah sebagai berikut:
'menggunakan ketat';//////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// Sortir ([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1], 5) * Sortir ([1,4,1,5,3,2,3,3,2,5,2,8,9,1], 5,0,5) */Exports.Sort = Fungsi (ARR, ARR, ARR) {ARR. hitung = hitung || (Hitungan> 1? Hitungan: 10); // menilai nilai maksimum dan minimum var min = arr [0], maks = arr [0]; untuk (var i = 1; i <arr.length; i ++) {min = min <arr [i]? min: arr [i]; max = max> arr [i]? Max: arr [i]; } var delta = (maks - min + 1) / count; // console.log (min+","+max+","+delta); // inisialisasi ember var bucket = []; // data penyimpanan ke ember untuk (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] - min) /delta); // indeks bucket if (bucket [idx]) {// bucket var bucket = bucket [idx]; var insert = false; // masukkan batu bendera l.retraversal (bucket, function (item, done) {if (arr [i] <= item.v) {// lebih kecil dari, masukkan l.append (item, _val (arr [i])); masukkan = true; done (); // Keluar traversal}}); if (! masukkan) {// lebih besar dari, masukkan l.append (bucket, _val (arr [i])); }} else {// bucket kosong var bucket = l.init (); L.Append (Bucket, _val (arr [i])); ember [idx] = ember; // implementasi daftar tautan}} var result = []; untuk (var i = 0, j = 0; i <count; i ++) {l.retraversal (buckets [i], function (item) {// console.log (i+":"+item.v); hasil [j ++] = item.v;}); } return result;} // Daftar Linked Fungsi Objek Penyimpanan _Val (v) {return {v: v}}Jalankan program:
var algo = membutuhkan ('./ index.js'); var data = [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]; Console.log (data); console.log (algo.bucketsort. console.log (algo.bucketsort.sort (data, 10)); // 10 emberKeluaran:
7, 22, 33, 36, 42, 42, 56, 67, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 67, 77, 47, 82, 82, 82, 42, 42, 42, 63, 67, 67, 67, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42. 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 83, 83, 67, 83, 83, 83, 83, 83, 83, 83, 83, 83, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42. 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 56, 56, 59, 64, 63, 63, 63, 63, 67, 67, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 63,
Apa yang perlu dijelaskan adalah:
(1) Urutkan dalam ember dapat diimplementasikan selama proses penyisipan seperti yang dijelaskan dalam program; Atau dapat dimasukkan tanpa menyortir, dan kemudian diurutkan selama proses penggabungan, dan penyortiran cepat dapat dipanggil.
(2) Daftar Tertaut. Dalam API Node yang mendasari, ada implementasi daftar tertaut. Saya tidak menggunakannya secara langsung, tetapi memanggilnya melalui paket LinkList: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4. Kasus: Statistik penyortiran ember pada skor ujian masuk perguruan tinggi
Salah satu skenario aplikasi paling terkenal untuk penyortiran ember adalah menghitung skor ujian masuk perguruan tinggi. Jumlah kandidat ujian masuk perguruan tinggi nasional dalam satu tahun adalah 9 juta, dan skornya adalah standar, dengan minimal 200 dan maksimum 900. Tidak ada desimal. Jika 9 juta angka ini diurutkan, apa yang harus kita lakukan?
Analisis Algoritma:
(1) Jika Anda menggunakan penyortiran berbasis perbandingan, penyortiran cepat, kompleksitas waktu rata-rata adalah O (nlogn) = O (9000000*log9000000) = 144114616 = 144 juta perbandingan.
(2) Jika Anda menggunakan penyortiran berbasis hitungan, penyortiran bucket, dan kompleksitas rata-rata, Anda dapat mengontrol kompleksitas linier. Saat membuat 700 ember, satu ember dari 200 menit hingga 900 menit, O (n) = O (90000000), itu setara dengan memindai data 900W.
Kami menjalankan program untuk membandingkan penyortiran cepat dan bucket sekaligus.
// Buat 100W potongan data di [200.900] interval var data tertutup = algo.data.randomdata (1000*1000.200.900); var S1 = Tanggal baru (). GetTime (); algo.quicksort.sort (data); // cepat sortir var S2 = tanggal baru (). GetTime. Buckets var S3 = Tanggal baru (). GetTime (); Console.log ("Time Quicksort: %SMS", S2-S1); Console.log ("Waktu Bucket: %SMS", S3-S2);Keluaran:
Waktu Quicksort: 14768MSBUCKET Waktu: 1089ms
Oleh karena itu, untuk kasus skor ujian masuk perguruan tinggi, penyortiran ember lebih cocok! Penggunaan algoritma yang sesuai kami dalam skenario yang sesuai akan membawa peningkatan kinerja pada program di luar perangkat keras.
5. Analisis Biaya Penyortiran Bucket
TETAPI...
Penyortiran bucket menggunakan hubungan pemetaan fungsi, mengurangi hampir semua pekerjaan perbandingan. Faktanya, perhitungan nilai f (k) penyortiran ember setara dengan divisi dalam urutan cepat, dan telah membagi sejumlah besar data menjadi blok data yang dipesan pada dasarnya (ember). Maka Anda hanya perlu membuat perbandingan canggih dan menyortir sejumlah kecil data dalam ember.
Kompleksitas waktu penyortiran ember dan kata kunci dibagi menjadi dua bagian:
(1) Looping untuk menghitung fungsi pemetaan bucket dari masing -masing kata kunci, dan kompleksitas kali ini adalah O (n).
(2) Gunakan algoritma penyortiran perbandingan canggih untuk mengurutkan semua data di setiap ember, dengan kompleksitas waktu ∑o (ni*logni). di mana Ni adalah jumlah data dari ember i-th.
Jelas, bagian (2) adalah penentu kinerja penyortiran ember. Meminimalkan jumlah data dalam ember adalah satu -satunya cara untuk meningkatkan efisiensi (karena kompleksitas waktu rata -rata terbaik berdasarkan penyortiran perbandingan hanya dapat mencapai O (n*logn)). Karena itu, kita perlu mencoba yang terbaik untuk melakukan dua poin berikut:
(1) Fungsi pemetaan F (k) dapat mengalokasikan data N untuk m ember secara merata, sehingga setiap ember memiliki volume data [N/M].
(2) Cobalah untuk meningkatkan jumlah barel. Dalam kasus ekstrem, setiap ember hanya bisa mendapatkan satu data, yang sepenuhnya menghindari operasi penyortiran "bandingkan" data dalam ember. Tentu saja, tidak mudah untuk melakukan ini. Ketika jumlah data sangat besar, fungsi F (k) akan membuat jumlah koleksi ember besar dan limbah ruang angkasa serius. Ini adalah trade-off antara biaya waktu dan ruang.
Agar data N dapat diurutkan dan ember, rata -rata kompleksitas waktu penyortiran bucket dari setiap data [N/M] adalah:
O (n)+o (m*(n/m)*log (n/m)) = o (n+n*(logn-logm)) = o (n+n*logn-n*logm)
Ketika n = m, yaitu, ketika hanya ada satu data per ember di bawah batas. Efisiensi terbaik dari penyortiran ember dapat mencapai O (n).
6. Ringkasan
Kompleksitas waktu rata-rata penyortiran ember adalah linier O (n+c), di mana c = n*(logn-logm). Jika jumlah barel M lebih besar relatif terhadap N yang sama, semakin tinggi efisiensinya, dan kompleksitas waktu terbaik mencapai O (n). Tentu saja, kompleksitas ruang penyortiran ember adalah O (n+m). Jika data input sangat besar dan jumlah ember sangat besar, biaya ruang tidak diragukan lagi mahal. Selain itu, jenis bucket stabil.
Sebenarnya, saya memiliki perasaan lain: di antara algoritma pencarian, kompleksitas waktu terbaik dari algoritma pencarian berbasis perbandingan adalah O (LOGN). Misalnya, pencarian setengah akhir, pohon biner seimbang, pohon merah dan hitam, dll. Namun, tabel hash memiliki o (c) efisiensi pencarian level linier (efisiensi pencarian mencapai O (1) jika tidak ada konflik). Mari kita perhatikan dengan baik: apakah pemikiran dan penyortiran ember dari tabel hash lagu yang sama?