Algoritme seperti apa yang membutuhkan satu set?

Pada kursus pemrograman pertama saya, saya diberitahu bahwa saya harus menggunakan set kapan pun saya perlu melakukan hal-hal seperti menghapus duplikat sesuatu. Misalnya: untuk menghapus semua duplikat dari vektor, beralih melalui vektor tersebut dan tambahkan masing-masing elemen ke set, lalu Anda pergi dengan kejadian unik. Namun, saya juga bisa melakukannya dengan menambahkan setiap elemen ke vektor lain dan memeriksa apakah elemen sudah ada. Saya berasumsi bahwa tergantung pada bahasa yang digunakan mungkin ada perbedaan dalam kinerja. Tetapi apakah ada alasan untuk menggunakan set selain itu?

Pada dasarnya: jenis algoritme apa yang membutuhkan satu set dan tidak boleh dilakukan dengan jenis wadah lainnya?

Anda bertanya tentang set secara spesifik tetapi saya pikir pertanyaan Anda adalah tentang konsep yang lebih besar: abstraksi. Anda sepenuhnya benar bahwa Anda dapat menggunakan Vector untuk melakukan ini (jika Anda menggunakan Java, gunakan ArrayList sebagai gantinya.) Tetapi mengapa berhenti di situ? Untuk apa Anda membutuhkan vektor? Anda dapat melakukan ini semua dengan array.

Saat Anda perlu menambahkan item ke array, Anda dapat dengan mudah mengulang setiap elemen dan jika tidak ada di sana, Anda menambahkannya di akhir. Tapi, sebenarnya, Anda perlu memeriksa dulu apakah ada ruang di array. Jika tidak ada, Anda harus membuat array baru yang lebih besar dan menyalin semua elemen yang ada dari array lama ke array baru dan kemudian Anda dapat menambahkan elemen baru. Tentu saja, Anda juga perlu memperbarui setiap referensi ke array lama untuk menunjuk ke yang baru. Sudah selesai? Bagus! Sekarang apa yang ingin kita capai lagi?

Atau, sebagai gantinya Anda bisa menggunakan contoh Set dan panggil saja add(). Alasan yang ada set adalah bahwa mereka adalah abstraksi yang berguna untuk banyak masalah umum. Misalnya, katakanlah Anda ingin melacak item dan bereaksi ketika yang baru ditambahkan. Anda memanggil add()satu set dan itu kembali trueatau falseberdasarkan pada apakah set itu dimodifikasi. Anda bisa menulis itu semua dengan tangan menggunakan primitif tetapi mengapa?

Mungkin sebenarnya ada kasus di mana Anda memiliki Daftar dan Anda ingin menghapus duplikat. Algoritma yang Anda usulkan pada dasarnya adalah cara paling lambat yang bisa Anda lakukan. Ada beberapa cara umum yang lebih cepat: mengaitkannya atau menyortirnya. Atau, Anda bisa menambahkannya ke set yang mengimplementasikan salah satu dari algoritma tersebut.

Di awal karir / pendidikan Anda fokusnya adalah pada pengembangan algoritma ini dan memahaminya dan penting untuk melakukannya. Tapi bukan itu yang dilakukan pengembang profesional secara normal. Mereka menggunakan pendekatan ini untuk membangun hal-hal yang jauh lebih menarik dan menggunakan implementasi yang dibangun sebelumnya dan andal menghemat banyak waktu.

Saya berasumsi bahwa tergantung pada bahasa yang digunakan mungkin ada perbedaan dalam kinerja. Tetapi apakah ada alasan untuk menggunakan set selain itu?

Oh ya, (tapi itu bukan kinerja.)

Gunakan set ketika Anda dapat menggunakannya karena tidak menggunakannya berarti Anda harus menulis kode tambahan. Menggunakan set membuat apa yang Anda lakukan mudah dibaca. Semua pengujian untuk logika keunikan disembunyikan di tempat lain di mana Anda tidak perlu memikirkannya. Itu di tempat yang sudah diuji dan Anda bisa percaya itu berhasil.

Tulis kode Anda sendiri untuk melakukan itu dan Anda harus khawatir. Bleh. Siapa yang mau melakukan itu?

