Dan lebih banyak tentang macam-macam

Saya berani mengangkat topik ini lagi. Saya akan mulai dengan tautan ke artikel oleh Mikhail Opanasenko (oms7) , yang sangat mengesankan dalam hal jumlah pekerjaan yang dilakukan, serta dalam jumlah tautan yang dikutip. Dia mulai menyiapkan materi, tidak tahu tentang publikasi ini, yang kemudian, setelah sosialisasi, menyebabkan perlunya pemrosesan substansial. Bagi mereka yang sudah membaca artikel ini, saya memberitahu Anda bahwa dalam materi saya, lebih banyak jenis data yang dipelajari, khususnya, string dan bilangan real, perpustakaan boost dan bsd digunakan, dan beberapa topik lain yang hilang dari artikel disebutkan.

Ada puluhan cara berbeda untuk mengatur item data secara berurutan. Di antara mereka, ada yang bekerja cepat, sehingga, misalnya, mereka dapat mengurutkan setiap array data yang terletak di RAM komputer dalam maksimum menit. Lebih khusus lagi, dapat dikatakan bahwa penyortiran cepat mengatur satu miliar bilangan bulat dalam komputer pribadi modern yang bagus dalam waktu kurang dari seratus detik. Jika Anda menggunakan metode primitif, non-cepat, misalnya, penyortiran gelembung atau penyortiran seleksi, untuk menyortir sejumlah besar elemen, maka waktu yang dihabiskan untuk pemrosesan data tersebut dapat melebihi harapan apa pun - "pemrosesan" tersebut sebenarnya dapat memakan waktu beberapa hari, minggu, dan bahkan bertahun-tahun. Perbedaan besar ini disebabkan oleh fakta bahwa waktu penyortiran dengan metode cepat memakan waktu sekitar sebanding dengan N log N , dan primitif - N ² . Dengan meningkatnya N, perbedaan antara dua nilai menjadi sangat nyata. Oleh karena itu, masuk akal untuk menggunakan metode primitif hanya untuk bekerja dengan data kecil, misalnya, pada komputer modern, hingga beberapa ribu elemen. Adalah wajar untuk menggunakannya untuk mengajarkan dasar-dasar pemrograman dan pemikiran logis, karena mereka jauh lebih sederhana daripada metode cepat.

Saya ingin memahami metode penyortiran yang ada di perpustakaan standar saat ini. Cari tahu seberapa besar perbedaan di antara mereka dalam hal karakteristik utama mereka, kecepatan kerja, dan juga fitur karakteristik mereka. Selain itu, kami akan mempertimbangkan sepanjang jalan untuk perbandingan dan latihan untuk pikiran beberapa metode yang tidak sulit untuk diterapkan. Perlu juga dicatat bahwa optimizer dari kompiler GCC dan mungkin kompiler bagus lainnya bekerja dengan sangat baik, mempercepat kode beberapa kali (kadang-kadang bahkan lebih dari 5 kali).

Mari kita mulai dengan metode semacam gelembung sebagai yang paling sederhana dan paling lambat. Menurut metode ini, Anda harus melalui array data berulang kali, membandingkan elemen tetangga dan mengubah tempat mereka jika urutan di antara mereka rusak. Setelah setiap pass, setidaknya satu elemen (terbesar atau terkecil - tergantung pada urutan yang dipilih) ada di tempatnya. Selain kesederhanaan, metode ini memiliki satu keunggulan lagi, tidak memerlukan memori tambahan. Satu lagi fitur metode gelembung dapat dicatat - ia sangat cepat memproses data yang sudah dipesan dan dalam beberapa kasus menjadikannya salah satu metode tercepat. Jika data hanya dipesan sebagian, maka metode ini bekerja lebih cepat dengan mereka, tetapi dalam kebanyakan kasus hanya sangat sedikit. Untuk tes, saya menggunakan implementasi berikut.

Metode lambat lainnya adalah pemilihan jenis. Di sini, pada setiap pass, elemen terbesar dan terkecil dalam data pertama kali ditemukan dan kemudian elemen-elemen ini ditempatkan di posisi ekstrem sesuai dengan urutan yang dipilih. Pada langkah selanjutnya, kami mengurutkan data tanpa elemen ekstrim ini. Metode ini sesederhana bubble sorting, dan juga tidak membutuhkan memori tambahan, tetapi terasa lebih cepat. Selain itu, pengurutan dengan metode ini melakukan pencatatan jumlah minimum permutasi elemen data. Oleh karena itu, ketika permutasi jauh lebih lambat daripada perbandingan, pemesanan dengan metode seleksi dapat diterima jika jumlah elemen data kecil. Ini implementasi saya. Lebih sering penyortiran ini disadari, menempatkan hanya satu elemen per pass. Heap sorting (atau piramidal), yang akan didiskusikan nanti, adalah versi yang paling canggih dari sorting yang dimaksud.

