Andrei Alexandrescu adalah legenda nyata. Ini adalah orang yang telah memberikan kontribusi signifikan pada sejarah bahasa pemrograman modern dan teknik pemrograman umum dan metaprogram. Berapa banyak salinan yang terpecah dalam diskusi
Desain C ++ Modern dan
Standar Pengkodean (ditulis dengan Sutter's C ++ Coat of Arms) yang luar biasa, dan
buku serta artikel lainnya . Sebagai rekan penulis
bahasa D , ia memiliki kesempatan tidak hanya untuk berteori, tetapi juga untuk membuat mimpinya menjadi kenyataan - dan, yang merupakan karakteristik, ia
diwujudkan .
Sekarang Anda memegang
laporan dari konferensi DotNext 2018 Piter, yang membahas tentang teknologi pengoptimalan modern. Apa hubungannya dengan .NET? Ini adalah laporan mendasar dari seseorang yang telah mengoptimalkan seluruh hidupnya. Jika kinerja penting bagi Anda, Anda perlu melihatnya (atau membaca artikel ini). Selamat datang di kucing!
Seni benchmarking
Saya ingin membahas dengan Anda beberapa topik yang berkaitan dengan pembandingan. Untuk memulai, mari kita ulangi beberapa hal dasar.
Hukum Amdahl adalah bagian dari ilmu komputer klasik, terutama digunakan dalam komputasi paralel, tetapi bekerja dalam sistem yang kompleks. Jika kita ingin meningkatkan kerja sistem tertentu, maka kita harus mulai dari mana masalah utama sistem ini terkonsentrasi. Undang-undang itu sendiri jelas: jika komponen adalah 20% dari sistem, maka peningkatan maksimum dalam kinerja sistem yang dapat dicapai dengan mengoptimalkan operasi hanya komponen ini adalah 20%. Terlalu sering saya harus bertemu orang (tentu saja, pembaca kami bukan milik mereka) yang melakukan hal-hal seperti mengoptimalkan penguraian baris perintah. Operasi ini mengambil 10 mikrodetik pertama dari program Anda, dan orang-orang menganalisis kompleksitas algoritmik mereka dan ngeri jika waktu kuadratik.
Seperti yang mungkin Anda ketahui, sebelum memulai optimasi, perlu membuat profil aplikasi dan memilih hot spot di dalamnya. Di sini harus dikatakan tentang
hukum Ladma (ini bukan nama asli, dan Amdal, baca mundur). Anda perlu memusatkan upaya Anda pada komponen yang mengarah pada investasi waktu terbesar. Itu perlu dipindahkan di luar aplikasi, melakukan pekerjaan yang diperlukan, kembali dan menguji lagi. Alasan Anda perlu melakukan ini adalah karena sangat sering peningkatan kinerja 20% adalah hasil dari sepuluh peningkatan 2%. Dan dalam kerangka sistem besar, tidak mungkin untuk mengukur peningkatan sekecil itu. Untuk ini, komponen harus diuji dalam test suite. Peningkatan 20% dalam kinerja salah satu komponen utama sistem dapat berarti peningkatan 5% untuk sistem secara keseluruhan, dan untuk beberapa area ini adalah hasil yang sangat baik. Jangan lupa bahwa optimasi dapat memiliki sejumlah efek global, jadi berdasarkan hasil benchmarking selektif, Anda harus sangat berhati-hati dalam menarik kesimpulan tentang operasi sistem secara keseluruhan.
Sebuah kesalahan yang saya yakin tidak dilakukan oleh pembaca kami, tetapi yang umumnya cukup umum: orang mengukur kecepatan perakitan debugging. Ini seharusnya tidak pernah dilakukan. Ini mirip dengan kesal karena kecepatan rendah siput di balapan: tidak dimaksudkan untuk kompetisi seperti itu, ia memiliki tujuan lain dalam hidup. Kesalahan lain, agak kurang jelas: orang pertama mengukur kinerja dasar sistem, dan segera setelah itu melakukan benchmarking. Tetapi setelah mengumpulkan garis dasar, banyak sumber daya yang dihangatkan. Misalnya, file yang terbuka buffered dan tetap di memori (setidaknya di Linux). Dengan demikian, tes kedua akan lebih cepat hanya karena diluncurkan setelah yang pertama. Ini terjadi bahkan dengan panggilan malloc. Setelah panggilan ini, sistem tidak kembali ke kondisi semula meskipun panggilan pelepasan memori dilakukan. Konfigurasi internal, caching, dan fitur yang digunakan oleh pengalokasi memori memungkinkan panggilan malloc berikut berjalan lebih cepat. Bahkan tanpa memperhitungkan efek cache, malloc ingat bahwa, misalnya, beberapa fungsi mengalokasikan memori untuk objek sebanyak 4 kilobyte berkali-kali, yang berarti Anda harus memiliki daftar bebas dengan ukuran elemen 4 kilobyte. Atau contoh lain: Pencarian DNS di-cache untuk digunakan kembali setelah permintaan pertama. Jika memungkinkan, selama penentuan tolok ukur, Anda harus memulai ulang seluruh proses setiap saat, dari awal hingga selesai.
Misalnya, untuk benar-benar mengembalikan sistem ke keadaan semula, dalam hal file, mereka harus dibuka pada disk terpisah, yang, setelah tes selesai, harus dihapus (seperti yang saya mengerti, ini dapat dilakukan di Windows). Operasi tidak mudah, tetapi dalam banyak kasus diperlukan.
Melanjutkan percakapan tentang kesalahan selama optimasi, saya harus berurusan dengan kasus-kasus seperti itu ketika biaya printf termasuk dalam hasil pengujian. Ada kesalahan prosedural ketika lebih dari satu hal diubah sebelum setiap pengukuran, yang melanggar prinsip paling dasar dari eksperimen ilmiah, karena tidak jelas efek mana yang Anda ukur. Kesalahan serius lainnya adalah ketika beberapa kasus langka dioptimalkan, yang mengarah ke pesimisasi dalam situasi lain.
Berikut ini adalah contoh dengan Stack Overflow. Penulis sering mengurutkan data yang sudah diurutkan dan terkejut, karena fungsi `is_sorted 'jelas lebih cepat daripada' sort. Lalu mengapa di `sortir baris pertama tidak` jika is_sorted kembali? Anda mengoptimalkan kasus yang sangat jarang, data yang diurutkan sepenuhnya, dan semua orang yang memiliki setidaknya satu elemen yang tidak diurutkan harus menanggung biaya optimasi ini. Ini tidak layak dilakukan.
Saya pikir saya tidak perlu membuktikan untuk waktu yang lama bahwa arsitektur yang bersaing hari ini sangat kompleks: perubahan frekuensi dinamis, gangguan oleh proses lain, virtualisasi, dll. Karena itu, hampir tidak mungkin untuk mendapatkan waktu yang sama saat mengukur, indikator Anda akan selalu bergetar. Karena itu, seseorang tidak boleh mengandalkan hal-hal yang tampak jelas. Katakanlah, mungkin tampak jelas bagi kita bahwa lebih sedikit instruksi berarti kode lebih cepat, dan ini tidak selalu benar. Mungkin juga terlihat bahwa menggunakan data yang tersimpan akan selalu lebih cepat daripada melakukan kembali perhitungan, jadi jika Anda menyimpan hasilnya, Anda akan baik-baik saja. Seperti dalam kasus sebelumnya, itu tidak dapat dinyatakan dengan tegas, seperti halnya sebaliknya tidak dapat dinyatakan tanpa syarat - itu semua tergantung pada konteksnya. Jelas Anda seharusnya hanya memiliki satu hal: semuanya perlu diukur. Jika Anda mengukur semuanya, Anda akan mendapatkan hasil yang lebih baik daripada para ahli dengan pengetahuan yang tidak melakukan pengukuran.
Ada sejumlah praktik yang cukup andal, yang pembahasannya dapat mengarahkan Anda ke pemikiran yang menarik. Kita harus mulai dengan fakta bahwa matematika tidak akan mengecewakan Anda. Memungkinkan untuk menunjukkan bahwa sistem dengan kecepatan yang berbeda dapat setara. Matematika memberikan aturan untuk menunjukkan kesetaraan beberapa hal dan mengidentifikasi beberapa sifat, dan meskipun tidak bias, tidak masalah hal-hal mana yang menarik dan mana yang tidak. Banyak orang berpikir bahwa optimasi didasarkan pada pengetahuan tentang kode mesin dan bekerja dengan bit, tetapi sebenarnya memiliki banyak matematika, karena Anda membuktikan bahwa sistem yang lebih cepat setara dengan yang lebih lambat.
Aturan umum lainnya adalah bahwa komputer suka hal-hal yang membosankan. Apakah Anda perlu mengalikan satu sama lain dengan dua vektor, masing-masing satu miliar elemen? Ini adalah tugas yang ideal untuk komputer, semua peralatan di dalamnya secara khusus dipertajam untuk tugas-tugas semacam ini. Untuk menganalisis data ini, berdasarkan pada mereka untuk membangun ekspresi reguler - Saya tidak ingin melakukan ini. Komputer tidak suka hal-hal seperti cabang, dependensi, panggilan tidak langsung, singkatnya - mereka tidak suka kode pintar, mereka suka kode membosankan. Komputer tidak menyukai perekaman tidak langsung - masalah rumit yang orang-orang yang terlibat dalam zat besi telah berjuang dengan untuk waktu yang lama dan tidak dapat menyelesaikannya.
Aturan lain adalah bahwa Anda harus memberikan preferensi untuk operasi yang paling tidak kuat, dengan kata lain, lebih memilih penambahan untuk perkalian, dan perkalian untuk eksponensial. Sekali lagi, matematika bermanfaat di sini.
Akhirnya, aturan terakhir - semakin kecil, semakin indah. Ukurannya yang kecil memungkinkan komputer untuk menyadari keunggulannya, karena mereka lebih suka bahwa data, dan terutama instruksinya, dekat satu sama lain. Hasil beberapa pengukuran kecepatan aplikasi akan selalu berbeda, Anda akan memiliki beberapa distribusi hasil. Biasanya kami hanya mengambil rata-rata beberapa hasil ini. Tetapi masalahnya adalah karena spesifikasi komputer, rata-rata akan mencakup banyak kebisingan. Ketika Bill Gates mengendarai bus, rata-rata, setiap penumpang di dalam bus adalah miliarder. Kedengarannya hebat, tetapi sedikit kenyamanan bagi orang tunawisma naik bus yang sama. Situasi serupa terjadi dengan gangguan: operasi multiplikasi membutuhkan nanodetik, tetapi ketika Anda melakukan banyak pengukuran operasi seperti itu, salah satunya pasti akan mengalami gangguan dua milidetik. Perbedaannya adalah tiga urutan besarnya, namun, pengembang tidak selalu mempertimbangkan ini.
Jadi, saya ulangi: kebisingan di komputer selalu aditif; untuk orang-orang, ini mungkin tampak tidak signifikan, tetapi untuk microbenchmarking itu penting, dan rata-rata aritmatika akan mencakup banyak suara. Alih-alih rata-rata, Anda memerlukan indikator yang hanya mengukur waktu yang dapat Anda pengaruhi. Jika kita mendekati masalah ini dari sudut pandang matematika, kita akan melihat bahwa kita perlu menemukan nilai yang sesuai dengan jumlah pengukuran terbesar yang telah kita buat. Dengan kata lain, kita membutuhkan mod. Ini segera membawa kita ke masalah: apa yang terjadi jika Anda mengambil mod quicksort? Jika algoritma ini probabilistik atau jika datanya acak, maka hampir tidak akan pernah ada mode. Kepadatan nilai akan hampir sama di seluruh spektrum. Dalam hal ini, kami hanya membuang 5% dari pengukuran terbesar dan setelah itu kami mengambil nilai rata-rata - atau maksimum, dalam kasus terakhir kami akan memiliki langit-langit yang tidak akan melebihi dalam 95% kasus. Hampir selalu akan ada satu subjek duduk di ruang bawah tanah lama dengan modem lambat, di mana setiap halaman akan dimuat selama satu jam. Manusia murni, kami, tentu saja, bersimpati dengannya, tetapi kami tidak dapat secara teknis membantu semua orang - oleh karena itu, 5% kasus yang tersisa harus diabaikan. Secara umum, ketika memecahkan masalah jaringan, kita sering fokus pada persentil ke-95, karena tidak mungkin untuk fokus pada ke-100. Persentil keseratus akan berarti hasil paling lambat dari semua pengukuran yang dikumpulkan - ini tidak informatif.
Ganti cabang dengan aritmatika
Bagaimana, saya harap, menjadi jelas bahwa pengukuran bukanlah masalah yang mudah. Mari kita lihat beberapa contoh dan mulai dengan mencoba mengganti percabangan dengan aritmatika. Kita berbicara tentang kasus di mana kita memerlukan pernyataan if, tetapi menggunakannya terlalu sering tidak diinginkan. Sebagai gantinya, kami akan mengintegrasikan hasil cabang sebagai nilai 0/1. Kode akan terlihat linier, komputer hanya perlu melewatinya dari awal hingga akhir, tanpa memikirkan langkah mana yang perlu Anda ambil selanjutnya.
Mari kita coba untuk menyelesaikan masalah berikut: transfer terendah setiap kuartil dari array ke kuartil pertama. Dengan kata lain, array harus dibagi menjadi empat bagian dan nilai minimum setiap bagian harus ditempatkan di awal array.
static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Di atas adalah kode dasar. Ngomong-ngomong, saya dapat dengan bangga melaporkan bahwa saya menerjemahkan contoh-contoh ini ke dalam C #, dan mereka berhasil dikompilasi. Kode itu sendiri cukup sederhana: `m diberikan indeks nilai terkecil dari dua nilai yang terletak di indeks` i dan `j, dan kemudian penugasan serupa diulang dua kali lagi, tergantung pada dua indeks lainnya. Akhirnya, nilai pada indeks `m dibalik dalam array dengan nilai pada indeks` i. Seperti yang Anda lihat, kita memotong array menggunakan empat variabel induktif.
Masalah pengujian algoritma seperti itu akan menarik dan tidak jelas. Kita perlu mengujinya bukan pada satu set data, tetapi pada data yang bisa muncul dalam berbagai kasus. Misalnya, pada data yang tampak seperti pipa organ: pertama-tama meningkat, lalu turun; pada data acak dengan distribusi seragam; pada kumpulan nol dan acak - dari hanya data acak di sini perbedaannya adalah bahwa akan ada banyak nilai duplikat; pada data yang sudah disortir; akhirnya, pada data yang diperoleh dengan pengukuran nyata dari beberapa fenomena fisik. Ini akan menjadi pendekatan yang serius untuk mengukur kecepatan suatu algoritma, dan secara umum diterima di antara orang-orang yang mempelajari algoritma.
Mari kita coba perbaiki kode yang baru saja kita temui.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Sebagai optimasi pertama, kami akan mencoba untuk menghindari pengulangan operasi yang berlebihan, untuk ini kami mengambil beberapa operasi divisi dari loop - membagi `n oleh 2 dan 4 dan membagi 3 *` n oleh 4. Tetapi setelah optimasi ini, kami menemukan bahwa perhitungan bukan untuk kami masalah utama: kode tidak akan menjadi lebih cepat, meskipun akan lebih kompak. Dalam kasus terbaik, kami akan mencapai peningkatan setengah persen.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Perubahan kedua yang akan kita lakukan pada kode adalah mengurangi ketergantungan. Dalam versi algoritma sebelumnya, menetapkan `m to` k atau` l tergantung pada nilai yang diberikan pada baris `m di atas. Untuk mengurangi jumlah dependensi `m, kami menghitung secara terpisah` m0 dan `m1, lalu membandingkannya. Ketika saya melakukan optimasi ini, saya berharap untuk peningkatan yang signifikan dalam kecepatan algoritma, tetapi pada akhirnya ternyata nol. Tapi, menurut saya, penting untuk menjaga jumlah dependensi seminimal mungkin, karena itu saya menyimpan kode.
static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Mari kita coba mengurangi jumlah variabel induktif dari empat menjadi satu, dan kita akan menghitung tiga yang tersisa secara hitung, karena mereka berada dalam hubungan yang konstan satu sama lain. Ini cukup sederhana: alih-alih `k, kita akan memiliki` i + q, alih-alih dua variabel lainnya - `i + 2 * q dan` i + 3 * q. Saya juga memiliki harapan tinggi untuk pengoptimalan ini, tetapi, seperti yang sebelumnya, itu tidak memberikan hasil dalam waktu. Ini lagi membuktikan pentingnya pengukuran: tanpa mereka saya dapat menyombongkan diri bahwa saya telah meningkatkan operasi algoritma secara signifikan, dan saya akan memiliki argumen yang sangat signifikan.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Sebagai upaya keempat, kami menyusun kembali siklus untuk menghilangkan multiplikasi dengan 3. Ini akan memberi kami peningkatan sebesar 3%. Hasilnya masih tidak mengesankan. Selanjutnya, cobalah untuk menyingkirkan operator ternary.
Untuk melakukan ini, saya ingin memperkenalkan Anda ke fungsi baru - `static int opsional (flag bool, nilai int). Ini mengubah nilai input Boolean ke Int32, mengalikan dengan -1 dan meneruskannya ke operator bitwise DAN bersama dengan nilai input kedua. Jika flag input salah, maka di int32 akan menjadi 0, dan setelah semua konversi pada output kita masih akan mendapatkan 0. Jika flag input benar, di int32 itu akan 1, ketika dikalikan dengan -1 kita mendapatkan FFFFFFFF, yang setelah bit "Dan" dengan nomor apa pun akan memberikan angka kedua ini. Harap dicatat bahwa tidak ada pernyataan if di mana pun, kodenya tanpa percabangan, itu membosankan untuk komputer (meskipun tampaknya rumit bagi kami).
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Kami akan mengganti operator ternary dengan fungsi opsional ini, kami akan mengintegrasikannya di dalam perhitungan. Kami menerapkannya dua kali, dan dalam kasus ketiga, tinggalkan tanda tanya. Jadi, alih-alih empat cek dalam siklus ini, saya hanya akan memiliki satu cek.
Dari hasil pengukuran yang Anda lihat pada slide, jelas betapa pentingnya menguji algoritma pada beberapa set data yang berbeda. Pada satu set kita tidak akan mengerti apa-apa. Pada data acak dan nyata, kami memiliki lebih dari dua kali lipat percepatan, pada pipa organ dan data yang diurutkan, kami mengalami sedikit perlambatan. Hal ini disebabkan oleh fakta bahwa dalam kasus data yang diurutkan untuk prediktor transisi tidak akan ada kejutan, itu akan memprediksi dengan akurasi 100%. Dalam kasus pipa organ, kita akan memiliki satu prediksi yang salah di tengah kumpulan data - sekali lagi, akurasi yang sangat tinggi. Sebaliknya, dengan data acak, perbedaan antara dua pendekatan kami akan sangat besar. Kami mengganti semua cek yang tidak dapat diprediksi dengan logika sederhana. Di sini kita kembali ke kebenaran sederhana: komputer dirancang untuk komputasi, seperti namanya (komputer - komputasi). Bercabang, menampilkan gambar di layar - semua ini kinerjanya jauh lebih buruk. Melakukan bitwise "Dan" bagi mereka jauh lebih sederhana daripada melewati pernyataan if.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } }
Setelah akhirnya mencapai hasil positif dari optimasi, kami akan mencoba mengganti operator ternary terakhir dengan fungsi kami `opsional. Kali ini kenaikan kecepatan akan kecil. Untuk memahami mengapa ini terjadi, Anda perlu melihat kode yang dihasilkan. Dalam versi kode sebelumnya, di mana tanda tanya masih ada, kompiler sudah menemukan cara untuk mengeksekusi kode tanpa bercabang. Dan ketika dia sampai ke operator ternary, dia sudah bisa memperkirakannya. Mengganti bagian terakhir ini dengan `opsional akan menghasilkan kode yang agak lebih buruk. Karena itu, saya ulangi, penting untuk melakukan pengukuran setiap waktu.
Fitur lain yang ingin saya rekomendasikan kepada Anda adalah `ifelse tanpa cabang, yang sekarang Anda lihat di layar. Benar, saya tidak dapat mencapai dengan itu peningkatan kinerja dalam contoh kita. Jika 0 dilewatkan sebagai bendera untuk itu, baris pertama adalah 0; dalam yang kedua, kita kurangi 1 dari 0 di Int32 dan dapatkan FFFFFFFF, setelah itu nilai ini diteruskan ke bitwise “Dan” bersama dengan argumen fungsi `v2, yang akan memberi kita argumen ini sendiri tanpa perubahan; akhirnya, baris pertama dan kedua diteruskan ke bitwise "OR", yang, sekali lagi, akan memberi kita `v2. Jika flagnya 1, maka baris pertama akan sama dengan `v1; dalam yang kedua, kita kurangi 1 dari 1 dan dapatkan 0, akibatnya seluruh baris akan menjadi 0, dan 0 dan `v1 dalam bitwise 'OR' akan memberikan` v1.
Saya berharap bahwa `ifelse tanpa fungsi percabangan akan menarik minat orang-orang yang terlibat dalam backend - untuk saat ini, kompiler modern karena alasan tertentu tidak menggunakan pendekatan ini. Dengan fungsi-fungsi ini, Anda dapat mengatur ulang algoritma sehingga kompiler memahaminya untuk Anda, karena Anda lebih pintar dan lebih kreatif daripada kompiler Anda.
Persimpangan set besar
Ubah topik pembicaraan kita sedikit dan lanjutkan ke persimpangan set besar. Sampai sekarang, kita telah berbicara tentang masing-masing operator, sekarang kita akan membuat algoritma baru, jadi kita perlu mengalihkan perhatian dari detail dan membuka pikiran kita ke perspektif yang lebih besar. Saya berasumsi bahwa Anda sudah terbiasa dengan menggabungkan gabungan, gandakan dua vektor, dan mencari elemen umum dari dua vektor diurutkan. Dua set yang diurutkan dilintasi, dan ketika elemen yang sama berada di dalamnya, ini dianggap sebagai kecocokan. Jika salah satu dari dua elemen yang dibandingkan lebih kecil, itu bergeser. Algoritma ini cukup sederhana, tetapi sangat umum - kemungkinan besar yang paling banyak digunakan di dunia. Ini digunakan dalam semua pertanyaan dari beberapa kata, setiap query seperti itu adalah persimpangan dari dua set. Algoritma ini, khususnya, menggunakan Google, dan juga harus diterapkan di semua kueri basis data.
int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; }
Lihatlah implementasi dasar dari algoritma ini. Jika kedua set input kosong, maka, jelas, kami mengembalikan 0. Selanjutnya, kami memulai loop tak terbatas, di mana, jika ada kecocokan, kami meningkatkan hasilnya dengan 1 dan memeriksa apakah siklus harus diselesaikan. Alih-alih infinite loop, seseorang bisa menggunakan pernyataan for dan menentukan kondisi untuk mengakhiri loop di dalamnya. Tapi itu berarti kerja ekstra. Dalam implementasi yang Anda lihat pada slide, di cabang pertama kita memiliki `if (a1 [i1] <a2 [i2]), setelah itu ada peningkatan` i1 oleh 1, dan kita hanya dapat memeriksa `i1. Demikian pula, di cabang kedua kita hanya perlu memeriksa `i2. Kedua nilai harus diperiksa hanya di cabang ketiga. Jika pemeriksaan ini di awal siklus, maka kami akan melakukan pekerjaan ekstra.
Mari kita coba untuk meningkatkan implementasi ini. Saat ini, kompleksitas algoritmiknya linear, tergantung pada dua argumen input. Dalam pembelajaran mesin, cukup sering kita harus menemukan persimpangan set yang sangat berbeda satu sama lain dalam ukuran atau dalam statistik. Misalnya, Anda memiliki vektor input panjang dan vektor fitur pendek yang Anda periksa. Dalam kode kami, mungkin ada sejuta catatan di `a1, dan seribu di` a2. Dalam hal ini, kami tidak siap untuk melakukan jutaan langkah untuk menyelesaikan algoritme ini. Beban terbesar di sini adalah pada baris kode berikut: `if (++ i1 == a1.length) putus. Tepat sebelum ini, perbandingan terjadi, dan kemudian di baris ini ada peningkatan nilai; ini, pada dasarnya, adalah pencarian linier. Kami beralih pada vektor panjang untuk mencari elemen yang pendek. Dalam kasus terburuk, kami akan melakukan banyak pencarian seperti itu, perlahan-lahan bergerak di sepanjang vektor.
Mari kita coba tingkatkan algoritma ini. Nah, jika bukan pencarian linear, maka biner lebih baik, bukan? Mari kita gunakan biner. Keuntungannya adalah memberikan indeks elemen terbesar yang lebih kecil.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; }
Kode di atas adalah implementasi dari algoritma pencarian biner kami. Tetapi itu tidak terlalu efektif. Situasi terburuk di sini adalah ketika pencarian biner akan gagal setiap saat. Dan itu akan muncul dalam skenario yang cukup penting - misalnya, ketika kedua set identik. Anda, seperti orang bodoh, memotong lingkaran dengan pencarian biner, sementara Anda hanya harus melalui algoritma linier pertama. Mengapa pencarian biner, ketika item yang diinginkan - setiap kali di sini, yang pertama dalam daftar?
Bagaimana cara membuat algoritma bekerja dengan sukses pada data yang identik dan berbeda? Memeriksa semua data akan terlalu mahal untuk sumber daya. Saya akan membuat reservasi bahwa ini bukan tentang data yang benar-benar identik, tetapi sangat mirip, dengan statistik yang sama, ukurannya juga dapat bervariasi. Anda dapat memeriksa beberapa item berikut. Solusi yang jelas adalah mengurangi pencarian Anda. Ketika kami melakukan pencarian biner, maka, setelah menemukan beberapa elemen, kami tidak lagi tertarik pada elemen yang lebih kecil darinya, karena vektor kedua juga diurutkan. Dengan demikian, kami dapat setiap kali mengurangi area pencarian kami, membuang semua elemen lebih sedikit dari elemen yang ditemukan.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; }
Inilah implementasi dari pendekatan ini. Anda melihat bahwa kami melakukan pencarian biner setiap kali untuk bagian dari array asli dimulai dengan `i2 dan diakhiri dengan` a2.length. Karena `i2 akan meningkat dengan setiap pencarian, area pencarian akan berkurang.
Optimasi berikutnya yang ingin saya terapkan di sini terkait dengan algoritma Pencarian Galloping. Intinya, ini adalah pencarian biner dengan langkah berbeda. Dalam hal pencarian biner, kami memulai setiap saat dari tengah - tetapi mari kita pikirkan ketika kami mencari nama di buku telepon, kami tidak membukanya di tengah? Jika nama seseorang dimulai, misalnya, pada "B", kami akan membuka buku lebih dekat ke awal. Prinsip ini diimplementasikan dalam pencarian berderap: kita mulai merayapi data dalam arah naik dengan langkah meningkat secara eksponensial setelah setiap pemeriksaan: pertama 1, lalu 2, lalu 4. Ini memberi kita kompleksitas algoritme yang baik. Jika langkahnya tumbuh secara linear, kompleksitasnya akan kuadratik. Ketika kita "melompat" elemen yang kita cari, kita melakukan pencarian biner normal pada segmen yang tersisa, yang akan kecil dan tidak akan secara signifikan mempengaruhi waktu eksekusi algoritma. Dengan demikian, kami menggabungkan semua keunggulan dari kedua pendekatan. Penerapan algoritma semacam itu:
int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; }
Kita sekarang membahas penskalaan, yaitu, mencoba menemukan persimpangan lebih dari dua set. Untuk setiap pencarian beberapa kata, kita perlu menemukan persimpangan beberapa set. Untuk melakukan ini, kita dapat, misalnya, membandingkan dua set pertama, lalu perpotongan mereka dengan yang ketiga dan seterusnya. Tapi ini bukan solusi optimal. Kita perlu mengambil elemen pertama dari semua set dan menemukan yang terkecil dari mereka, yang kemudian perlu dipindahkan. Kita membutuhkan struktur data yang memungkinkan kita menemukan elemen terkecil dari banyak elemen dan memiliki kompleksitas konstan. Struktur data seperti itu banyak. Tapi itu akan menjadi banyak yang aneh, itu tidak akan didasarkan pada array fisik. Itu akan menjadi imajiner, kita akan mengatur di dalamnya hanya elemen pertama dari set kita. Setelah kami menemukan elemen terkecil di heap, kami masih dapat mencari semua set lainnya.
Bekerja pada topik yang kita diskusikan dalam praktik hari ini memiliki bentuk yang agak artisanal. Dalam praktiknya, kita paling sering memiliki beberapa set, bukan hanya dua, dan cukup banyak pekerjaan telah ditulis tentang topik ini. Algoritma klasik di sini adalah SVS, di mana kami mengelompokkan set, mengambil dua yang terkecil dan memilih yang terpendek sebagai kandidat.
Di sini Anda dapat menemukan gambaran umum yang baik tentang topik ini. Masalah yang terkait dengan set berpotongan, produk skalar vektor jarang, menyortir dengan menggabungkan, segala bentuk perbandingan dengan gambar dari waktu ke waktu menjadi lebih dan lebih menarik. Algoritma yang saya tunjukkan telah memantapkan dirinya sebagai sangat berguna. Terima kasih atas perhatian anda
Andrei Alexandrescu tidak akan datang ke DotNext 2018 Moskow, tetapi Jeffrey Richter, Greg Young, Pavel Yosifovich dan lainnya akan ada di sana. Nama-nama pembicara dan topik-topik laporan dapat ditemukan di sini , dan tiket di sini . Bergabunglah sekarang!