Pada dasarnya: jenis algoritme apa yang membutuhkan satu set dan tidak boleh dilakukan dengan jenis wadah lainnya?

Tidak ada algoritma yang "tidak boleh dilakukan dengan jenis wadah lain". Hanya ada algoritma yang dapat memanfaatkan set. Sangat menyenangkan ketika Anda tidak perlu menulis kode tambahan.

Sekarang tidak ada yang khusus tentang set dalam hal ini. Anda harus selalu menggunakan koleksi yang paling sesuai dengan kebutuhan Anda. Di java saya menemukan gambar ini sangat membantu dalam membuat keputusan itu. Anda akan melihat bahwa ia memiliki tiga jenis set yang berbeda.

Dan sebagaimana @germi tunjukkan dengan benar, jika Anda menggunakan koleksi yang tepat untuk pekerjaan itu, kode Anda menjadi lebih mudah dibaca orang lain.

Namun, saya juga bisa melakukannya dengan menambahkan setiap elemen ke vektor lain dan memeriksa apakah elemen sudah ada.

Jika Anda melakukan itu, maka Anda menerapkan semantik satu set di atas struktur data vektor. Anda sedang menulis kode tambahan (yang bisa mengandung kesalahan), dan hasilnya akan sangat lambat jika Anda memiliki banyak entri.

Mengapa Anda ingin melakukannya dengan menggunakan implementasi set yang ada, teruji, efisien?

Entitas perangkat lunak yang mewakili entitas dunia nyata sering kali ditetapkan secara logis. Misalnya, pertimbangkan sebuah Mobil. Mobil memiliki pengidentifikasi unik dan sekelompok mobil membentuk satu set. Gagasan yang ditetapkan berfungsi sebagai kendala pada pengumpulan Mobil yang mungkin diketahui oleh suatu program dan membatasi nilai data.

Juga, set memiliki aljabar yang sangat baik. Jika Anda memiliki satu set Mobil yang dimiliki oleh George dan satu set yang dimiliki oleh Alice, maka perserikatan jelas merupakan set yang dimiliki oleh George dan Alice bahkan jika George dan Alice keduanya memiliki mobil yang sama. Jadi algoritma yang harus menggunakan set adalah yang mana logika entitas yang terlibat menunjukkan karakteristik set. Itu ternyata sangat umum.

Bagaimana set diimplementasikan dan bagaimana kendala keunikan dijamin adalah masalah lain. Seseorang berharap dapat menemukan implementasi yang sesuai untuk himpunan logika yang menghilangkan duplikat mengingat set itu sangat mendasar untuk logika, tetapi bahkan jika Anda melakukan implementasi sendiri, jaminan keunikan adalah intrinsik untuk penyisipan item dalam set dan Anda tidak harus "memeriksa apakah elemen sudah ada".

Terlepas dari karakteristik kinerja (yang sangat signifikan, dan seharusnya tidak mudah diabaikan), Sets sangat penting sebagai koleksi abstrak.

Bisakah Anda meniru perilaku Set (mengabaikan kinerja) dengan Array? Ya, tentu saja! Setiap kali Anda menyisipkan, Anda dapat memeriksa apakah elemen tersebut sudah ada dalam array, dan kemudian hanya menambahkan elemen jika belum ditemukan. Tapi itu adalah sesuatu yang secara sadar Anda harus sadari, dan ingat setiap kali Anda memasukkan ke dalam Array-Psuedo-Set Anda. Oh apa itu, Anda dimasukkan sekali secara langsung, tanpa terlebih dahulu memeriksa duplikat? Nah, array Anda telah merusak invariannya (bahwa semua elemen unik, dan setara, tidak ada duplikat).

Jadi apa yang akan Anda lakukan untuk menyiasatinya? Anda akan membuat tipe data baru, sebut saja (katakanlah PsuedoSet), yang membungkus array internal, dan memperlihatkan insertoperasi secara publik, yang akan menegakkan keunikan elemen. Karena array yang dibungkus hanya dapat diakses melalui insertAPI publik ini , Anda menjamin bahwa duplikat tidak akan pernah terjadi. Sekarang tambahkan beberapa hashing untuk meningkatkan kinerja containspemeriksaan, dan cepat atau lambat Anda akan menyadari bahwa Anda menerapkan sepenuhnya Set.

