Ketika tidak menggunakan algoritma STL. Berikan contoh

Kawan, selamat malam! Anda dengan dingin membongkar edisi pertama buku " C ++ 17 STL. Perpustakaan Template Standar " dari kami dan Anda terus menganalisis yang kedua, sehingga kami akhirnya memutuskan untuk menyajikan di sini sudut pandang alternatif. Penulis artikel hari ini adalah Ivan Čukić, yang juga memiliki buku Pemrograman Fungsional di C ++ , yang sedang dipersiapkan untuk diterbitkan di Manning Publishing House. Kami menawarkan untuk mengevaluasi pemikiran, kode, dan perhitungan skeptisnya

Pembukaan

Saya ingin menamai posting ini "Pada kejujuran algoritma STL" untuk menguji kemampuan saya sendiri dalam memprovokasi klik. Tapi kemudian dia memutuskan bahwa lebih baik menulis artikel untuk audiens target, dan tidak menulis posting di mana mereka yang ingin berdebat tentang tesis mengerikan saya akan datang bersama-sama.

Jadi, saya dapat berasumsi bahwa Anda tertarik pada algoritma, kompleksitasnya dan ingin menulis kode yang paling sempurna.

Algoritma

Di komunitas C ++ profesional modern, orang sering disarankan: untuk membuat program Anda lebih aman, lebih cepat, lebih ekspresif, dll. - Gunakan algoritma dari perpustakaan standar. Saya juga mencoba mempopulerkan saran ini dalam buku, pidato, seminar ... di mana pun ada audiens yang cocok.

Tentu saja, benar-benar benar bahwa jika kita tertarik untuk menulis loop for untuk menyelesaikan masalah di hadapan kita, pertama-tama kita perlu memikirkan apakah algoritma yang ada dari library standar (atau boost) cocok untuk ini, dan tidak bertindak secara membabi buta.

Kita masih perlu tahu bagaimana algoritma ini diimplementasikan, persyaratan dan jaminan apa yang terkait dengannya, apa kompleksitas spasial dan temporal mereka.

Biasanya, jika kita dihadapkan dengan tugas yang persis memenuhi persyaratan algoritma STL, dan dapat diterapkan secara langsung, algoritma ini akan menjadi solusi yang paling efektif.

Suatu masalah dapat muncul jika kita perlu menyiapkan data dalam beberapa cara sebelum menerapkan algoritma.

Persimpangan set

Misalkan kita sedang menulis alat untuk pengembang C ++ yang akan memberikan tips tentang mengganti opsi pengambilan default (berbicara tentang [=] dan [&] ) dalam ekspresi lambda, dan secara eksplisit akan menampilkan daftar variabel yang ditangkap.

 std::partition(begin(elements), end(elements), [=] (auto element) { ^~~ -  -  ,   [threshold] return element > threshold; }); 

Saat mem-parsing file, kita membutuhkan koleksi yang menyimpan variabel dari cakupan saat ini dan tetangga. Segera setelah kami menemukan ekspresi lambda dengan tangkapan default, kita perlu melihat variabel apa yang digunakan di sana.

Akibatnya, kami memiliki dua set: di satu akan ada variabel dari area visibilitas sekitarnya, dan yang lain akan ada variabel yang digunakan dalam tubuh ekspresi lambda.

Daftar opsi penangkapan yang akan kami tawarkan untuk penggantian harus merupakan persimpangan dari dua set ini (ekspresi lambda dapat menggunakan variabel global yang tidak perlu ditangkap, dan tidak semua variabel dari lingkup sekitarnya akan digunakan dalam ekspresi lambda).

Dan, jika kita membutuhkan persimpangan, maka kita dapat menggunakan std::set_intersection .

Algoritma ini cukup indah dalam kesederhanaannya. Ia menerima dua koleksi yang diurutkan dan secara bersamaan menjalankannya dari awal hingga akhir:

• Jika item saat ini di koleksi pertama sama dengan item saat ini di koleksi kedua, itu ditambahkan ke hasil, yang algoritma hanya bergerak ke item berikutnya di kedua koleksi;
• Jika item aktual dalam koleksi pertama kurang dari item sebenarnya dalam koleksi kedua, maka algoritme hanya melewatkan item saat ini di koleksi pertama;
• Jika item aktual dalam koleksi pertama lebih besar dari item sebenarnya dalam koleksi kedua, maka algoritme hanya melewatkan item saat ini di koleksi kedua;

Setidaknya satu elemen (dari koleksi input pertama atau kedua) dilewati di setiap iterasi - oleh karena itu, kompleksitas algoritma akan linear - O(m + n) , di mana m adalah jumlah elemen dalam koleksi pertama dan n adalah jumlah elemen dalam koleksi kedua .

Sederhana dan efektif. Selama koleksi input diurutkan.

Menyortir

Inilah masalahnya: bagaimana jika koleksi tidak disortir?

Dalam contoh sebelumnya, akan lebih bijaksana untuk menyimpan variabel dari area visibilitas sekitarnya dalam struktur seperti tumpukan, di mana parser bisa menambahkan elemen baru memasuki lingkup baru dan menghapus variabel dari lingkup saat ini segera setelah ia pergi.