Kode untuk metode terakhir yang dianggap lambat, jenis penyisipan, mungkin merupakan kode terpendek dari semua kode yang menerapkan jenis, jadi metode ini kadang-kadang digunakan oleh jenis cepat kompleks untuk kasus-kasus di mana jumlah item yang akan diurutkan kecil (beberapa puluh). Ini agak mirip dengan menyortir dengan gelembung, karena di sana-sini elemen tetangga berturut-turut dibandingkan. Tetapi mengurutkan berdasarkan sisipan mencari elemen berikutnya untuk posisi yang benar di bagian data yang sudah diurutkan, dan tidak hanya mendorong elemen ekstrem ke posisi ekstrem. Dengan pendekatan ini, memori tambahan juga tidak diperlukan. Seperti penyortiran gelembung, penyisipan penyisipan sangat cepat pada data yang dipesan dan lebih cepat pada data yang dipesan sebagian. Dalam kasus terakhir, secara signifikan lebih cepat daripada gelembung. Biasanya menyortir berdasarkan sisipan agak lebih cepat daripada menyortir berdasarkan pilihan. Dan tidak seperti yang terakhir, itu, seperti penyortiran gelembung, stabil. Terburuk dari semuanya, penyortiran penyisipan berfungsi dengan data dalam urutan terbalik, yang terkadang menjadi yang paling lambat dari yang paling lambat. Untuk tes, implementasi berikut ini digunakan. Ini dapat dipercepat sedikit jika Anda menggunakan pencarian tidak linier, tetapi biner, misalnya, menggunakan fungsi std :: bsearch. Akselerasi yang signifikan dapat dicapai dengan menggunakan struktur tipe daftar, penyisipan elemen yang sangat cepat. Anda juga dapat memperhatikan bahwa ini adalah penyortiran yang paling alami - misalnya, biasanya digunakan secara intuitif saat bermain kartu.

Shell sorting adalah yang paling sederhana di antara metode cepat dan sangat cocok untuk siswa yang baru mulai belajar pemrograman. Ini hanya beberapa modifikasi dari penyortiran gelembung. Satu-satunya perbedaan di antara mereka adalah bahwa dalam pemilahan Shell, jarak antara elemen-elemen yang dibandingkan diambil bervariasi dari lorong ke lorong, dari yang lebih besar di lintasan pertama, ke 1 di yang terakhir, sehingga metode Shell berubah menjadi penyortiran gelembung primitif di lintasan terakhir ini. Donald Shell menerbitkan algoritma penyortiran dasar yang mendapatkan namanya pada tahun 1959. Jadi, ini adalah salah satu penyortiran universal pertama yang bekerja cepat. Sebagai perbandingan, algoritma pengurutan cepat diterbitkan dua tahun kemudian, dan pemilahan populer Tim atau pengurutan introspektif menjadi dikenal hanya pada tahun 90-an. Beberapa masalah matematika yang tidak terpecahkan yang menarik dikaitkan dengan pengurutan Shell, yang utamanya adalah bagaimana memilih secara optimal perpindahan antara elemen yang dibandingkan. Beberapa urutan rekaman ditemukan, misalnya, A102549 . Urutan semacam itu ditemukan melalui perhitungan kolosal, sehingga mereka memiliki panjang yang sangat pendek, A102549 hanya 8 elemen, yang cukup hanya untuk data hingga sekitar 3.000 elemen. Untuk data besar, sekuel perlu dilihat hampir secara acak. Nilai yang digunakan dekat dengan kekuatan 2, e , 2.25 dan 3. Angka prima yang dekat dengan kekuatan 2 menunjukkan hasil terburuk, terasa lebih rendah daripada yang terbaik. Tetapi tiga opsi lainnya ternyata kurang lebih sama dalam hal dampak pada kinerja dan mungkin sangat dekat dengan optimal. Selain itu, dalam tiga kasus ini, penggunaan bilangan prima tidak memberikan keuntungan nyata. Sangat mengherankan bahwa bias yang diajukan di Wikipedia (dengan basis 2,25) berdasarkan referensi ke karya yang sesuai tidak menunjukkan hasil terbaik pada tes, meskipun perbedaan mereka dari yang terbaik sangat tidak signifikan (tidak lebih dari 5-10%). Menggunakan A102549 sebagai titik awal juga tidak memberikan hasil yang nyata. Mikhail Opanasenko juga mencoba mengungkap penyortiran Shell dan memperoleh hasil yang menarik bahwa perpindahan yang dipilih oleh rumus s _{n + 1} = 10s _n / 3 memberikan efek yang sangat baik dan bahkan mungkin mendekati ideal. Hasil saya mengkonfirmasi ini. Dalam banyak kasus, bias semacam itu yang memberikan hasil terbaik, meskipun ini tidak selalu terjadi dan kesenjangan dari hasil terdekat cukup kecil (sekitar 5%). Kode saya untuk mengimplementasikan penyortiran Shell menggunakan tabel kecil dengan offset, meskipun jika Anda tidak menggunakan bilangan prima, maka offset untuk tabel ini dapat dihitung hampir secara instan, seperti yang dilakukan dalam implementasi salah satu varian yang diberikan dari penyortiran ini.

Sangat menarik bahwa jika kita mengambil offset dekat dengan kekuatan tiga kali lipat dengan cara yang sedikit berbeda dan menggunakan algoritma yang sedikit berbeda (lihat implementasi ), maka pada angka 32-bit kita akan mendapatkan kecepatan mendekati yang terbaik, tetapi pada angka yang lebih panjang dan pada garis kita akan mendapatkan perlambatan yang signifikan, kadang-kadang lebih dari 100%. Hasil untuk algoritma terbaik yang digunakan oleh oms7 juga ada dalam tabel di bawah ini, tetapi meskipun menunjukkan hasil yang baik secara berurutan, ia tertinggal jauh di belakang para pemimpin dalam hal nilai absolut.