Saya juga akan menanggapi dengan pernyataan dan pertanyaan lanjutan:

Pada kursus pemrograman pertama saya, saya diberitahu bahwa saya harus menggunakan Array setiap kali saya perlu melakukan hal-hal seperti menyimpan beberapa elemen yang dipesan dari sesuatu. Misal: untuk menyimpan koleksi nama rekan kerja. Namun, saya juga bisa melakukannya dengan mengalokasikan memori mentah, dan mengatur nilai alamat memori yang diberikan oleh pointer awal + beberapa offset.

Bisakah Anda menggunakan pointer mentah dan memperbaiki offset untuk meniru Array? Ya, tentu saja! Setiap kali Anda memasukkan, Anda dapat memeriksa apakah offset tidak berkeliaran di ujung memori yang dialokasikan. Tetapi itu adalah sesuatu yang secara sadar Anda harus sadari, dan ingat setiap kali Anda memasukkan ke dalam Pseudo-Array Anda. Oh apa itu, Anda memasukkan satu kali secara langsung, tanpa terlebih dahulu memeriksa offset? Nah, ada kesalahan Segmentasi dengan nama Anda di atasnya!

Jadi apa yang akan Anda lakukan untuk menyiasatinya? Anda akan membuat tipe data baru, menyebutnya (katakanlah PsuedoArray), yang membungkus penunjuk dan ukuran, dan mengekspos insertoperasi secara publik, yang akan memastikan bahwa offset tidak melebihi ukuran. Karena data yang dibungkus hanya dapat diakses melalui insertAPI publik ini , Anda menjamin bahwa tidak ada buffer overflow yang dapat terjadi. Sekarang tambahkan beberapa fungsi kenyamanan lainnya (mengubah ukuran array, penghapusan elemen, dll.), Dan cepat atau lambat Anda akan menyadari bahwa Anda menerapkan sepenuhnya Array.

Ada semua jenis algoritma berbasis set, terutama di mana Anda perlu melakukan persimpangan dan serikat set dan hasilnya hasilnya berupa set.

Algoritme berbasis set banyak digunakan dalam berbagai algoritma pencarian jalur, dll.

Untuk primer tentang teori himpunan, periksa tautan ini: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

Jika Anda perlu mengatur semantik, gunakan satu set. Ini akan menghindari bug karena duplikat palsu karena Anda lupa memangkas vektor / daftar pada tahap tertentu, dan itu akan lebih cepat daripada yang dapat Anda lakukan dengan terus-menerus memangkas vektor / daftar Anda.

Saya benar-benar menemukan kontainer standar kebanyakan tidak berguna dan saya lebih suka menggunakan array tetapi saya melakukannya dengan cara yang berbeda.

Untuk menghitung set persimpangan, saya beralih melalui array pertama dan tandai elemen dengan bit tunggal. Kemudian saya beralih melalui array kedua dan mencari elemen yang ditandai. Voila, atur persimpangan dalam waktu linier dengan jauh lebih sedikit kerja dan memori daripada tabel hash, misalnya Serikat pekerja dan perbedaan sama-sama mudah diterapkan menggunakan metode ini. Itu membantu bahwa basis kode saya berputar di sekitar elemen pengindeksan daripada menduplikasi mereka (saya menduplikasi indeks ke elemen, bukan data dari elemen itu sendiri) dan jarang membutuhkan apa pun untuk diurutkan, tapi saya belum pernah menggunakan struktur data yang ditetapkan selama bertahun-tahun hasilnya.

Saya juga memiliki beberapa kode C bit-fiddling jahat yang saya gunakan bahkan ketika elemen tidak menawarkan bidang data untuk tujuan tersebut. Ini melibatkan penggunaan memori elemen itu sendiri dengan menetapkan bit paling signifikan (yang tidak pernah saya gunakan) untuk tujuan menandai elemen yang dilalui. Itu sangat menjijikkan, jangan lakukan itu kecuali Anda benar-benar bekerja di tingkat perakitan dekat, tetapi hanya ingin menyebutkan bagaimana hal itu dapat diterapkan bahkan dalam kasus ketika elemen tidak menyediakan beberapa bidang khusus untuk dilalui jika Anda dapat menjamin bahwa bit tertentu tidak akan pernah digunakan. Ini dapat menghitung set persimpangan antara 200 juta elemen (sekitar 2,4 gigs data) dalam waktu kurang dari satu detik pada i7 mungil saya. Coba lakukan persimpangan set antara dua std::setcontoh yang berisi masing-masing seratus juta elemen dalam waktu yang sama; bahkan tidak mendekati.