Dengan demikian, variabel tidak akan diurutkan berdasarkan nama, dan kami tidak akan dapat langsung menggunakan std::set_intersection untuk operasi. Demikian pula, jika Anda melacak variabel di tubuh ekspresi lambda, maka kami kemungkinan besar tidak akan dapat menyimpannya dalam bentuk diurutkan.

Karena std::set_intersection hanya berfungsi dengan koleksi yang diurutkan, dalam banyak proyek prinsip ini terjadi: pertama kita mengurutkan koleksi, dan kemudian kita memanggil std::set_intersection .

Jika kita lupa bahwa menyortir tumpukan variabel dalam contoh kita benar-benar merendahkan seluruh penggunaan tumpukan yang kita definisikan, algoritma persimpangan untuk koleksi yang tidak disortir akan terlihat seperti ini:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); } 

Apa kompleksitas dari keseluruhan algoritma ini? Penyortiran membutuhkan waktu quasilinear, sehingga kompleksitas keseluruhan dari pendekatan ini adalah O(n log n + m log m + n + m) .

Sortir lebih kecil

Apakah mungkin dilakukan tanpa penyortiran?

Jika kedua koleksi tidak diurutkan, maka kita harus berkeliling koleksi kedua untuk setiap elemen dari yang pertama - untuk memutuskan apakah akan memasukkannya dalam set hasil. Meskipun pendekatan ini cukup umum dalam proyek nyata, itu bahkan lebih buruk daripada yang sebelumnya - kompleksitasnya adalah O(n * m) .

Alih-alih menyortir semuanya dalam satu baris, atau tidak menyortir apa pun, ingat Zen dan pilih Path Ketiga - kami hanya mengurutkan satu koleksi.

Jika hanya satu koleksi yang diurutkan, maka kami dapat mengulangi semua nilai dari yang tidak disortir satu per satu dan untuk setiap nilai periksa apakah koleksi tersebut ada dalam koleksi yang diurutkan. Untuk melakukan ini, terapkan pencarian biner.

Dalam hal ini, kompleksitas waktu adalah O(n log n) untuk menyortir koleksi pertama dan O (m log n) untuk menyortir dan memeriksa. Kompleksitas total akan menjadi O((n + m) log n) .

Jika kami memutuskan untuk mengurutkan koleksi kedua, dan bukan yang pertama, maka kompleksitasnya adalah O((n + m) log m) .

Untuk mencapai efisiensi maksimum, kami selalu mengurutkan koleksi di mana ada lebih sedikit elemen, sehingga kompleksitas akhir dari algoritma kami adalah
((m + n) log (min(m, n)) .

Implementasinya akan terlihat seperti ini:

 template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); } 

Dalam contoh kami dengan daftar tangkap dalam ekspresi lambda, kumpulan variabel yang ada dalam ekspresi lambda biasanya disortir, karena cenderung lebih kecil dari koleksi semua variabel dari semua cakupan sekitarnya.

Hashing

Opsi terakhir adalah membangun std::unordered_set (implementasi set unordered berbasis hash) dari koleksi yang lebih kecil, daripada mengurutkannya. Dalam hal ini, kompleksitas operasi pencarian akan rata-rata O(1) , tetapi akan membutuhkan waktu untuk membangun std::unordered_set . Kompleksitas bangunan dapat berkisar dari O(n) hingga O(n*n) , dan ini merupakan masalah potensial.

 template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); } 

Pendekatan hashing menang sepenuhnya ketika Anda perlu menghitung persimpangan beberapa set dengan satu set kecil yang telah ditentukan. Yaitu, kita memiliki himpunan A , himpunan B₁ , B₂… dan kami ingin menghitung A ∩ B₁, A ∩ B₂…

Dalam kasus ini, Anda dapat mengabaikan kompleksitas std::unordered_set construct, dan kompleksitas penghitungan setiap persimpangan akan linier - O(m) , di mana m adalah jumlah elemen dalam koleksi kedua.

Kontrol

Tentu saja, selalu berguna untuk memeriksa kompleksitas algoritme, tetapi dalam kasus seperti itu juga bijaksana untuk memeriksa berbagai pendekatan menggunakan pos pemeriksaan. Terutama ketika memilih dari dua opsi terakhir, di mana kami membandingkan pencarian biner dan perangkat berbasis hash.
Tes paling sederhana saya menunjukkan bahwa opsi pertama, di mana Anda harus mengurutkan kedua koleksi, selalu yang paling lambat.

Mengurutkan koleksi lebih kecil mengungguli std::unordered_set sedikit, tetapi tidak terlalu.

Baik pendekatan kedua dan ketiga sedikit lebih cepat daripada yang pertama dalam kasus ketika kedua koleksi memiliki jumlah elemen yang sama, dan jauh lebih cepat (hingga enam kali) ketika jumlah elemen dalam satu koleksi sekitar 1000 kali lebih banyak daripada yang kedua.