Cara tercepat untuk mengurutkan 10 angka? (jumlahnya 32 bit)

211

Saya memecahkan masalah dan itu melibatkan pengurutan 10 angka (int32) dengan sangat cepat. Aplikasi saya perlu mengurutkan 10 angka jutaan kali secepat mungkin. Saya mengambil sampel sekumpulan miliaran elemen dan setiap kali saya harus memilih 10 angka darinya (disederhanakan) dan mengurutkannya (dan membuat kesimpulan dari daftar 10 elemen yang diurutkan).

Saat ini saya menggunakan jenis penyisipan tapi saya membayangkan saya bisa menerapkan algoritma penyortiran khusus yang sangat cepat untuk masalah spesifik saya 10 angka yang akan mengalahkan jenis penyisipan.

Adakah yang tahu cara mendekati masalah ini?

bodacydo
sumber
14
Kedengarannya kasar, serangkaian ifpernyataan bersarang harus bekerja yang terbaik. Hindari loop.
John Alexiou
8
Apakah Anda berharap bahwa angka akan diberikan kepada Anda dengan bias dalam set permutasi, atau akankah mereka didistribusikan secara seragam? Apakah akan ada hubungan antara pemesanan satu daftar dan yang berikutnya?
Douglas Zare
4
Seluruh kumpulan data (dengan miliaran angka) didistribusikan menurut hukum Benford tetapi ketika saya memilih elemen secara acak dari rangkaian ini, mereka tidak lagi (menurut saya).
bodacydo
13
Anda mungkin ingin membaca stackoverflow.com/q/2786899/995714
phuclv
11
Jika Anda memilih secara acak dari miliaran elemen, maka sangat mungkin bahwa latensi untuk menarik data tersebut memiliki dampak yang lebih besar daripada waktu yang diperlukan untuk mengurutkan elemen yang dipilih meskipun seluruh rangkaian data menggunakan RAM. Anda dapat menguji dampaknya dengan membandingkan kinerja dengan memilih data secara berurutan dibandingkan secara acak.
Steve S.

Jawaban:

213

(Menindaklanjuti saran HelloWorld untuk melihat ke jaringan penyortiran.)

Tampaknya jaringan 29-perbandingan / swap adalah cara tercepat untuk melakukan semacam 10-input. Saya menggunakan jaringan yang ditemukan oleh Waksman pada tahun 1969 untuk contoh ini dalam Javascript, yang seharusnya diterjemahkan langsung ke C, karena itu hanya daftar ifpernyataan, perbandingan, dan swap.

function sortNet10(data) {	// ten-input sorting network by Waksman, 1969
    var swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
    return(data);
}

alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));

Berikut ini adalah representasi grafis dari jaringan, dibagi menjadi beberapa fase independen. Untuk memanfaatkan pemrosesan paralel, pengelompokan 5-4-3-4-4-4-3-2 dapat diubah menjadi pengelompokan 4-4-4-4-4-4-3-2.
Jaringan penyortiran 10 input (Waksman, 1969)

10-input sorting network (Waksman, 1969) dikelompokkan ulang

m69 '' snarky and unwelcoming ''
sumber
69
saran; gunakan makro swap. like#define SORTPAIR(data, i1, i2) if (data[i1] > data[i2]) { int swap = data[i1]... }
Peter Cordes
9
Dapatkah secara logis ditunjukkan bahwa ini adalah minimum?
corsiKa
8
@corsiKa Ya, jaringan penyortiran telah menjadi bidang penelitian sejak awal ilmu komputer. Dalam banyak kasus, solusi optimal telah dikenal selama beberapa dekade. Lihat en.wikipedia.org/wiki/Sorting_network
m69 '' snarky and unwelcoming ''
8
Saya membuat Jsperf untuk menguji dan saya dapat mengonfirmasi bahwa Network Sort lebih dari 20 kali lebih cepat daripada sort asli browser. jsperf.com/fastest-10-number-sort
Daniel
9
@Katai Ini akan menghancurkan optimasi apa pun yang mungkin dihasilkan oleh kompiler Anda. Ide buruk. Baca ini untuk informasi lebih lanjut en.wikipedia.org/wiki/…
Antzi
88