Selain itu ...

Namun, saya juga bisa melakukannya dengan menambahkan setiap elemen ke vektor lain dan memeriksa apakah elemen sudah ada.

Itu memeriksa untuk melihat apakah suatu elemen sudah ada dalam vektor baru umumnya akan menjadi operasi waktu linier, yang akan membuat persimpangan set itu sendiri operasi kuadratik (jumlah ledakan pekerjaan semakin besar ukuran input). Saya merekomendasikan teknik di atas jika Anda hanya ingin menggunakan vektor atau array tua polos dan melakukannya dengan cara yang skala luar biasa.

Pada dasarnya: jenis algoritme apa yang membutuhkan satu set dan tidak boleh dilakukan dengan jenis wadah lainnya?

Tidak ada jika Anda meminta pendapat bias saya jika Anda membicarakannya di tingkat kontainer (seperti dalam struktur data yang khusus diterapkan untuk menyediakan operasi yang ditetapkan secara efisien), tetapi ada banyak yang memerlukan logika yang ditetapkan pada tingkat konseptual. Sebagai contoh, katakanlah Anda ingin menemukan makhluk di dunia permainan yang mampu terbang dan berenang, dan Anda memiliki makhluk terbang dalam satu set (apakah Anda benar-benar menggunakan wadah set) atau yang dapat berenang di yang lain . Dalam hal ini, Anda ingin persimpangan ditetapkan. Jika Anda ingin makhluk yang bisa terbang atau magis, maka Anda menggunakan serikat pekerja. Tentu saja Anda tidak benar-benar membutuhkan wadah untuk mengimplementasikan ini, dan implementasi paling optimal umumnya tidak membutuhkan atau ingin wadah yang dirancang khusus untuk menjadi sebuah wadah.

Pergi Bersinggungan

Baiklah, saya mendapat beberapa pertanyaan bagus dari JimmyJames mengenai pendekatan persimpangan set ini. Ini agak menyimpang dari subjek tapi oh well, saya tertarik melihat lebih banyak orang menggunakan pendekatan intrusi dasar ini untuk mengatur persimpangan sehingga mereka tidak membangun struktur tambahan seperti pohon biner seimbang dan tabel hash hanya untuk tujuan operasi yang ditetapkan. Seperti disebutkan persyaratan mendasar adalah bahwa daftar elemen copy dangkal sehingga mereka mengindeks atau menunjuk ke elemen bersama yang dapat "ditandai" sebagai dilalui oleh melewati melalui daftar atau array yang tidak disortir pertama atau apa pun untuk kemudian mengambil pada yang kedua melewati daftar kedua.

Namun, ini dapat dicapai secara praktis bahkan dalam konteks multithreading tanpa menyentuh unsur-unsur asalkan:

1. Dua agregat berisi indeks ke elemen.
2. Kisaran indeks tidak terlalu besar (katakan [0, 2 ^ 26), bukan miliaran atau lebih) dan cukup padat ditempati.

Ini memungkinkan kita untuk menggunakan array paralel (hanya satu bit per elemen) untuk tujuan operasi yang ditetapkan. Diagram:

Sinkronisasi utas hanya perlu ada di sana saat memperoleh array bit paralel dari pool dan melepaskannya kembali ke pool (dilakukan secara implisit ketika keluar dari ruang lingkup). Dua loop aktual untuk melakukan operasi yang ditetapkan tidak perlu melibatkan sinkronisasi utas. Kita bahkan tidak perlu menggunakan kumpulan bit paralel jika utas hanya dapat mengalokasikan dan membebaskan bit secara lokal, tetapi kumpulan bit dapat berguna untuk menggeneralisasi pola dalam basis kode yang sesuai dengan jenis representasi data ini di mana elemen pusat sering dirujuk. oleh indeks sehingga setiap utas tidak perlu repot dengan manajemen memori yang efisien. Contoh utama untuk area saya adalah sistem entitas-komponen dan representasi mesh yang diindeks. Keduanya sering perlu mengatur persimpangan dan cenderung merujuk ke segala sesuatu yang disimpan secara terpusat (komponen dan entitas dalam ECS dan simpul, tepi,

Jika indeks tidak padat dan tersebar jarang, maka ini masih berlaku dengan implementasi yang jarang dari array bit / boolean paralel, seperti yang hanya menyimpan memori dalam potongan-potongan 512-bit (64 byte per node yang tidak dikontrol yang mewakili 512 indeks yang berdekatan) ) dan lewati mengalokasikan blok berdekatan yang benar-benar kosong. Kemungkinan Anda sudah menggunakan sesuatu seperti ini jika struktur data pusat Anda jarang ditempati oleh elemen itu sendiri.

... ide serupa untuk bitet yang jarang digunakan sebagai bit array paralel. Struktur-struktur ini juga cenderung tidak berubah karena mudah untuk menyalin blok chunky yang dangkal yang tidak perlu disalin dalam-dalam untuk membuat salinan baru yang tidak dapat diubah.

Sekali lagi mengatur persimpangan antara ratusan juta elemen dapat dilakukan dalam waktu kurang dari satu detik menggunakan pendekatan ini pada mesin yang sangat rata-rata, dan itu dalam satu utas.

Ini juga dapat dilakukan dalam waktu kurang dari setengah jika klien tidak memerlukan daftar elemen untuk persimpangan yang dihasilkan, seperti jika mereka hanya ingin menerapkan beberapa logika ke elemen yang ditemukan di kedua daftar, pada titik mana mereka dapat melewati penunjuk fungsi atau functor atau delegasi atau apa pun untuk dipanggil kembali untuk memproses rentang elemen yang berpotongan. Sesuatu untuk efek ini:

// 'func' receives a range of indices to
// process.
set_intersection(func):
{
    parallel_bits = bit_pool.acquire()

    // Mark the indices found in the first list.
    for each index in list1:
        parallel_bits[index] = 1

    // Look for the first element in the second list 
    // that intersects.
    first = -1
    for each index in list2:
    {
         if parallel_bits[index] == 1:
         {
              first = index
              break
         }
    }

    // Look for elements that don't intersect in the second
    // list to call func for each range of elements that do
    // intersect.
    for each index in list2 starting from first:
    {
        if parallel_bits[index] != 1:
        {
             func(first, index)
             first = index
        }
    }
    If first != list2.num-1:
        func(first, list2.num)
}

... atau sesuatu untuk efek ini. Bagian yang paling mahal dari pseudocode pada diagram pertama adalah intersection.append(index)pada loop kedua, dan itu berlaku bahkan untuk std::vectorukuran daftar yang lebih kecil sebelumnya.

Bagaimana Jika Saya Mendalam Semuanya?

Hentikan itu! Jika Anda perlu melakukan set persimpangan, itu menyiratkan bahwa Anda menduplikasi data untuk berpotongan. Kemungkinannya adalah bahwa objek terkecil sekalipun tidak lebih kecil dari indeks 32-bit. Sangat mungkin untuk mengurangi rentang pengalamatan elemen Anda menjadi 2 ^ 32 (2 ^ 32 elemen, bukan 2 ^ 32 byte) kecuali jika Anda benar-benar membutuhkan lebih dari ~ 4,3 miliar elemen yang dipakai, pada saat itu diperlukan solusi yang sama sekali berbeda ( dan yang pasti tidak menggunakan wadah yang ditetapkan dalam memori).

Kecocokan Kunci

Bagaimana dengan kasus di mana kita perlu melakukan operasi set di mana elemen tidak identik tetapi bisa memiliki kunci yang cocok? Dalam hal itu, ide yang sama seperti di atas. Kami hanya perlu memetakan setiap kunci unik untuk indeks. Jika kuncinya adalah string, misalnya, maka string yang diinternir dapat melakukan hal itu. Dalam kasus tersebut, struktur data yang bagus seperti trie atau tabel hash diperlukan untuk memetakan kunci string ke indeks 32-bit, tetapi kami tidak memerlukan struktur seperti itu untuk melakukan operasi yang ditetapkan pada indeks 32-bit yang dihasilkan.

