Apa struktur data yang kurang dikenal tetapi bermanfaat?

Ada beberapa struktur data di sekitar yang benar-benar berguna tetapi tidak diketahui oleh kebanyakan programmer. Yang mana mereka?

Semua orang tahu tentang daftar yang ditautkan, pohon biner, dan hash, tetapi bagaimana dengan Melewati daftar dan filter Bloom misalnya. Saya ingin tahu lebih banyak struktur data yang tidak begitu umum, tetapi patut diketahui karena mereka mengandalkan ide-ide hebat dan memperkaya kotak alat programmer.

PS: Saya juga tertarik dengan teknik seperti Dancing link yang memanfaatkan properti struktur data secara pintar.

EDIT : Silakan coba sertakan tautan ke halaman yang menggambarkan struktur data secara lebih rinci. Juga, coba tambahkan beberapa kata tentang mengapa struktur data keren (seperti yang ditunjukkan Jonas Kölker ). Juga, coba berikan satu struktur data per jawaban . Ini akan memungkinkan struktur data yang lebih baik mengapung ke atas berdasarkan suara mereka sendiri.

Tries , juga dikenal sebagai prefix-tree atau crit-bit tree , telah ada selama lebih dari 40 tahun tetapi masih relatif tidak dikenal. Penggunaan percobaan yang sangat keren dijelaskan dalam " TRASH - LC-trie dinamis dan struktur data hash ", yang menggabungkan trie dengan fungsi hash.

Filter Bloom : Array bit m bit, awalnya semua diatur ke 0.

Untuk menambahkan item Anda menjalankannya melalui fungsi hash k yang akan memberi Anda indeks k dalam array yang kemudian Anda tetapkan ke 1.

Untuk memeriksa apakah suatu item ada di set, hitung indeks k dan periksa apakah semuanya diatur ke 1.

Tentu saja, ini memberikan beberapa kemungkinan false-positif (menurut wikipedia sekitar 0,61 ^ (m / n) di mana n adalah jumlah item yang dimasukkan). Negatif palsu tidak dimungkinkan.

Menghapus item tidak mungkin, tetapi Anda dapat menerapkan penghitungan filter bloom , yang diwakili oleh array int dan kenaikan / penurunan.

Tali : Ini adalah string yang memungkinkan untuk prepends murah, substring, sisipan tengah dan tambahkan. Saya benar-benar hanya pernah menggunakannya sekali, tetapi tidak ada struktur lain yang cukup. String dan susunan array reguler jauh terlalu mahal untuk apa yang perlu kami lakukan, dan membalikkan segala sesuatu adalah mustahil.

Melewati daftar cukup rapi.

Wikipedia
Daftar lompatan adalah struktur data probabilistik, berdasarkan beberapa paralel, daftar tertaut yang diurutkan, dengan efisiensi yang sebanding dengan pohon pencarian biner (catatan log dan waktu rata-rata untuk sebagian besar operasi).

Mereka dapat digunakan sebagai alternatif untuk pohon seimbang (menggunakan keseimbangan probalistik daripada penegakan keseimbangan yang ketat). Mereka mudah diimplementasikan dan lebih cepat daripada mengatakan, pohon merah-hitam. Saya pikir mereka harus berada di setiap toolchest programmer yang baik.

Jika Anda ingin mendapatkan pengantar mendalam untuk melewati daftar di sini adalah tautan ke video perkenalan tentang Algoritma MIT untuk mereka.

Juga, di sini adalah applet Java menunjukkan Lists Lewati visual.

Indeks spasial , khususnya pohon R dan pohon KD , menyimpan data spasial secara efisien. Mereka bagus untuk data koordinat peta geografis dan algoritma VLSI place and route, dan kadang-kadang untuk pencarian tetangga terdekat.

Array Bit menyimpan bit individual secara kompak dan memungkinkan operasi bit cepat.

Ritsleting - turunan dari struktur data yang memodifikasi struktur untuk memiliki gagasan alami 'kursor' - lokasi saat ini. Ini sangat berguna karena mereka menjamin indeks tidak dapat keluar dari batas - digunakan, misalnya di window manager xmonad untuk melacak window mana yang telah difokuskan.

Hebatnya, Anda dapat menurunkannya dengan menerapkan teknik dari kalkulus ke jenis struktur data asli!

Berikut ini beberapa di antaranya:

• Suffix mencoba. Berguna untuk hampir semua jenis pencarian string (http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). Lihat juga susunan sufiks; mereka tidak secepat pohon sufiks, tetapi jauh lebih kecil.