Saat Anda menangani ukuran tetap ini, lihat Sorting Networks . Algoritma ini memiliki runtime yang tetap dan independen terhadap inputnya. Untuk kasus penggunaan Anda, Anda tidak memiliki overhead seperti yang memiliki beberapa algoritma penyortiran.

Sortasi Bitonic adalah implementasi dari jaringan tersebut. Yang ini bekerja paling baik dengan len (n) <= 32 pada CPU. Pada input yang lebih besar Anda bisa berpikir untuk pindah ke GPU. https://en.wikipedia.org/wiki/Sorting_network

Btw, halaman yang bagus untuk membandingkan algoritme pengurutan ada di sini (meskipun tidak ada bitonic sort.

http://www.sorting-algorithms.com

Halo Dunia
sumber
3
@ ErickG.Hagstrom Ada banyak solusi; selama mereka menggunakan perbandingan 29, mereka sama-sama efisien. Saya menggunakan solusi Waksman dari tahun 1969; dia rupanya yang pertama menemukan versi perbandingan 29.
m69 '' snarky and unwelcoming ''
1
Ya, @ m69. Ada lebih dari satu juta. Solusi Waksman memiliki panjang 29, dan kedalaman 9. Solusi yang saya tautkan adalah peningkatan di atas dalam dimensi kedalaman: panjang = 29, kedalaman = 8. Tentu saja, ketika diimplementasikan dalam C, kedalaman tidak masalah.
Erick G. Hagstrom
4
@ ErickG.Hagstrom Rupanya ada 87 solusi dengan kedalaman 7, yang pertama ditemukan oleh Knuth pada tahun 1973, tetapi saya belum dapat menemukannya dengan Google cepat. larc.unt.edu/ian/pubs/9-input.pdf (lihat Kesimpulan, hal.14)
m69 '' snarky and unwelcoming ''
4
@ ErickG.Hagstrom: depth mungkin tidak membuat perbedaan "pada level C", tetapi mungkin sekali kompiler dan CPU selesai dengan itu, ada beberapa kemungkinan bahwa itu akan sebagian diparalelkan dalam CPU dan oleh karena itu kedalaman yang lebih kecil dapat membantu. Tergantung pada CPU, tentu saja: beberapa CPU relatif sederhana dan melakukan satu demi satu hal, sedangkan beberapa CPU dapat memiliki beberapa operasi dalam penerbangan, khususnya Anda mungkin mendapatkan kinerja yang sangat berbeda untuk setiap beban dan menyimpan ke tumpukan yang diperlukan dalam Untuk memanipulasi 10 variabel, tergantung bagaimana mereka dilakukan.
Steve Jessop
1
@ ErickG.Hagstrom Itu tidak segera jelas dari kertas oleh Ian Parberry, tetapi jaringan kedalaman-7 memiliki panjang lebih besar dari 29. Lihat Knuth, "Seni Pemrograman Komputer Vol.III", §5.3.4, ara . 49 dan 51.
m69 '' snarky and unwelcoming ''
33

Gunakan jaringan penyortiran yang memiliki perbandingan dalam kelompok 4, sehingga Anda dapat melakukannya di register SIMD. Sepasang instruksi min / maks yang dikemas mengimplementasikan fungsi pembanding yang dikemas. Maaf saya tidak punya waktu sekarang untuk mencari halaman yang saya ingat pernah melihat ini, tetapi mudah-mudahan mencari di jaringan penyortiran SIMD atau SSE akan mengubah sesuatu.

x86 SSE memang memiliki instruksi min dan max integer 32bit-integer untuk vektor empat int 32bit. AVX2 (Haswell dan yang lebih baru) memiliki vektor yang sama tetapi untuk 256b dari 8 int. Ada juga instruksi pengocokan yang efisien.

Jika Anda memiliki banyak jenis kecil yang independen, dimungkinkan untuk melakukan 4 atau 8 jenis secara paralel menggunakan vektor. Esp. jika Anda memilih elemen secara acak (sehingga data yang akan disortir tidak akan bersebelahan dalam memori), Anda dapat menghindari kerutan dan cukup membandingkan dalam urutan yang Anda butuhkan. 10 register untuk menampung semua data dari 4 (AVX2: 8) daftar 10 int masih menyisakan 6 regs untuk ruang awal.

Jaringan sortir vektor kurang efisien jika Anda juga perlu mengurutkan data terkait. Dalam hal itu, cara yang paling efisien tampaknya menggunakan perbandingan-bungkus untuk mendapatkan topeng yang elemennya berubah, dan menggunakan topeng itu untuk mencampur vektor (referensi ke) data terkait.

Peter Cordes
sumber
26

Bagaimana dengan jenis pemilihan yang tidak terbuka, kurang cabang?

#include <iostream>
#include <algorithm>
#include <random>

//return the index of the minimum element in array a
int min(const int * const a) {
  int m = a[0];
  int indx = 0;
  #define TEST(i) (m > a[i]) && (m = a[i], indx = i ); 
  //see http://stackoverflow.com/a/7074042/2140449
  TEST(1);
  TEST(2);
  TEST(3);
  TEST(4);
  TEST(5);
  TEST(6);
  TEST(7);
  TEST(8);
  TEST(9);
  #undef TEST
  return indx;
}

void sort( int * const a ){
  int work[10];
  int indx;
  #define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647; 
  //get the minimum, copy it to work and set it at max_int in a
  GET(0);
  GET(1);
  GET(2);
  GET(3);
  GET(4);
  GET(5);
  GET(6);
  GET(7);
  GET(8);
  GET(9);
  #undef GET
  #define COPY(i) a[i] = work[i];
  //copy back to a
  COPY(0);
  COPY(1);
  COPY(2);
  COPY(3);
  COPY(4);
  COPY(5);
  COPY(6);
  COPY(7);
  COPY(8);
  COPY(9);
  #undef COPY
}

int main() {
  //generating and printing a random array
  int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
  std::random_device rd;
  std::mt19937 g(rd());
  std::shuffle( a, a+10, g);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  }
  std::cout << std::endl;

  //sorting and printing again
  sort(a);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  } 

  return 0;
}