Banyak solusi algoritmik dan struktur data yang sangat murah dan langsung terbuka seperti ini ketika kita dapat bekerja dengan indeks ke elemen dalam rentang yang sangat wajar, bukan rentang pengalamatan penuh dari mesin, dan sering kali lebih dari layak untuk menjadi dapat memperoleh indeks unik untuk setiap kunci unik.

Saya Suka Indeks!

Saya suka indeks sama seperti pizza dan bir. Ketika saya berusia 20-an, saya benar-benar masuk ke C ++ dan mulai mendesain semua jenis struktur data yang sepenuhnya memenuhi standar (termasuk trik-trik yang terlibat untuk mengaburkan ctor pengisi dari range ctor pada waktu kompilasi). Kalau dipikir-pikir itu buang-buang waktu.

Jika Anda memutar database Anda di sekitar menyimpan elemen-elemen secara terpusat dalam array dan mengindeksnya daripada menyimpannya dengan cara yang terfragmentasi dan berpotensi melintasi seluruh rentang mesin yang dapat ditangani, maka Anda dapat menjelajahi dunia kemungkinan algoritmik dan struktur data hanya dengan menjelajahi mendesain wadah dan algoritma yang berputar di sekitar tua intatau polos int32_t. Dan saya menemukan hasil akhirnya jauh lebih efisien dan mudah dipertahankan di mana saya tidak terus-menerus mentransfer elemen dari satu struktur data ke yang lain ke yang lain.

Beberapa contoh menggunakan kasus ketika Anda bisa mengasumsikan bahwa nilai unik apa pun Tmemiliki indeks unik dan akan memiliki instance yang berada di array pusat:

Jenis radix multithreaded yang bekerja dengan baik dengan bilangan bulat bertanda untuk indeks . Saya sebenarnya memiliki jenis radix multithreaded yang membutuhkan waktu 1/10 dari waktu untuk mengurutkan seratus juta elemen sebagai jenis paralel Intel sendiri, dan Intel sudah 4 kali lebih cepat daripada std::sortuntuk input besar seperti itu. Tentu saja Intel jauh lebih fleksibel karena ini adalah semacam berbasis perbandingan dan dapat mengurutkan hal-hal secara leksikografis, sehingga membandingkan apel dengan jeruk. Tapi di sini saya sering hanya membutuhkan jeruk, seperti saya mungkin melakukan radix sort pass hanya untuk mencapai pola akses memori yang ramah cache atau menyaring duplikat dengan cepat.

Kemampuan untuk membangun struktur terkait seperti daftar tertaut, pohon, grafik, tabel hash rantai terpisah, dll. Tanpa alokasi tumpukan per node . Kami hanya dapat mengalokasikan node dalam jumlah besar, sejajar dengan elemen, dan menghubungkannya bersama dengan indeks. Node itu sendiri hanya menjadi indeks 32-bit ke node berikutnya dan disimpan dalam array besar, seperti:

Ramah untuk pemrosesan paralel. Seringkali struktur yang ditautkan tidak begitu ramah untuk pemrosesan paralel, karena canggung setidaknya untuk mencoba mencapai paralelisme di pohon atau traversal daftar terkait sebagai lawan dari, katakanlah, hanya melakukan paralel untuk loop melalui array. Dengan representasi indeks / array pusat, kita selalu dapat pergi ke array pusat dan memproses semuanya dalam loop paralel chunky. Kami selalu memiliki array pusat dari semua elemen yang dapat kami proses dengan cara ini, bahkan jika kami hanya ingin memproses beberapa (pada titik mana Anda dapat memproses elemen yang diindeks oleh daftar yang diurutkan berdasarkan radix untuk akses yang ramah-cache melalui array pusat).