Akankah ada cara untuk menemukan offset terbaik? Mungkin, tetapi saya berani menyarankan bahwa itu tidak segera. Pengurutan Shell digunakan dalam kernel Linux, dan setidaknya dalam satu pustaka C kodenya digunakan untuk fungsi qsort () standar. Secara teori telah dibuktikan bahwa kecepatan sortir optimal Shell hanya sedikit lebih lambat daripada metode logaritmik cepat "nyata". Memang, ketergantungan waktu pemrosesan data rata-rata pada ukurannya untuk pemilahan Shell yang optimal dijelaskan oleh rumus ∽ N (log N / log log N ) ² , yang bahkan untuk N yang sangat besar sangat dekat dengan rumus ∽ N log N khas untuk metode cepat lainnya. Biasanya, pengurutan Shell seringkali lebih cepat daripada metode yang secara teoritis lebih cepat dan hanya mulai menghasilkan sedikit untuk mereka ketika memproses array yang agak besar (dari urutan 10 juta elemen). Penyortiran ini benar-benar tidak memerlukan memori tambahan dan berperilaku stabil untuk berbagai pilihan untuk mengisi data, dibandingkan dengan penyortiran cepat. Metode Shell tidak memiliki properti stabilitas.

Penyortiran cepat hanya sedikit lebih kompleks daripada algoritma Shell dan masih merupakan salah satu cara tercepat untuk mengatur data yang tersebar secara acak. Namun, penyortiran ini memiliki beberapa kelemahan. Ia membutuhkan memori tambahan dan untuk kasus yang sangat jarang, ia bekerja sangat lambat, sesuai dengan ketergantungan kuadratik. Gagasan utama dari metode ini adalah untuk membagi data menjadi dua bagian: data dalam satu bagian harus lebih atau kurang (tergantung pada urutan yang dipilih) daripada yang lain. Ada beberapa metode untuk pemisahan ini. Idealnya, dengan setiap divisi, kedua bagian harus berukuran kurang lebih sama, dan yang terburuk, ketika salah satu bagian ternyata terdiri dari hanya satu elemen selama pembagian. Mari kita perhatikan beberapa implementasi algoritma penyortiran cepat, khususnya, metode Hoar , di mana elemen referensi yang membagi data menjadi dua bagian dipilih dari tengah data yang diurutkan.

Kami juga mempertimbangkan algoritma Lomuto yang sangat kompak, yang kadang-kadang sedikit (sekitar 1%) lebih cepat daripada metode Hoare yang dipertimbangkan. Namun, pada kasus khusus yang khas, misalnya, pada data pesanan, invers, atau malovarian, metode Lomuto menunjukkan kelambatan yang ekstrem. Selain itu, di antara opsi yang dipertimbangkan untuk penyortiran cepat, ini ternyata menjadi yang paling serakah untuk ukuran tumpukan selama menjalankan praktis: ketika menyortir array yang relatif kecil, hanya jenis ini tidak memiliki cukup 8 megabyte untuk tumpukan, saya harus mengatur ukuran ini melalui ulimit lebih banyak. Keserakahan yang demikian terhadap tumpukan mengarah pada pelambatan besar ketika memproses data besar (puluhan juta baris), dan saya mengalami kesulitan menyebut sifatnya. Saya hanya bisa menyatakan bahwa lebih baik tidak menggunakan pengurutan ini dari paragraf berikutnya dengan data tersebut.

Metode Lomuto memilih elemen terakhir sebagai referensi, tetapi dimungkinkan untuk menerapkan penyortiran cepat tanpa elemen pendukung sama sekali, lebih tepatnya, pemilihan elemen semacam itu di sini terjadi sebagai hasil dari pembagian data yang sudah dilakukan. Penyortiran ini berdasarkan karakteristik kecepatan ternyata dekat dengan metode Lomuto, meskipun biasanya sedikit lebih cepat, dan dalam kasus-kasus ekstrim itu terasa lebih cepat daripada Lomuto, tetapi lebih lambat dari Hoar.

Pada tahun 2009, algoritma quick-sort dua jangkar diterbitkan, yang menjadi standar untuk bahasa Java. Algoritma ini mengurangi jumlah permutasi sebesar 20% dibandingkan dengan yang tipikal terbaik, tetapi jumlah perbandingan tidak berubah. Penulisnya adalah Vladimir Yaroslavsky. Ini benar-benar berfungsi, sebagai aturan, lebih cepat daripada jenis cepat lainnya. Saya sedikit mengoptimalkannya, menggunakan fakta yang sudah lama diketahui bahwa pada arsitektur x86, swap biasanya bekerja lebih cepat daripada penugasan, dan untuk string C ++ jauh, jauh lebih cepat. Semua penyortiran cepat dianggap sejauh ini tidak memiliki properti stabilitas.

Memori tambahan untuk pengurutan cepat diperlukan untuk mengatur panggilan rekursif. Namun, panggilan kedua tersebut dapat digantikan dengan satu loop, dengan mengoptimalkan rekursi ekor , yang dalam hal kecepatan mungkin tidak memberikan keuntungan apa pun, tetapi secara signifikan mengurangi ukuran data tambahan yang digunakan. Saya menerapkan opsi semacam Hoar dengan optimasi ini. Selain itu, dalam program sistem, Anda dapat memeriksa penumpukan tumpukan dan jika mendekati nilai kritis, Anda dapat dengan mudah mengatur ulang semua panggilan rekursif dan mulai menyortir lagi - untuk kasus ini jelas bahwa Anda perlu menggunakan opsi pengurutan cepat yang tidak melambat pada data yang hampir dipesan, misalnya , versi Hoar yang diusulkan di atas. Melawan penggunaan memori tambahan dapat dianggap sebagai gagasan utama penyortiran cepat dari perpustakaan bahasa C standar di GCC. Itu umumnya ditinggalkan rekursi. Sebaliknya, mereka menggunakan simulasinya, yang memungkinkan sepertiga untuk mengurangi beban pada tumpukan. Kode itu ternyata agak besar, sekitar 150 baris. Tentang penyortiran ini masih akan ada sedikit materi di bawah ini.

