Sebagai kelanjutan dari topik saya ingin membagikan kode saya, yang menyalip std::sort() dari versi saat ini dari GNU C ++ Library dan (kurang-lebih, tidak ada data pasti) mengulangi hasil dari "Sort Alexandrescu" dengan CppCon 2019 .
Kondisi tugas
Dalam kode C++ ), perlu upaya yang wajar untuk menyortir tidak lebih buruk daripada std::sort() untuk menyingkirkan overhead menggunakan perpustakaan qsort() . Karena itu, termasuk menggunakan makro, bukan templat.
Pada gilirannya, jika Anda mengurutkan "tikus" daripada "gajah", maka biaya qsort() cukup besar: aritmatika alamat tambahan dan panggilan tidak langsung ke fungsi pembanding.
Hasil
Menurut informasi yang tersedia, kombinasi algoritma dan fitur implementasi ini lebih cepat daripada banyak opsi lain dalam arti praktis:
- dengan jumlah perbandingan dan gerakan (diukur dengan mengganti kelas
C++ untuk menghitung perbandingan dan tugas). - oleh volume kode mesin (membutuhkan sedikit ruang dalam cache).
- oleh volume kode sumber dan transparansi.
- pada urutan acak panjang, kenaikan cenderung 3-5%, tergantung pada SORT_THRESHOLD .
- hingga 1,5-2-3 kali lebih cepat dengan data yang dipesan atau didominasi dipesan.
- sedikit kerugian hanya pada urutan yang sangat singkat dalam urutan terbalik.
Sangat mungkin bahwa opsi ini sedikit lebih cepat dan / atau sedikit lebih lambat daripada sebagian besar jenisnya, tetapi menemukan ini secara harfiah adalah karya raksasa yang tidak mampu saya beli.
Sangat menarik jika seseorang membandingkan opsi ini dengan opsi saat ini di Tarantool, PostgreSQL, SQLite, dan MySQL. Saya harap kaamo tidak akan bisa lewat dengan SysBench - nya .
Bagaimana Alexandrescu?
Dalam komentar pertama dari RPG18, ada tautan ke kinerja baru-baru ini oleh Andrei Alexandrescu "Kecepatan Ditemukan Dalam Pikiran Orang" , di mana ia mengarah ke ide yang hampir serupa, tetapi pergi ke heap_sort lebih dekat ke final.
Pertunjukan itu terasa agak lama bagi saya (jika olegbunin telah memberikan 90 menit setidaknya sekali ...), tetapi jumlahnya tidak cukup. Secara khusus, saya ingin melihat perilaku penyortiran dengan meningkatnya N , karena peningkatan ambang penyelesaian QuickSort mengarah ke akselerasi pada ukuran besar dan perlambatan ke yang kecil, dll.
Namun demikian, dilihat dari angka-angka yang dikutip Alexandrescu, opsi yang dijelaskan tiba-tiba memberikan percepatan yang sama. Namun, sampai saya menemukan kode yang ditampilkan ke Alexandrescu dalam bentuk selesai, untuk "mengambil dan membandingkan", dan tidak ada waktu untuk menyandikan dengan video (tulis jika Anda menemukan atau melakukannya).
Sisi ideologis
Sisi teoretis dan ideologis dari "algoritma" ini cukup sederhana:
- Untuk urutan non-pendek, kami menggunakan QuickSort dengan semua optimasi yang dapat diterima:
- Tidak secara rekursif menggunakan tumpukan posisi internal pada pointer.
- Sebagai elemen pendukung, kami menggunakan median elemen pertama, tengah, dan terakhir.
- Kami tidak mengurutkan porsi kecil, kami meninggalkannya untuk ShellSort.
- Setelah pemisahan, kami selalu menempatkan bagian terbesar di tumpukan, akibatnya, tumpukan tidak bisa lebih dalam dari
Log2(N) .
- Tambah-urutkan data menggunakan ShellSort:
- jumlah minimum yang dilewati.
- langkah pada lintasan pertama berkorelasi dengan ukuran maksimum segmen yang tidak disortir.
- total hanya dua operan dengan langkah 8 dan (mau tidak mau) 1.
- Menggunakan ShellSort memungkinkan Anda untuk secara relatif meningkatkan ambang keluar untuk QuckSort. Sebagai hasilnya, kami memiliki kombinasi salah satu opsi QuickSort terbaik dengan penghematan karena jalan keluar sebelumnya dan penyortiran yang sedikit lebih cepat.
Perlu dicatat bahwa tergantung pada arsitektur prosesor dan kondisi aplikasi, Anda dapat meningkatkan gain pada urutan panjang hingga 10-15% dengan memilih SORT_THRESHOLD dalam 128-256. Namun, ini memperlambat pemrosesan urutan dengan urutan terbalik dan dekat dengannya.
Namun demikian, ini adalah bonus yang baik jika Anda memahami bahwa urutan terbalik tidak mungkin dalam data Anda, atau jika Anda dapat dengan murah mendeteksi kasus-kasus seperti itu dan menjalankan cabang dengan SORT_THRESHOLD kecil.
PS
Opsi pengurutan yang dijelaskan adalah "redone" untuk proyek libmdbx saya (basis data nilai kunci yang disematkan dengan ACID), di mana deskripsi README dan API yang lain diperbarui (sebenarnya ditulis ulang). Oleh karena itu, saya akan berterima kasih atas koreksi kesalahan ketik dan untuk saran dan saran. Dirinya, sebagai aturan, tidak terlihat kurangnya beberapa informasi.