http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6

Satu-satunya garis yang relevan adalah dua yang pertama #define.

Ini menggunakan dua daftar dan sepenuhnya memeriksa kembali yang pertama untuk sepuluh kali yang akan menjadi semacam pemilihan yang diimplementasikan dengan buruk, namun itu menghindari cabang dan loop panjang variabel, yang dapat mengimbangi dengan prosesor modern dan seperangkat data kecil.


Tolok ukur

Saya membandingkan dengan jaringan penyortiran, dan kode saya tampaknya lebih lambat. Namun saya mencoba untuk menghapus membuka gulungan dan salinannya. Menjalankan kode ini:

#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>

int min(const int * const a, int i) {
  int m = a[i];
  int indx = i++;
  for ( ; i<10; i++) 
    //see http://stackoverflow.com/a/7074042/2140449
    (m > a[i]) && (m = a[i], indx = i ); 
  return indx;
}

void sort( int * const a ){
  for (int i = 0; i<9; i++)
    std::swap(a[i], a[min(a,i)]); //search only forward
}


void sortNet10(int * const data) {  // ten-input sorting network by Waksman, 1969
    int swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
}


std::chrono::duration<double> benchmark( void(*func)(int * const), const int seed ) {
  std::mt19937 g(seed);
  int a[10] = {10,11,12,13,14,15,16,17,18,19};
  std::chrono::high_resolution_clock::time_point t1, t2; 
  t1 = std::chrono::high_resolution_clock::now();
  for (long i = 0; i < 1e7; i++) {
    std::shuffle( a, a+10, g);
    func(a);
  }
  t2 = std::chrono::high_resolution_clock::now();
  return std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
}