Penyortiran hash bisa sangat cepat, dekat dengan ∽ N. Namun, kadang-kadang dapat bekerja pada ketergantungan kuadrat. Kecepatan metode penyortiran ini sangat tergantung pada input. Jika data terdistribusi secara merata oleh fungsi hash melalui array bantu, maka kita mendapatkan hubungan linier tercepat. Dan jika semua data dikelompokkan di dekat beberapa "pusat massa" berjauhan atau ketika ada banyak elemen data yang identik, yaitu, ketika banyak tabrakan hash terjadi, maka kita mendapatkan tipe terburuk ketergantungan n ² . Seperti penyortiran pohon, untuk mengurutkan hash, Anda memerlukan cukup banyak data tambahan, dalam daftar kode di bawah ini Anda perlu, misalnya, 12 byte tambahan untuk setiap integer yang dapat diurutkan (int32, x86-64). Properti yang menarik dari pengurutan hash adalah tidak adanya operasi perbandingan antara elemen data, yang membedakan pengurutan ini dari semua yang dipertimbangkan di atas. Lebih tepatnya, operasi ini hanya diperlukan untuk tabrakan. Saat menyortir data di mana kunci cocok dengan seluruh elemen data, Anda dapat menggunakan penghitung tambahan untuk jumlah elemen yang identik, tetapi ini lebih merupakan optimasi yang meragukan. Anda juga dapat menggunakan pohon biner daripada daftar untuk menyimpan data tabrakan hash, ini sangat mempercepat pekerjaan untuk kasus-kasus khusus individu ketika ada banyak tabrakan, tetapi secara keseluruhan, ketika menggunakan pohon biner, dalam banyak kasus itu melambat dan ini terlepas dari fakta bahwa dalam kasus ini elemen data harus menyimpan hampir 100 byte informasi tambahan. Saya menerapkan tiga opsi untuk pengurutan hash menggunakan pohon biner: satu menggunakan pohon tidak berurutan, dan dua lainnya menggunakan pohon standar dari std dan meningkatkan perpustakaan. Penyortiran hash praktis tidak cocok untuk menyortir string teks, kecuali untuk string yang sangat pendek, karena tidak mungkin membuat fungsi hash yang baik untuk data tersebut. Saya tidak bisa mengadaptasi hash C ++ standar (unordered_multiset) untuk menyortir: Saya mencoba menggunakan fungsi hash monoton dan memesan hubungan alih-alih kesetaraan - ini tidak berhasil.

Penyortiran array sangat mirip dengan yang sebelumnya. Array bantu juga digunakan, di mana nilai dimasukkan oleh fungsi hash. Dalam hal terjadi tabrakan, perlu untuk menggeser fragmen kontinyu dari elemen yang ditempati ke posisi kiri atau kanan, membebaskan posisi yang ditunjukkan oleh fungsi hash untuk elemen baru. Untuk mendapatkan kecepatan yang baik, perlu bahwa array bantu beberapa kali (dari 2-3) lebih dari yang asli. Dengan peningkatan ukuran array bantu, kecepatan operasi hanya meningkat hingga batas tertentu, tergantung pada data yang diurutkan dan fungsi hash yang terkait dengannya, dan kemudian (biasanya dari 4-5) menurun. Kecepatan operasi hampir sama dengan hash, tetapi pada data yang baik sedikit lebih cepat, dan pada data yang buruk itu terasa lebih lambat. Semacam ini juga membutuhkan banyak memori tambahan. , , , , – 28 , , , , . . , .

, , , , , , , .

Salah satu penyortiran tercepat, yang tidak pernah menggunakan perbandingan sama sekali, adalah penyortiran bitwise yang dikenal sejak abad ke-19. (radix sort). – ( 8, 11 16 ). , . . ( LSD – Least Significant Digit), ( MSD – Most Significant Digit). . , : boost, ++, - ++. , , . , , , , . , , ( , ). , . di sini , ini didasarkan pada kode dari artikel oms7 yang disebutkan. Opsi urutan byte terbalik lebih fleksibel dan sangat cocok untuk menyortir string. Opsi ini dapat diimplementasikan tanpa menggunakan memori tambahan (harga untuk ini adalah hilangnya properti stabilitas), seperti yang dilakukan dalam fungsi radixsort () perpustakaan bsd. Kode saya oms7, , , , , sradixsort() bsd. , , , . - , , . « » . , , , ∽ N , tetapi koefisien proporsionalitas di sini tergantung pada ukuran elemen data dan untuk string atau nomor yang panjang itu bisa sangat terlihat.

Opsi untuk sortasi MSD bitwise adalah sortasi berkas , struktur data yang memungkinkan Anda untuk secara efisien menempatkan kunci array asosiatif. Implementasi saya , meskipun mengoptimalkan penggunaan memori, masih ternyata sangat rakus untuk itu. Dengan kecepatan, hasil terbaik diperoleh saat memilah garis panjang.

Selanjutnya kami akan mempertimbangkan beberapa penyortiran yang dapat ditemukan di perpustakaan standar.