Dapat mengaitkan data ke setiap elemen dengan cepat dalam waktu konstan . Seperti halnya array paralel bit di atas, kita dapat dengan mudah dan sangat murah mengaitkan data paralel ke elemen untuk, katakanlah, pemrosesan sementara. Ini memiliki kasus penggunaan di luar data sementara. Misalnya, sistem jala mungkin ingin memungkinkan pengguna untuk melampirkan sebanyak peta UV ke jala yang mereka inginkan. Dalam kasus seperti itu, kita tidak bisa hanya kode-keras berapa banyak peta UV akan ada di setiap titik tunggal dan wajah menggunakan pendekatan AoS. Kita harus dapat mengaitkan data tersebut dengan cepat, dan array paralel berguna di sana dan jauh lebih murah daripada jenis apa pun wadah asosiatif canggih, bahkan tabel hash.

Tentu saja array paralel disukai karena sifatnya yang rawan kesalahan menjaga array paralel sinkron satu sama lain. Setiap kali kita menghapus elemen pada indeks 7 dari array "root", misalnya, kita juga harus melakukan hal yang sama untuk "anak-anak". Namun, cukup mudah di sebagian besar bahasa untuk menggeneralisasi konsep ini ke wadah tujuan umum sehingga logika rumit untuk menjaga agar array paralel tetap sinkron satu sama lain hanya perlu ada di satu tempat di seluruh basis kode, dan wadah array paralel seperti itu dapat gunakan implementasi array jarang di atas untuk menghindari pemborosan banyak memori untuk ruang kosong yang berdekatan dalam array yang akan direklamasi pada penyisipan selanjutnya.

Lebih Banyak Elaborasi: Pohon Bitset Jarang

Baiklah, saya mendapat permintaan untuk menguraikan lebih banyak lagi yang menurut saya sarkastik, tetapi saya tetap akan melakukannya karena itu sangat menyenangkan! Jika orang ingin membawa ide ini ke level yang sama sekali baru, maka dimungkinkan untuk melakukan persimpangan set tanpa bahkan perulangan linear melalui elemen N + M. Ini adalah struktur data pamungkas yang telah saya gunakan sejak lama dan pada dasarnya model set<int>:

Alasannya dapat melakukan set persimpangan tanpa memeriksa setiap elemen di kedua daftar adalah karena bit set tunggal pada akar hierarki dapat menunjukkan bahwa, katakanlah, satu juta elemen yang berdekatan ditempati dalam set. Dengan hanya memeriksa satu bit, kita bisa tahu bahwa indeks N dalam kisaran, [first,first+N)berada di set, di mana N bisa menjadi angka yang sangat besar.

Saya benar-benar menggunakan ini sebagai pengoptimal loop ketika melintasi indeks yang diduduki, karena katakanlah ada 8 juta indeks yang ditempati di set. Nah, biasanya kita harus mengakses 8 juta integer dalam memori dalam kasus itu. Dengan yang satu ini, ia berpotensi hanya dapat memeriksa beberapa bit dan muncul dengan rentang indeks indeks yang ditempati untuk dilewati. Lebih jauh, rentang indeks yang muncul dengan urutan yang diurutkan yang membuat untuk akses sekuensial sangat ramah-cache sebagai lawan dari, katakanlah, iterasi melalui array indeks yang tidak disortir yang digunakan untuk mengakses data elemen asli. Tentu saja teknik ini memberikan hasil yang lebih buruk untuk kasus-kasus yang sangat jarang, dengan skenario kasus terburuk adalah seperti setiap indeks tunggal menjadi bilangan genap (atau setiap orang menjadi ganjil), dalam hal ini tidak ada daerah yang bersebelahan sama sekali. Namun dalam kasus penggunaan saya setidaknya,

Untuk memeriksa apakah set yang berisi n elemen berisi elemen lain X biasanya memakan waktu konstan. Untuk memeriksa apakah array yang berisi n elemen berisi elemen lain X biasanya membutuhkan waktu O (n). Itu buruk, tetapi jika Anda ingin menghapus duplikat dari n item, tiba-tiba dibutuhkan O (n) pada waktunya alih-alih O (n ^ 2); 100.000 item akan membuat komputer Anda bertekuk lutut.

Dan Anda meminta lebih banyak alasan? "Terlepas dari penembakan itu, apakah Anda menikmati malam itu, Mrs. Lincoln?"