int main() {
  std::random_device rd;
  for (int i = 0; i < 10; i++) {
    const int seed = rd();
    std::cout << "seed = " << seed << std::endl;
    std::cout << "sortNet10: " << benchmark(sortNet10, seed).count() << std::endl;
    std::cout << "sort:      " << benchmark(sort,      seed).count() << std::endl;
  }
  return 0;
}

Saya secara konsisten mendapatkan hasil yang lebih baik untuk jenis pemilihan kurang cabang dibandingkan dengan jaringan penyortiran.

$ gcc -v
gcc version 5.2.0 (GCC) 
$ g++ -std=c++11 -Ofast sort.cpp && ./a.out
seed = -1727396418
sortNet10: 2.24137
sort:      2.21828
seed = 2003959850
sortNet10: 2.23914
sort:      2.21641
seed = 1994540383
sortNet10: 2.23782
sort:      2.21778
seed = 1258259982
sortNet10: 2.25199
sort:      2.21801
seed = 1821086932
sortNet10: 2.25535
sort:      2.2173
seed = 412262735
sortNet10: 2.24489
sort:      2.21776
seed = 1059795817
sortNet10: 2.29226
sort:      2.21777
seed = -188551272
sortNet10: 2.23803
sort:      2.22996
seed = 1043757247
sortNet10: 2.2503
sort:      2.23604
seed = -268332483
sortNet10: 2.24455
sort:      2.24304
DarioP
sumber
4
Hasilnya tidak terlalu mengesankan, tetapi sebenarnya apa yang saya harapkan. Jaringan sortir meminimalkan perbandingan, bukan swap. Ketika semua nilai sudah ada dalam perbandingan cache jauh lebih murah daripada swap, jadi pilihan sortir (yang meminimalkan jumlah swap) berada di atas angin. (dan tidak ada banyak lagi perbandingan: jaringan dengan 29 perbandingan, hingga 29 swap?; vs. sort seleksi dengan 45 perbandingan dan paling banyak 9 swap)
contoh
7
Oh dan itu memang memiliki cabang - kecuali garis for ( ; i<10; i++) (m > a[i]) && (m = a[i], indx = i ); dioptimalkan dengan sangat baik. (korsleting biasanya merupakan bentuk percabangan)
contoh
1
@EugeneRyabtsev juga, tetapi itu diberi makan dengan urutan acak yang sama sepanjang waktu sehingga harus dibatalkan. Aku mencoba untuk mengubah std::shuffledengan for (int n = 0; n<10; n++) a[n]=g();. Waktu pelaksanaan dibagi dua dan jaringan lebih cepat sekarang.
DarioP
Bagaimana hal ini dibandingkan dengan libc ++ std::sort?
gnzlbg
1
@gnzlbg saya mencoba std::sortjuga tetapi kinerjanya sangat buruk sehingga saya bahkan tidak memasukkannya dalam benchmark. Saya kira dengan set data kecil ada overhead yang cukup.
DarioP
20

Pertanyaannya tidak mengatakan bahwa ini adalah semacam aplikasi berbasis web. Satu hal yang menarik perhatian saya adalah:

Saya mengambil sampel sekumpulan miliaran elemen dan setiap kali saya harus memilih 10 angka darinya (disederhanakan) dan mengurutkannya (dan membuat kesimpulan dari daftar 10 elemen yang diurutkan).