C (qsort, GCC), . , - (, BSD) , , ++, , POD . , , memcpy . , , , . GCC . - , , , std::vector , – . : , - , , qsort . – , 7 , , . . «» ( 21 ). , .

C++, , std::sort , GCC. , spread- , spread- ( 0 30%), – 3-4 . , : 1) , ; 2) , .

++ ( std::stable_sort), seperti namanya, memiliki properti stabilitas - ia mempertahankan urutan relatif antara elemen dengan kunci yang sama. Properti ini relatif jarang diperlukan, meskipun saya menulis tentang itu agak tidak berdasar, hanya berdasarkan pengalaman saya sendiri. Itu dapat menggunakan memori tambahan, yang membuatnya lebih cepat. Anehnya, pengurutan ini seringkali lebih cepat daripada std :: sort.

Dalam python bahasa super-populer, pengurutan Tim digunakan sebagai standar . Untuk tes, saya menggunakan versinya dari repositori github. Ini menunjukkan hasil yang baik memecahkan rekor pada data yang dipesan sebagian, tetapi rata-rata masih terasa lebih lambat daripada pemimpin. Biasanya kecepatannya adalah rata-rata antara penyortiran cepat dan penyortiran Shell, meskipun pada garis kadang-kadang dekat dengan para pemimpin. Ia memiliki properti stabilitas. Ini mengimplementasikan algoritma yang relatif rumit, dalam implementasi standar yang kesalahan ditemukan pada tahun 2015, yang, bagaimanapun, membutuhkan situasi yang agak tidak realistis untuk manifestasinya.

Pustaka BSD C memiliki penyortiran bitwise ( radixsort ) (sradixsort). , -. – , ++.

- BSD ( mergesort) Penyortiran ini dikenal sebagai salah satu yang tercepat untuk data akses berurutan (file, daftar) dan mungkin digunakan di pustaka standar C ++ untuk menyortir daftar (std :: list dan std :: forward_list). Ngomong-ngomong, dia dikenal sejak 1948 dan salah satu pengembangnya adalah ahli matematika dan spesialis yang sangat terkenal dalam sistem komputer pertama von Neumann. Dari metode cepat, pengurutan ini tidak dibedakan oleh karakteristik terbaik, meskipun, sebagai aturan, ini agak lebih cepat daripada metode Shell. Itu membutuhkan memori tambahan dan biasanya diterapkan berkelanjutan.

Selain itu, masih ada penyortiran dengan banyak(heapsort). Heap biasanya digunakan untuk antrian optimal dengan prioritas, tetapi juga dapat digunakan untuk menyortir. Tumpukan tumpukan tidak memerlukan memori tambahan, tetapi mereka tidak memiliki properti stabilitas. Dalam kecepatan untuk angka, secara signifikan (hingga 3-6 kali) lebih lambat daripada metode Shell, tetapi untuk garis yang tidak terlalu pendek, itu menunjukkan hasil yang sangat baik, menyalip (dengan peningkatan panjang garis, keuntungan meningkat) metode Shell.

Heap sorting juga tersedia di pustaka standar C ++. Penyortiran semacam itu dilakukan dalam dua operasi: membangun heap (std :: make_heap) dan kemudian benar-benar menyortir ( std :: sort_heap) Di sini, tidak seperti perpustakaan bsd, penyortiran hanyalah salah satu operasi untuk heap. Biasanya, opsi pengurutan ini sedikit lebih cepat dari yang sebelumnya (opsi bsd menunjukkan hasil yang lebih baik hanya pada angka pendek dan panjang s-line).

++, (std::multiset) – , . . , , , 10-30%. , , g++ , 32 a ( x86-64) – , . . boost::container::multiset, : 24 . boost, – , . - . – .

boost spreadsort , 21 . . . , , . – -, bsd. - , , spin- . spread- (boost v1.62) - saat menyortir array C-string kecil (hingga 1000 elemen), ia bekerja dengan kesalahan.

Ada juga algoritma pdqsort baru yang meningkatkan, seperti yang dinyatakan oleh penulis, penyortiran introspektif. Algoritma baru ini, yang belum dijelaskan di Wikipedia. Hasilnya - meskipun tidak buruk, tetapi tidak terlalu mengesankan. Ini lebih lambat dari std :: sortir pada bilangan bulat pendek, tetapi lebih cepat pada string dan bilangan bulat panjang. Dalam kedua kasus tersebut, perbedaannya agak tidak signifikan. Hasil terbaik untuk penyortiran ini diperoleh untuk string C ++ panjang - ini dia lebih rendah, meskipun secara nyata, hanya untuk pemimpin, penyortiran-penyebar.

Sebagai pendongkrak Anda masih bisa menemukan spinsort. Ini juga merupakan algoritma baru, yang, tidak seperti yang sebelumnya, memiliki properti stabilitas dan yang juga belum dijelaskan di Wikipedia. Biasanya dia dekat dengan pemimpin, tetapi dengan tertinggal di belakangnya. Ini membutuhkan, meskipun tidak terlalu banyak, memori tambahan. Mari kita akhiri

dengan flat_stable_sort dari pustaka boost yang sama. Ini adalah algoritma baru yang kuat lainnya yang belum dijelaskan di Wikipedia. Sejauh ini, ini adalah metode tercepat, tetapi sedikit lebih rendah daripada kebanyakan metode perpustakaan cepat lainnya. Ini menggunakan memori tambahan sangat sedikit (namun, selalu membutuhkan tabel ukuran tetap 8 KB) dan seringkali terasa lebih cepat daripada metode Shell.