• Bentangkan pohon (seperti yang disebutkan di atas). Alasan mereka keren ada tiga:

  • Mereka kecil: Anda hanya perlu pointer kiri dan kanan seperti yang Anda lakukan di pohon biner apa pun (tidak ada informasi warna-simpul atau ukuran yang perlu disimpan)
  • Mereka (relatif) sangat mudah diimplementasikan
  • Mereka menawarkan kompleksitas diamortisasi optimal untuk seluruh host "kriteria pengukuran" (login dan waktu pencarian menjadi semua orang tahu). Lihathttp://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

• Pohon pencarian berurutan Heap: Anda menyimpan sekelompok (kunci, prio) pasangan di pohon, sehingga itu pohon pencarian sehubungan dengan kunci, dan tumpukan memerintahkan sehubungan dengan prioritas. Orang dapat menunjukkan bahwa pohon seperti itu memiliki bentuk yang unik (dan itu tidak selalu penuh ke atas dan ke kiri). Dengan prioritas acak, ini memberi Anda waktu pencarian O (log n) yang diharapkan, IIRC.

• Ceruk satu adalah daftar adjacency untuk grafik planar tidak berarah dengan O (1) pertanyaan tetangga. Ini bukan struktur data seperti cara tertentu untuk mengatur struktur data yang ada. Begini cara Anda melakukannya: setiap grafik planar memiliki simpul dengan derajat paling banyak 6. Pilih simpul seperti itu, letakkan tetangganya dalam daftar tetangganya, hapus dari grafik, dan ulangi sampai grafik kosong. Ketika diberi pasangan (u, v), cari u di daftar tetangga v dan untuk v di daftar tetangga u. Keduanya memiliki ukuran paling banyak 6, jadi ini adalah O (1).

Dengan algoritma di atas, jika u dan v adalah tetangga, Anda tidak akan memiliki u dalam daftar v dan v dalam daftar u. Jika Anda membutuhkan ini, tambahkan saja tetangga yang hilang setiap node ke daftar tetangga simpul itu, tetapi simpan berapa banyak dari daftar tetangga yang perlu Anda cari untuk pencarian cepat.

Saya pikir alternatif bebas kunci untuk struktur data standar yaitu antrian bebas kunci, tumpukan dan daftar banyak diabaikan.
Mereka semakin relevan karena concurrency menjadi prioritas yang lebih tinggi dan tujuan yang jauh lebih mengagumkan daripada menggunakan Mutex atau kunci untuk menangani baca / tulis bersamaan.

Berikut ini beberapa tautan
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Tautan ke PDF]
http://www.boyet.com/Articles/LockfreeStack.html

Blog Mike Acton (sering provokatif) memiliki beberapa artikel bagus tentang desain dan pendekatan bebas kunci

Saya pikir Disjoint Set cukup bagus untuk kasus-kasus ketika Anda perlu membagi banyak item menjadi set yang berbeda dan permintaan keanggotaan. Implementasi yang baik dari operasi Union dan Find menghasilkan biaya diamortisasi yang secara efektif konstan (kebalikan dari Fungsi Ackermnan, jika saya mengingat kelas struktur data dengan benar).

Tumpukan Fibonacci

Mereka digunakan dalam beberapa algoritma yang dikenal paling cepat (tanpa gejala) untuk banyak masalah yang berhubungan dengan grafik, seperti masalah Jalur Terpendek. Algoritma Dijkstra berjalan dalam waktu O (E log V) dengan tumpukan biner standar; menggunakan tumpukan Fibonacci meningkatkannya menjadi O (E + V log V), yang merupakan percepatan besar untuk grafik padat. Sayangnya, mereka memiliki faktor konstan yang tinggi, seringkali membuat mereka tidak praktis dalam praktik.

Siapa pun yang berpengalaman dalam rendering 3D harus terbiasa dengan pohon-pohon BSP . Secara umum, ini adalah metode dengan menyusun adegan 3D agar dapat dikelola untuk rendering mengetahui koordinat dan bantalan kamera.

Binary space partisiing (BSP) adalah metode untuk membagi ruang secara rekursif menjadi set cembung oleh pesawat terbang. Subdivisi ini memunculkan representasi adegan dengan menggunakan struktur data pohon yang dikenal sebagai pohon BSP.