Sebagai seorang insinyur perangkat lunak dan perangkat keras ini benar-benar berteriak "FPGA" kepada saya. Saya tidak tahu kesimpulan apa yang perlu Anda ambil dari kumpulan angka yang diurutkan atau dari mana data berasal tetapi saya tahu hampir sepele untuk memproses di suatu tempat antara seratus juta dan satu miliar dari "sort-and-" ini menganalisis "operasi per detik . Saya telah melakukan pekerjaan sekuensing DNA yang dibantu FPGA di masa lalu. Hampir tidak mungkin untuk mengalahkan kekuatan pemrosesan besar-besaran dari FPGA ketika masalahnya cocok untuk jenis solusi.

Pada tingkat tertentu, satu-satunya faktor pembatas adalah seberapa cepat Anda dapat menyekop data menjadi FPGA dan seberapa cepat Anda bisa mengeluarkannya.

Sebagai referensi, saya merancang prosesor gambar real-time berkinerja tinggi yang menerima data gambar RGB 32 bit dengan kecepatan sekitar 300 juta piksel per detik. Data mengalir melalui filter FIR, pengganda matriks, tabel pencarian, blok deteksi tepi spasial dan sejumlah operasi lainnya sebelum keluar dari ujung lainnya. Semua ini pada Xilinx Virtex2 FPGA yang relatif kecil dengan clocking internal berkisar dari sekitar 33MHz hingga, jika saya ingat dengan benar, 400MHz. Oh, ya, itu juga memiliki implementasi kontroler DDR2 dan menjalankan dua bank memori DDR2.

Sebuah FPGA dapat menghasilkan semacam angka sepuluh 32 bit pada setiap transisi jam saat beroperasi pada ratusan MHz. Akan ada penundaan singkat di awal operasi karena data mengisi pipa pemrosesan. Setelah itu Anda harus bisa mendapatkan satu hasil per jam. Atau lebih jika pemrosesan dapat diparalelkan dengan mereplikasi pipa sort-and-analysis. Solusinya, pada prinsipnya, hampir sepele.

Intinya adalah: Jika aplikasi tidak terikat PC dan aliran data dan pemrosesan "kompatibel" dengan solusi FPGA (baik berdiri sendiri atau sebagai kartu co-prosesor di mesin) tidak ada cara Anda pergi untuk dapat mengalahkan tingkat kinerja yang dapat dicapai dengan perangkat lunak yang ditulis dalam bahasa apa pun, terlepas dari algoritma.

EDIT:

Cukup jalankan pencarian cepat dan temukan kertas yang mungkin berguna bagi Anda. Sepertinya tanggal kembali ke 2012. Anda dapat melakukan BANYAK lebih baik dalam kinerja hari ini (dan bahkan saat itu). Ini dia:

Menyortir Jaringan pada FPGA

martin
sumber
10

Baru-baru ini saya menulis sebuah kelas kecil yang menggunakan algoritma Bose-Nelson untuk menghasilkan jaringan sortir pada waktu kompilasi.

Ini dapat digunakan untuk membuat sort yang sangat cepat untuk 10 angka.

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * \tparam NumElements  The number of elements in the array or container to sort.
 * \tparam T            The element type.
 * \tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * \param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * \param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 10 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    std::cout << "\n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    return 0;
}

Perhatikan bahwa alih-alih if (compare) swappernyataan, kami secara eksplisit memberi kode pada operator ternary untuk min dan maks. Ini untuk membantu mendorong kompiler menggunakan kode branchless.

Tolak ukur

Tolok ukur berikut dikompilasi dengan dentang -O3 dan berjalan pada pertengahan 2012 macbook air saya.

Menyortir data acak

Membandingkannya dengan kode DarioP, berikut adalah jumlah milidetik yang diambil untuk mengurutkan 1 juta array int 32-bit ukuran 10:

Hardcoded Sort Net 10: 88.774 ms
Templated Bose-Nelson sort 10: 27.815 ms

Menggunakan pendekatan templated ini, kita juga dapat menghasilkan jaringan sortir pada waktu kompilasi untuk sejumlah elemen lainnya.