Pertimbangkan mejawaktu (dalam ms) dari pengoperasian algoritme ini pada komputer dengan 8 GB RAM dengan prosesor AMD Phenom ™ II X4 955 @ 3.214 MHz. Komputer bekerja selama total beberapa bulan, dan ukuran total data yang dikumpulkan dalam dua file json yang dimuat dengan tabel hampir 400 KB. Pengaturan waktu diberikan oleh rata-rata jumlah lintasan, untuk ukuran yang lebih kecil, lintasan ini lebih besar. Bekerja dengan cache dengan cara yang agak rumit mengubah kecepatan perhitungan, sehingga hasil yang diperoleh hanya perkiraan terbaik (Saya dapat mengasumsikan bahwa ketidaktepatan waktu dapat mencapai hingga 20%). Saya percaya bahwa pada prosesor modern terbaik untuk PC, hasilnya dapat diperoleh 2-3 kali lebih cepat, tetapi harus diingat bahwa banyak prosesor modern bekerja dengan beralih di antara frekuensi yang berbeda dan hasil yang diperoleh bersama mereka,akan lebih mendekati.

Ini dan tabel berikut bersifat interaktif. Selain nilai absolut dari timing, Anda juga dapat melihat nilainya relatif terhadap rata-rata, median, minimum, dan maksimum. Anda dapat mengubah akurasi karakter. Anda juga bisa mendapatkan hubungan waktu untuk berbagai jenis isian dan tipe data. Yang terakhir, misalnya, mungkin menunjukkan bahwa menyortir string C terasa jauh lebih cepat daripada string C ++. Dari metode pengurutan, Anda juga dapat memilih dan merakit berbagai himpunan bagian. Anda tentu saja dapat mengatur penyortiran berdasarkan kolom apa pun. Sayangnya, saya tidak tahu cara menggunakan Javascript dalam artikel di hub, sehingga tabel hanya tersedia dengan referensi. Untuk kasus jika imtqy.com kelebihan beban, saya juga memberikan tautan cadangan ke tabel pertama dan kedua .

, , . , N , 1000, , . , ( ). , (deviation) .

:

• jenis shell terbaik pada data hingga 10 juta elemen dapat menyalip timsort dan bahkan beberapa jenis cepat;
• timsort sangat dekat dalam kecepatan qsort (clib), kadang-kadang menyalip agak, dan kadang-kadang sebaliknya;
• heapsort dan terutama treeort sering melambat secara nyata, tetapi dengan latar belakang gelembung atau bahkan pilihan, jelas bahwa ini masih merupakan metode cepat. Menariknya, kedua metode ini sering memiliki karakteristik yang sangat mirip - mereka berdua membangun pohon. Sangat mudah untuk melihat bahwa dependensi untuk heapsort dan treeort, meskipun tidak jelas kuadrat, jelas bukan N log N , tetapi jauh lebih buruk - dibandingkan dengan pengurutan Shell, yang berperilaku jauh lebih baik dengan meningkatkan volume data daripada heapsort atau treesort, sementara bahwa dia sendiri lebih lambat dari N log N. Dengan demikian, implementasi praktis dari heap dan sortasi pohon tidak sesuai dengan spesifikasi teoretis mereka;
• data pada pengurutan string menunjukkan bahwa hukum dependensi waktu di sini tidak sama dengan angka - panjang string yang diurutkan entah bagaimana ditumpangkan pada undang-undang ini di sini. Sayangnya, saya tidak tahu rumus untuk penyortiran yang diketahui yang akan memberikan hukum pasti tentang dependensi waktu ketika bekerja dengan string;
• menarik bahwa kecepatan bekerja dengan bilangan real hampir sama dengan bilangan bulat - ini adalah konsekuensi dari kenyataan bahwa dalam arsitektur x86 modern, optimasi yang sangat efektif untuk bekerja dengan stack dibuat;
• hash_sort menunjukkan hasil yang cukup biasa-biasa saja, ini dimungkinkan karena fakta bahwa karena penggunaan memori tambahan, kinerja cache prosesor menurun tajam. Pada data acak kecil (kurang dari seratus ribu elemen) pengurutan hash menyalip jenis cepat terbaik. Anda juga dapat melihat bahwa dimungkinkan lagi karena cache, beberapa hasil dari penyortiran ini sangat aneh, misalnya, 10 ⁵ , 10 ⁶ dan 10 ⁷ bilangan bulat 32-bit saat menggunakan pengisian yang dipesan sebagian diurutkan sekitar kurang lebih sama waktu! Semacam efek yang hampir kuantum. :) Saya yakin bahwa jika Anda mencari, Anda dapat menemukan kesulitan lainnya untuk menjelaskan hasil.

Saya akan menambahkan beberapa kesimpulan tentang beberapa kasus khusus:

