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?
algorithm
sorting
insertion-sort
sorting-network
bodacydo
sumber
sumber
if
pernyataan bersarang harus bekerja yang terbaik. Hindari loop.Jawaban:
(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
if
pernyataan, perbandingan, dan swap.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.
sumber
#define SORTPAIR(data, i1, i2) if (data[i1] > data[i2]) { int swap = data[i1]... }
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
sumber
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.
sumber
Bagaimana dengan jenis pemilihan yang tidak terbuka, kurang cabang?
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:
Saya secara konsisten mendapatkan hasil yang lebih baik untuk jenis pemilihan kurang cabang dibandingkan dengan jaringan penyortiran.
sumber
for ( ; i<10; i++) (m > a[i]) && (m = a[i], indx = i );
dioptimalkan dengan sangat baik. (korsleting biasanya merupakan bentuk percabangan)std::shuffle
denganfor (int n = 0; n<10; n++) a[n]=g();
. Waktu pelaksanaan dibagi dua dan jaringan lebih cepat sekarang.std::sort
?std::sort
juga tetapi kinerjanya sangat buruk sehingga saya bahkan tidak memasukkannya dalam benchmark. Saya kira dengan set data kecil ada overhead yang cukup.Pertanyaannya tidak mengatakan bahwa ini adalah semacam aplikasi berbasis web. Satu hal yang menarik perhatian saya adalah:
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
sumber
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.
Perhatikan bahwa alih-alih
if (compare) swap
pernyataan, 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.
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
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.
Anda mungkin ingin memilih algoritma pengurutan yang sesuai tergantung pada data.
Kode yang digunakan untuk tolok ukur dapat ditemukan di sini .
sumber
v1 = v0 < v1 ? v1 : v0; // Max
masih dapat bercabang, dalam hal ini dapat diganti denganv1 += v0 - t
karena jikat
ituv0
kemudianv1 + v0 -t == v1 + v0 - v0 == v1
yang laint
adalahv1
danv1 + v0 -t == v1 + v0 - v1 == v0
maxss
atauminss
instruksi pada kompiler modern. Tetapi dalam kasus di mana itu tidak berhasil, cara bertukar lainnya dapat digunakan. :)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:
sumber
in[y+2]= in[y];
, salah ketik?Anda dapat membuka gulungan sepenuhnya
insertion sort
Untuk membuatnya lebih mudah, rekursif
template
s dapat digunakan tanpa overhead fungsi. Karena sudah merupakantemplate
,int
bisa menjaditemplate
parameter juga. Ini juga membuat ukuran array pengkodean selain 10 sepele untuk dibuat.Perhatikan bahwa untuk mengurutkan
int x[10]
panggilan adalahinsert_sort<int, 9>::sort(x);
karena kelas menggunakan indeks dari item terakhir. Ini bisa dibungkus, tetapi itu akan menjadi lebih banyak kode untuk dibaca.Dalam pengujian saya ini lebih cepat daripada contoh jaringan penyortiran.
sumber
Untuk alasan yang mirip dengan yang saya jelaskan di sini , fungsi penyortiran berikut,
sort6_iterator()
dansort10_iterator_local()
, harus berkinerja baik, di mana jaringan penyortiran diambil dari sini :Untuk memanggil fungsi ini, saya melewatinya dengan
std::vector
iterator.sumber
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:
sumber