Waktu (dalam milidetik) untuk mengurutkan 1 juta array dari berbagai ukuran.
Jumlah milidetik untuk array ukuran 2, 4, 8 masing-masing adalah 1.943, 8.655, 20.246.
C ++ Pengaturan waktu Static Bose-Nelson Static

Penghargaan untuk Glenn Teitelbaum untuk jenis penyisipan yang tidak gulungan.

Berikut adalah jam rata-rata per sort untuk array kecil dari 6 elemen. Kode dan contoh benchmark dapat ditemukan pada pertanyaan ini:
Jenis tercepat dari array dengan panjang tetap 6 int

Direct call to qsort library function       : 326.81
Naive implementation (insertion sort)       : 132.98
Insertion Sort (Daniel Stutzbach)           : 104.04
Insertion Sort Unrolled                     : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum)  : 81.55
Rank Order                                  : 44.01
Rank Order with registers                   : 42.40
Sorting Networks (Daniel Stutzbach)         : 88.06
Sorting Networks (Paul R)                   : 31.64
Sorting Networks 12 with Fast Swap          : 29.68
Sorting Networks 12 reordered Swap          : 28.61
Reordered Sorting Network w/ fast swap      : 24.63
Templated Sorting Network (this class)      : 25.37

Ia melakukan secepat contoh tercepat dalam pertanyaan untuk 6 elemen.

Kinerja untuk menyortir data yang diurutkan

Seringkali, array input mungkin sudah diurutkan atau sebagian besar diurutkan.
Dalam kasus seperti itu, jenis penyisipan bisa menjadi pilihan yang lebih baik.

masukkan deskripsi gambar di sini

Anda mungkin ingin memilih algoritma pengurutan yang sesuai tergantung pada data.

Kode yang digunakan untuk tolok ukur dapat ditemukan di sini .

Vektor
sumber
Apakah ada peluang Anda dapat menambahkan perbandingan untuk algo saya di bawah?
Glenn Teitelbaum
@GlennTeitelbaum setiap kesempatan Anda menambahkan ini ke tolok ukur Anda dan mengungkapkan cara dan hasil?
greybeard
Kudos untuk menambahkan data pada pengurutan input yang diurutkan.
greybeard
Pada beberapa sistem v1 = v0 < v1 ? v1 : v0; // Maxmasih dapat bercabang, dalam hal ini dapat diganti dengan v1 += v0 - tkarena jika titu v0kemudianv1 + v0 -t == v1 + v0 - v0 == v1 yang lain tadalah v1danv1 + v0 -t == v1 + v0 - v1 == v0
Glenn Teitelbaum
Terner biasanya mengkompilasi ke dalam maxssatau minssinstruksi pada kompiler modern. Tetapi dalam kasus di mana itu tidak berhasil, cara bertukar lainnya dapat digunakan. :)
Diberi vektor
5

Meskipun jenis jaringan memiliki peluang bagus untuk menjadi cepat pada array kecil, kadang-kadang Anda tidak bisa mengalahkan jenis penyisipan jika dioptimalkan dengan benar. Misalnya memasukkan batch dengan 2 elemen:

{
    final int a=in[0]<in[1]?in[0]:in[1];
    final int b=in[0]<in[1]?in[1]:in[0];
    in[0]=a;
    in[1]=b;
}
for(int x=2;x<10;x+=2)
{
    final int a=in[x]<in[x+1]?in[x]:in[x+1];
    final int b=in[x]<in[x+1]?in[x+1]:in[x];
    int y= x-1;

    while(y>=0&&in[y]>b)
    {
        in[y+2]= in[y];
        --y;
    }
    in[y+2]=b;
    while(y>=0&&in[y]>a)
    {
        in[y+1]= in[y];
        --y;
    }
    in[y+1]=a;
}
warren
sumber
Tidak yakin mengapa Anda ulangi in[y+2]= in[y];, salah ketik?
Glenn Teitelbaum
Wow, bagaimana saya melakukan itu? Dan bagaimana seseorang bisa begitu lama memperhatikan? Jawabannya: Ini bukan kesalahan ketik: Saya mengadaptasi algoritma yang berbeda yang memiliki baik kunci dan array nilai.
warren
3