• beberapa jenis padding data mengungkapkan kelemahan dalam quicksort. Namun, pilihan elemen pendukung dengan cara yang rumit membuat kemungkinan jatuh ke urutan yang buruk untuk menyortir praktis nol. Anda juga dapat memilih elemen pendukung pada setiap pass dengan cara yang berbeda atau secara acak. Mungkin mereka melakukannya dalam qsort (clib). Metode Hoare yang dipertimbangkan bekerja sangat lambat hanya pada sekuens yang dirancang khusus, yang ditemui secara kebetulan selama kerja praktek - ini adalah kasus dengan probabilitas 2 ^N- 3 / N ^N , yaitu, peristiwa yang hampir benar-benar mustahil. Meskipun jika kita mempertimbangkan urutan di mana metode Hoar tidak bekerja selambat mungkin, tetapi hanya dengan perlambatan yang signifikan, maka ada lebih banyak kasus seperti itu, yang, bagaimanapun, meninggalkan kemungkinan kasus pemrosesan data lambat yang tidak dapat diterima masih praktis tidak signifikan, meskipun sangat mengganggu dalam perbedaan dari nol. Juga hampir tidak mungkin untuk secara tidak sengaja mendapatkan data yang mana penyortiran cepat dengan dua titik kontrol akan bekerja lambat, menurut hukum kuadratik. Opsi pengurutan cepat Lomuto tanpa dan tanpa elemen dukungan menunjukkan hasil yang sangat buruk pada hampir semua kasus pengisian tertentu;
• dalam beberapa kasus khusus, penyortiran “gelembung” paling lambat memberikan hasil yang sangat baik, dan beberapa yang tercepat, penyortiran cepat, sebaliknya, sangat buruk;
• Penyortiran hash menunjukkan hasil yang sangat buruk pada pengisian tipe 8 dan 9, ini karena urutan monoton diambil dari nilai berturut-turut, mulai dari yang lebih kecil, dan 1% dari angka acak diambil dari kisaran dari yang lebih rendah ke nilai maksimum, yang menanggung semua berturut-turut 99% dari data menjadi satu elemen hash. Kasus ini menunjukkan dengan sangat baik masalah yang mungkin timbul saat menggunakan penyortiran ini atau menyortir dengan array dengan data yang tidak diketahui;
• pemilihan sortir berperilaku sangat stabil pada semua jenis pengisian, sortasi tumpukan dan pohon juga cukup stabil, tanpa puncak dan kemiringan yang jelas. Ini benar, tentu saja, untuk jenis Shell, serta sebagian besar metode cepat lainnya dari perpustakaan standar.

Sekarang saatnya berbicara tentang tipe data yang digunakan dengan algoritma pengurutan:

1. integer 32-bit ditandatangani (int32_t), tetapi hanya non-negatif yang digunakan. Data numerik lainnya juga diambil hanya non-negatif - ini tidak mengurangi hasil umum, tetapi membuatnya lebih mudah untuk mendapatkan beberapa algoritma;
2. integer, 64-bit ditandatangani (int64_t);
3. bilangan bulat, ditandatangani 128-bit (__int128 - didukung oleh setidaknya GCC);
4. struktur lima bilangan bulat (int32_t), salah satunya digunakan sebagai kunci (INT1P4). Ketika menyortir data seperti itu, jumlah permutasi mulai mempengaruhi waktu komputasi secara lebih signifikan, oleh karena itu, metode dengan permutasi yang lebih sedikit mendapatkan beberapa keuntungan;
5. bilangan real seperti presisi ganda, ganda (angka float);
6. string pendek C ++ dan C. String 1 hingga 16 diambil (string pendek dan c-string pendek);
7. string C dan C ++ dengan panjang sedang, yang panjangnya dari 1 hingga 256 (string dan c-string);
8. garis panjang C dan C ++, panjangnya dari 1 hingga 2 ²⁰ (ini sedikit lebih dari satu juta), dan garis dipilih sehingga panjang rata-rata tidak melebihi 512, sehingga garis dipilih hanya untuk pengisian acak, untuk kasus lain, garis hanya diambil panjangnya dari 1 hingga 512 (panjang string dan panjang c-string).

Dan juga tentang cara mengisi array sumber untuk menyortir:

1. secara kebetulan;
2. secara ketat naik (dipesan);
3. benar-benar turun (urutan terbalik, terbalik);
4. nilai acak dari rentang 0 hingga 99 (variasi kecil, variasi rendah 100);
5. urutan acak 0 dan 1 (variasi kecil, variasi rendah 2);
6. konstan 0 (spread kecil, variasi rendah 1);
7. urutan memimpin versi qsort (Hoare) ke eksekusi paling lambat. Sangat mengherankan bahwa ada tepat 2 ^N -3 sekuens semacam itu di antara semua sekuens panjang N ;
8. benar-benar naik, dengan penyisipan 1% angka acak (dipesan sebagian);
9. benar-benar turun, dengan penyisipan 1% variabel acak (sebagian terbalik).

Harus ditekankan bahwa data acak adalah kasus paling umum dalam mengisi array, semua metode lain sangat langka dan bahkan hampir tidak mungkin selama operasi normal tertentu.

Mari kita lihat hasil tes, di mana penyortiran bekerja dengan semua urutan data yang mungkin. Jumlah urutan seperti itu sama dengan faktorial panjangnya, dengan demikian, untuk urutan panjang 12 ada 479'001'600 varian - PC modern yang baik akan menghitung jumlah mereka dalam waktu kurang dari satu menit. Jika kita mengambil urutan panjang 14, kita sudah mendapatkan 87'178'291'200 varian untuk beberapa jam operasi komputer. Oleh karena itu, tabel berikut ini menunjukkan waktu rata-rata (dalam siklus prosesor yang diperoleh melalui instruksi RDTSC ) dari satu pengurutan ketika mengurutkan semua permutasi hingga hanya 12. Dalam data, jenis numerik sebelumnya dan string pendek diambil. Tentu saja, orang dapat memperhatikan bahwa urutan dengan elemen berulang tidak dipertimbangkan. Namun, saya berani menyarankan bahwa kehadiran mereka tidak akan secara kualitatif mengubah hasil, tetapi secara signifikan dapat memperlambat penerimaan mereka.