Dengan kata lain, ini adalah metode memecah poligon yang berbentuk rumit menjadi set cembung, atau poligon yang lebih kecil yang seluruhnya terdiri dari sudut non-refleks (sudut lebih kecil dari 180 °). Untuk deskripsi yang lebih umum tentang partisi ruang, lihat partisi ruang.

Awalnya, pendekatan ini diusulkan dalam grafik komputer 3D untuk meningkatkan efisiensi rendering. Beberapa aplikasi lain termasuk melakukan operasi geometris dengan bentuk (konstruktif solid geometri) di CAD, deteksi tabrakan dalam game robotika dan komputer 3D, dan aplikasi komputer lainnya yang melibatkan penanganan adegan spasial yang kompleks.

Pohon Huffman - digunakan untuk kompresi.

Lihatlah Finger Trees , terutama jika Anda seorang penggemar struktur data yang murni fungsional yang disebutkan sebelumnya . Mereka adalah representasi fungsional dari sekuens persisten yang mendukung akses ke ujung dalam waktu konstan diamortisasi, dan penggabungan dan pemisahan dalam waktu logaritmik dalam ukuran potongan yang lebih kecil.

Sesuai artikel aslinya :

Pohon 2-3 jari fungsional kami adalah contoh dari teknik desain umum yang diperkenalkan oleh Okasaki (1998), yang disebut perlambatan rekursif implisit . Kami telah mencatat bahwa pohon-pohon ini merupakan perpanjangan dari struktur deque implisitnya, menggantikan pasangan dengan 2-3 node untuk memberikan fleksibilitas yang diperlukan untuk penggabungan dan pemisahan yang efisien.

Finger Tree dapat diparameterisasi dengan monoid , dan menggunakan monoid yang berbeda akan menghasilkan perilaku yang berbeda untuk pohon tersebut. Ini memungkinkan Finger Tree mensimulasikan struktur data lainnya.

Circular atau ring buffer - digunakan untuk streaming, antara lain.

Saya terkejut tidak ada yang menyebut pohon Merkle (mis. Hash Trees ).

Digunakan dalam banyak kasus (program P2P, tanda tangan digital) di mana Anda ingin memverifikasi hash seluruh file ketika Anda hanya memiliki bagian dari file yang tersedia untuk Anda.

<zvrba> Pohon Van Emde-Boas

Saya pikir akan bermanfaat untuk mengetahui mengapa mereka keren. Secara umum, pertanyaan "mengapa" adalah yang paling penting untuk ditanyakan;)

Jawaban saya adalah mereka memberi Anda kamus O (log log n) dengan kunci {1..n}, terlepas dari berapa banyak kunci yang digunakan. Sama seperti separuh berulang memberi Anda O (log n), sqrting berulang memberi Anda O (log log n), yang adalah apa yang terjadi di pohon vEB.

Bagaimana dengan hamparan pohon ?

Juga, struktur data murni fungsional Chris Okasaki muncul di pikiran.

Varian yang menarik dari tabel hash disebut Cuckoo Hashing . Ini menggunakan beberapa fungsi hash, bukan hanya 1 untuk menangani tabrakan hash. Tabrakan diselesaikan dengan menghapus objek lama dari lokasi yang ditentukan oleh hash utama, dan memindahkannya ke lokasi yang ditentukan oleh fungsi hash alternatif. Cuckoo Hashing memungkinkan penggunaan ruang memori yang lebih efisien karena Anda dapat meningkatkan load factor hingga 91% dengan hanya 3 fungsi hash dan masih memiliki waktu akses yang baik.

Sebuah tumpukan min-max adalah variasi dari tumpukan yang menerapkan antrian prioritas double-berakhir. Ini mencapainya dengan perubahan sederhana ke properti heap: Sebuah pohon dikatakan min-max dipesan jika setiap elemen pada level genap (ganjil) kurang (lebih besar) dari semua anak dan cucu. Level diberi nomor mulai dari 1.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

Saya suka Cast Oblivious datastructures . Ide dasarnya adalah untuk meletakkan pohon di blok-blok yang lebih kecil secara rekursif sehingga cache dengan berbagai ukuran akan memanfaatkan blok yang cocok untuk mereka. Ini mengarah pada penggunaan caching yang efisien dalam segala hal, mulai dari cache L1 di RAM hingga potongan besar data yang dibaca dari disk tanpa perlu mengetahui secara spesifik ukuran dari setiap lapisan caching tersebut.

