Sortasi LSD Bitwise (Radix Sort)

Baru-baru ini menerbitkan banyak artikel tentang berbagai algoritma pengurutan dan perbandingannya, saya memutuskan untuk membuat lima sen saya sendiri.

Saya ingin memberi tahu Anda tentang algoritma favorit saya untuk menyortir LSD bitwise (digit paling signifikan - pertama bit paling signifikan) dengan hitungan (Radix Sort). Algoritma klasik agak dipikirkan kembali oleh penulis ke arah beberapa optimasi dalam mendukung percepatan dan kesederhanaan.

Jadi, penyortiran yang diusulkan berkelanjutan. Kami akan mengurutkan angka integer 32 bit. Untuk bekerja, Anda membutuhkan ~ (n + 4KB) memori tambahan, yang agak boros, tetapi memungkinkan Anda untuk mencapai beberapa peningkatan kinerja.

Dalam LSD jenis ini, perbandingan dan pertukaran tidak digunakan, algoritma ini sepenuhnya linier. Kompleksitas komputasi O (N).

Fitur utama dari algoritma ini adalah efisiensi tinggi untuk kumpulan data yang sangat campuran atau acak. Pada set yang hampir diurutkan, masuk akal untuk menggunakan algoritma lain, karena gain tidak akan begitu signifikan. Ini bekerja buruk pada array kecil, kurang dari beberapa ratus elemen.

Penyortiran dilakukan secara lokal untuk menghemat memori.

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ... 

Kode ini ditulis dalam Pascal, tetapi tidak akan sulit untuk porting ke bahasa apa pun yang nyaman bagi Anda.

Urutan eksekusi terdiri dari dua tahap:

1. Untuk setiap blok (delapan digit biner - 1 byte (nilai optimal)), dengan menghitung, posisinya dalam array baru dihitung.
2. Secara berurutan untuk setiap blok (dari yang paling signifikan ke yang tertinggi), ia bergerak ke posisi yang dihitung sebelumnya.

Perbaikan:

1. Untuk array offset, kami menggunakan perataan dalam memori, dan karena volume kecil itu ditempatkan di L1 - cache prosesor.
2. Array offset diisi segera untuk semua digit, yang memungkinkan Anda untuk berjalan di array untuk menghitung hanya sekali.
3. Perhitungan posisi tidak dimulai dari kepala array, tetapi dari akhir, ini memecahkan dua masalah:
   
   • akhir array pada pass pertama sudah ada dalam cache "warmed", yang dengan array besar memberikan sedikit akselerasi;
   • kedua, siklus menurun ke nol lebih pendek oleh satu instruksi assembler, pada setiap langkah siklus, relatif terhadap siklus naik.
4. Untuk setiap iterasi (dari empat), loop bersarang tidak digunakan, meskipun kurang indah, tetapi beberapa instruksi prosesor lebih disimpan.

Karena kesederhanaannya, kode ini hampir identik dalam kecepatan untuk kompiler 32 dan 64 bit. Jika perlu, mudah untuk membayangkan versi algoritma untuk angka 16 dan 64 bit.

Perbandingan algoritma pengambilan sampel acak dengan penyortiran cepat pada platform 64-bit (rata-rata, masing-masing sepuluh lintasan).



Saran dan komentar tentang optimasi dipersilakan.

Terima kasih