Hasil untuk data sekecil itu tidak terlalu representatif, dan terutama untuk metode penyortiran yang kompleks, tetapi mereka masih melengkapi gagasan tentang perilaku penyortiran. Beberapa jenis, sejauh yang saya tahu, mengganti algoritma utama mereka dengan yang lain ketika bekerja dengan array kecil - ini adalah jenis menyebar, cepat dengan dua titik jangkar dan radix_msd (dua penggunaan terakhir menyisipkan). Dan beberapa penyortiran (flat_stable dan radix) menggunakan tabel kecil, tetapi dengan ukuran data kecil, tabel ini ternyata jauh lebih besar dari data itu sendiri, yang sangat memperlambat metode ini dibandingkan dengan yang lain dan menghasilkan hasil yang aneh. Hasil yang aneh juga diperoleh dengan pengurutan bitwise lainnya dan dengan pengurutan hash dan array. Hasil yang tidak biasa seperti itu mudah dijelaskan oleh fakta bahwa waktu persiapan untuk data sebelum menyortir metode ini untuk data kecil lebih lama daripada waktu penyortiran itu sendiri. Tentu saja, ketika mengukur interval waktu sekecil itu (nanodetik), pengaruh berbagai kesalahan pada hukum yang ditampilkan jauh lebih tinggi daripada di tabel sebelumnya. Oleh karena itu, undang-undang tersebut ternyata sangat mendekati, sering "dengan pergeseran" ke nilai yang berlebihan. Yang terakhir ini sebagian dijelaskan oleh fakta bahwa ketika bekerja dengan data kecil waktu penyortiran itu sendiri menjadi sebanding dengan waktu memanggil fungsi penyortiran dan beberapa operasi tambahan yang diperlukan untuk mengukur waktu. Program mencoba untuk mengurangi overhead yang disebutkan dari output, tetapi ternyata dilakukan agak kurang. Dengan semua ini, saya berani berasumsi bahwa dengan membandingkan hasil untuk berbagai jenis data dan dengan mempertimbangkan komentar yang dibuat, Anda terkadang dapat membuat asumsi yang tidak jauh dari akurat.

Sebagai kesimpulan, tabel lain yang menunjukkan seberapa banyak metode pengujian yang berbeda diperlukan untuk menyortir memori tambahan. Jelas, nilai ini tergantung pada sistem. Dalam pengujian saya, seperti yang sudah saya tulis, ini adalah x86-64, GCC. Huruf T di dalamnya berarti ukuran tipe dalam byte (panjang string tidak termasuk dalam ukuran ini: untuk C-lines adalah ukuran pointer, untuk C ++ lines itu adalah ukuran deskriptor, 32 byte untuk x86-64 GCC), huruf L adalah tengah panjang jenis dalam byte (untuk angka ini adalah T, dan untuk string adalah panjang rata-rata string), huruf A dapat memiliki nilai 1 atau 0 - ini adalah penyelarasan ke batas 64-bit, dan huruf M adalah penyelarasan dari pengalokasi memori standar (diasumsikan sejajar dengan batas 32 byte). Simbol ^* berarti bahwa data untuk jenis penyortiran ini diperoleh hanya berdasarkan analisis membaca bidang VmRSS dari / proc / PID / status (bidang yang disebutkan adalah ukuran dari program proses).


Tentu saja ada metode penyortiran lainnya, baik primitif dan cepat. Pustaka boost memiliki algoritme paralel yang memungkinkan Anda memanfaatkan keberadaan inti prosesor tambahan dalam sistem. Anda juga dapat menggunakan penambah wadah pesanan sendiri :: container :: flat_multiset alih-alih std :: multiset, tetapi kerjanya sangat lambat.

Saya mengambil kesempatan ini untuk mengatakan beberapa komentar tentang peningkatan perpustakaan secara umum. Saya sarankan untuk tidak lewat. Bahkan fitur-fitur yang ada di perpustakaan standar dalam peningkatan, sebagai aturan, lebih baik diimplementasikan, dan kadang-kadang (seperti ekspresi reguler) jauh lebih baik. Jika kita berbicara tentang wadah, maka dalam dorongan mereka terlihat lebih besar, dan mereka yang bertepatan dengan yang standar kadang-kadang agak lebih cepat dan sering memiliki perbaikan kecil, tapi bagus. Tingkatkan pemeriksaan jenis yang lebih teliti, yang kadang-kadang dapat membantu mendeteksi kesalahan yang hampir sulit dipahami yang biasanya tidak muncul dengan sendirinya, tetapi dalam beberapa keadaan dapat diaktifkan secara tidak terduga. Kerugian dari peningkatan termasuk tanpa syarat sama sekali tidak dapat dibaca dan besar dalam pesan volume tentang kesalahan kompilasi pada banyak konstruksi dari perpustakaan ini - ini, meskipun pada tingkat lebih rendah, berlaku untuk perpustakaan standar. Sudah waktunya bagi pengembang C ++ untuk melakukan sesuatu tentang ini.

Semua file dengan tes dan beberapa materi terkait lainnya dapat diambil dari repositori saya. Jika seseorang tertarik pada data sumber mentah, maka Anda bisa mendapatkannya di sini (1,4 MB). Saya akan senang dengan komentar, kritik, dan tambahan apa pun.