Pohon Miring Merah-Hitam Miring . Implementasi yang disederhanakan secara signifikan dari pohon merah-hitam oleh Robert Sedgewick yang diterbitkan pada 2008 (~ setengah dari baris kode untuk diimplementasikan). Jika Anda pernah mengalami kesulitan membungkus kepala Anda di sekitar implementasi pohon Merah-Hitam, baca tentang varian ini.

Sangat mirip (jika tidak identik) dengan Andersson Trees.

Antrian Mencuri Pekerjaan

Struktur data bebas kunci untuk membagi pekerjaan yang setara di antara beberapa utas. Implementasi antrian pencurian pekerjaan di C / C ++?

Tumpukan binewial bootstrap oleh Gerth Stølting Brodal dan Chris Okasaki:

Terlepas dari nama panjang mereka, mereka menyediakan operasi heap optimal asimptotik, bahkan dalam pengaturan fungsi.

• O(1)ukuran, penyatuan , masukkan, minimum
• O(log n) deleteMin

Perhatikan bahwa penyatuan membutuhkan O(1)lebih dari O(log n)waktu tidak seperti tumpukan yang lebih terkenal yang biasanya dicakup dalam buku teks struktur data, seperti tumpukan kiri . Dan tidak seperti tumpukan Fibonacci , asimptotik itu adalah yang terburuk, bukannya diamortisasi, bahkan jika digunakan terus-menerus!

Ada beberapa implementasi di Haskell.

Mereka bersama-sama diturunkan oleh Brodal dan Okasaki, setelah Brodal datang dengan tumpukan imperatif dengan asimptotik yang sama.

• Kd-Trees , struktur data spasial yang digunakan (antara lain) dalam Real-Time Raytracing, memiliki sisi negatif yang segitiga yang memotong ruang yang berbeda harus dipotong. Secara umum, BVH lebih cepat karena lebih ringan.
• MX-CIF Quadtrees , simpan kotak pembatas alih-alih set titik sembarang dengan menggabungkan quadtree biasa dengan pohon biner di tepi paha depan.
• HAMT , peta hash hirarkis dengan waktu akses yang umumnya melebihi O (1) peta hash karena konstanta yang terlibat.
• Inverted Index , cukup terkenal di kalangan mesin pencari, karena digunakan untuk pengambilan cepat dokumen yang terkait dengan istilah pencarian yang berbeda.

Sebagian besar, jika tidak semua, ini didokumentasikan pada Kamus Algoritma dan Struktur Data NIST

Pohon Bola. Hanya karena mereka membuat orang tertawa.

Bola pohon adalah struktur data yang mengindeks poin dalam ruang metrik. Inilah artikel tentang membangunnya. Mereka sering digunakan untuk menemukan tetangga terdekat ke suatu titik atau mempercepat k-means.

Tidak benar-benar struktur data; lebih banyak cara untuk mengoptimalkan array yang dialokasikan secara dinamis, tetapi buffer celah yang digunakan dalam Emacs agak keren.

Pohon Fenwick. Ini adalah struktur data untuk menjaga jumlah penjumlahan semua elemen dalam vektor, antara dua subindeks i dan j yang diberikan. Solusi sepele, menghitung ulang jumlah sejak awal tidak memungkinkan untuk memperbarui item (Anda harus melakukan O (n) bekerja untuk menjaga).

Fenwick Trees memungkinkan Anda untuk memperbarui dan meminta dalam O (log n), dan cara kerjanya sangat keren dan sederhana. Ini dijelaskan dengan sangat baik di koran asli Fenwick, tersedia secara gratis di sini:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Ayahnya, pohon RQM juga sangat keren: Ini memungkinkan Anda untuk menyimpan info tentang elemen minimum antara dua indeks dari vektor, dan juga bekerja di O (log n) pembaruan dan kueri. Saya suka mengajar pertama RQM dan kemudian Pohon Fenwick.

Pohon Van Emde-Boas . Saya bahkan memiliki implementasi C ++ , untuk hingga 2 ^ 20 integer.

Kumpulan bersarang bagus untuk mewakili pohon dalam database relasional dan menjalankan kueri pada mereka. Sebagai contoh, ActiveRecord (ORM default Ruby on Rails) hadir dengan plugin set bersarang yang sangat sederhana , yang membuat bekerja dengan pohon sepele.

Ini cukup spesifik untuk domain, tetapi struktur data setengah-tepi cukup rapi. Ini menyediakan cara untuk beralih di atas jerat poligon (wajah dan tepi) yang sangat berguna dalam grafik komputer dan geometri komputasi.