Anda dapat membuka gulungan sepenuhnya insertion sort

Untuk membuatnya lebih mudah, rekursif template s dapat digunakan tanpa overhead fungsi. Karena sudah merupakan template, intbisa menjadi templateparameter juga. Ini juga membuat ukuran array pengkodean selain 10 sepele untuk dibuat.

Perhatikan bahwa untuk mengurutkan int x[10] panggilan adalah insert_sort<int, 9>::sort(x);karena kelas menggunakan indeks dari item terakhir. Ini bisa dibungkus, tetapi itu akan menjadi lebih banyak kode untuk dibaca.

template <class T, int NUM>
class insert_sort;

template <class T>
class insert_sort<T,0>
// stop template recursion
// sorting 1 item is a no-op
{
public:
    static void place(T *x) {}
    static void sort(T * x) {}
};

template <class T, int NUM>
class insert_sort
// use template recursion to do insertion sort
// NUM is the index of the last item, eg. for x[10] call <9>
{
public:
    static void place(T *x)
    {
        T t1=x[NUM-1];
        T t2=x[NUM];
        if (t1 > t2)
        {
            x[NUM-1]=t2;
            x[NUM]=t1;
            insert_sort<T,NUM-1>::place(x);
        }
    }
    static void sort(T * x)
    {
        insert_sort<T,NUM-1>::sort(x); // sort everything before
        place(x);                    // put this item in
    }
};

Dalam pengujian saya ini lebih cepat daripada contoh jaringan penyortiran.

Glenn Teitelbaum
sumber
0

Untuk alasan yang mirip dengan yang saya jelaskan di sini , fungsi penyortiran berikut, sort6_iterator()dan sort10_iterator_local(), harus berkinerja baik, di mana jaringan penyortiran diambil dari sini :

template<class IterType> 
inline void sort10_iterator(IterType it) 
{
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   auto data##a=*(data+a);
#define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b);
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9) 
  SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6) 
  SORT2(4,9) SORT2(0,1) 
  SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8) 
  SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2) 
  SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6) 
  SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5) 
  SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6) 
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Untuk memanggil fungsi ini, saya melewatinya dengan std::vectoriterator.

Matthew K.
sumber
0

Sortasi penyisipan membutuhkan perbandingan rata-rata 29,6 untuk mengurutkan 10 input dengan case terbaik 9 dan terburuk 45 (input yang diberikan dalam urutan terbalik).

Shellsort {9,6,1} akan membutuhkan perbandingan rata-rata 25,5 untuk mengurutkan 10 input. Kasus terbaik adalah 14 perbandingan, terburuk adalah 34 dan menyortir input terbalik memerlukan 22.

Jadi menggunakan shellsort sebagai ganti insertion mengurangi rata-rata case sebesar 14%. Meskipun kasus terbaik meningkat sebesar 56%, kasus terburuk berkurang sebesar 24% yang signifikan dalam aplikasi di mana menjaga kinerja kasus terburuk dalam pemeriksaan adalah penting. Kasus terbalik dikurangi 51%.

Karena Anda sepertinya terbiasa dengan jenis penyisipan, Anda dapat mengimplementasikan algoritma sebagai jaringan penyortiran untuk {9,6} dan kemudian menempelkan jenis penyisipan ({1}) setelah itu:

i[0] with i[9]    // {9}

i[0] with i[6]    // {6}
i[1] with i[7]    // {6}
i[2] with i[8]    // {6}
i[3] with i[9]    // {6}

i[0 ... 9]        // insertion sort
Olof Forshell
sumber