Pertanyaan Apa struktur data yang kurang diketahui tetapi berguna?


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

Semua orang tahu tentang daftar terkait, pohon biner, dan hash, tapi bagaimana dengan Abaikan daftar dan Filter mekar sebagai contoh. Saya ingin tahu lebih banyak struktur data yang tidak begitu umum, tetapi patut diketahui karena mereka bergantung pada ide-ide hebat dan memperkaya kotak alat programmer.

PS: Saya juga tertarik dengan teknik seperti Link menari yang membuat penggunaan properti yang cerdas dari struktur data umum.

EDIT: Silakan coba sertakan tautan ke halaman yang menjelaskan struktur data secara lebih rinci. Juga, coba tambahkan beberapa kata Mengapa struktur data yang keren (as Jonas Kölker sudah disebutkan). Juga, coba sediakan satu struktur data per jawaban. Ini akan memungkinkan struktur data yang lebih baik untuk mengapung ke atas berdasarkan suara mereka sendiri.


797


asal


Jawaban:


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


271



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

Untuk menambahkan item, Anda menjalankannya k fungsi hash yang akan memberi Anda k indeks dalam larik yang kemudian Anda setel ke 1.

Untuk memeriksa apakah suatu item ada dalam set, hitunglah k indeks dan periksa apakah semuanya sudah diatur ke 1.

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

Menghapus item tidak mungkin, tetapi Anda dapat menerapkan menghitung filter mekar, diwakili oleh array int dan kenaikan / penurunan.


231



Tali: Ini adalah string yang memungkinkan untuk prepends murah, substring, insertion tengah dan menambahkan. Saya benar-benar hanya menggunakannya sekali, tetapi tidak ada struktur lain yang akan mencukupi. String reguler dan penambahan array terlalu mahal untuk apa yang perlu kita lakukan, dan membalikkan apa pun tidak mungkin.


140



Abaikan daftar cukup rapi.

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

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

Jika Anda ingin mendapatkan pengantar mendalam untuk melewati daftar di sini adalah a tautan ke video Pengantar MIT untuk Algoritma ceramah pada mereka.

Juga, sini adalah applet Java yang menunjukkan Skip Lists secara visual.


128



Indeks Spasial, khususnya R-trees dan Pohon KD, menyimpan data spasial secara efisien. Mereka baik untuk data koordinat peta geografis dan tempat VLSI dan algoritma rute, dan kadang-kadang untuk pencarian tetangga terdekat.

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


92



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

Hebatnya, Anda bisa mendapatkannya menerapkan teknik dari kalkulus ke tipe struktur data asli!


87



Berikut beberapa di antaranya:

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

  • Pohon Splay (seperti yang disebutkan di atas). Alasan mereka keren adalah tiga kali lipat:

    • Ukurannya kecil: Anda hanya perlu pointer kiri dan kanan seperti yang Anda lakukan di pohon biner (tidak ada informasi warna titik atau ukuran yang perlu disimpan)
    • Mereka (relatif) sangat mudah diimplementasikan
    • Mereka menawarkan kompleksitas amortisasi yang optimal untuk seluruh host "kriteria pengukuran" (log n lookup time menjadi satu-satunya orang yang tahu). Lihat http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • Pohon-pohon pencarian yang dipesan secara acak: Anda menyimpan sekelompok pasangan (kunci, prio) dalam sebuah pohon, seperti pohon pencarian dengan memperhatikan kunci-kunci, dan disusun sesuai dengan prioritas. Satu dapat menunjukkan bahwa pohon seperti itu memiliki bentuk yang unik (dan itu tidak selalu dikemas penuh ke atas dan ke kiri). Dengan prioritas acak, itu memberi Anda diharapkan O (log n) waktu pencarian, IIRC.

  • Satu niche adalah daftar adjacency untuk grafik planar tidak terarah dengan O (1) pertanyaan tetangga. Ini tidak begitu banyak struktur data sebagai cara tertentu untuk mengatur struktur data yang ada. Begini cara Anda melakukannya: setiap graf planar memiliki node dengan derajat paling banyak 6. Pilih simpul seperti itu, masukkan tetangganya dalam daftar tetangganya, keluarkan dari grafik, dan rekurse hingga grafik kosong. Ketika diberi sepasang (u, v), carilah u dalam daftar tetangga v dan untuk daftar tetangga v dalam u. Keduanya memiliki ukuran paling banyak 6, jadi ini adalah O (1).

Dengan algoritme di atas, jika u dan v bertetangga, Anda tidak akan memiliki u dalam daftar v dan v dalam daftar u. Jika Anda membutuhkan ini, cukup tambahkan setiap tetangga yang hilang node ke daftar tetangga simpul itu, tetapi simpan berapa banyak daftar tetangga yang perlu Anda telusuri untuk pencarian cepat.


69



Saya pikir alternatif bebas-lock pada struktur data standar yaitu antrian bebas-lock, stack, dan list sangat diabaikan.
Mereka semakin relevan karena konkurensi menjadi prioritas yang lebih tinggi dan merupakan tujuan yang jauh lebih mengagumkan daripada menggunakan Mutexes atau kunci untuk menangani membaca / menulis secara bersamaan.

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 

Mike Acton Blog (sering bersifat provokatif) memiliki beberapa artikel yang sangat bagus tentang desain dan pendekatan bebas-lock


65



kupikir Set Disjoint cukup bagus untuk kasus ketika Anda perlu membagi banyak item ke dalam kumpulan dan keanggotaan kueri yang berbeda. Implementasi yang baik dari Uni dan Menemukan hasil operasi dalam biaya diamortisasi yang secara efektif konstan (kebalikan dari Fungsi Ackermnan, jika saya ingat kelas struktur data saya dengan benar).


55



Tumpukan Fibonacci

Mereka digunakan dalam beberapa algoritma yang paling cepat dikenal (asimtotik) untuk banyak masalah yang terkait dengan grafik, seperti masalah Jalan Terpendek. Algoritma Dijkstra berjalan dalam waktu O (E log V) dengan tumpukan biner standar; menggunakan tumpukan Fibonacci meningkatkan itu ke O (E + V log V), yang merupakan percepatan besar untuk grafik padat. Sayangnya, mereka memiliki faktor konstan yang tinggi, sering membuat mereka tidak praktis dalam prakteknya.


52



Siapa pun yang memiliki pengalaman dalam 3D rendering harus akrab dengan Pohon BSP. Secara umum, ini adalah metode dengan menyusun adegan 3D agar dapat dikelola untuk menerjemahkan koordinat dan bearing kamera.

Partisi ruang biner (BSP) adalah a   metode untuk membagi kembali secara rekursif   ruang menjadi set cembung oleh hyperplanes.   Subdivisi ini menimbulkan a   representasi dari adegan dengan cara   dari struktur data pohon yang dikenal sebagai   Pohon BSP.

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

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


44