Penggunaan praktis dari berbagai struktur data [tertutup]

Ada banyak pembicaraan tentang struktur data, tetapi saya tidak dapat menemukan daftar sederhana dari struktur data dan penggunaan praktisnya di luar sana. Saya mencoba belajar untuk wawancara dan saya pikir ini akan membantu saya, bersama dengan banyak orang lainnya. Saya mencari sesuatu seperti ini:

Struktur data - Contoh / Digunakan untuk

Tabel hash - pencarian data cepat ... lalu berikan contoh

Himpunan - ...

Pohon biner - ...

Jika ada sumber daya seperti ini di suatu tempat, beri tahu saya.

Terima kasih!

EDIT: Maksud saya wikipedia bagus dan semuanya, tetapi di sebagian besar halaman mereka sebenarnya tidak mencantumkan penggunaan praktis. Saya mencari sesuatu yang lebih dari itu.

Menemukan daftar dalam pertanyaan serupa, sebelumnya di StackOverflow:

Tabel Hash - digunakan untuk pencarian data cepat - tabel simbol untuk kompiler, pengindeksan database, cache, representasi data unik.

Trie - kamus, seperti yang ditemukan di ponsel untuk pelengkapan otomatis dan pengecekan ejaan.

Pohon sufiks - pencarian teks lengkap cepat yang digunakan di sebagian besar pengolah kata.

Stack - undo \ redo operasi dalam pengolah kata, evaluasi ekspresi dan penguraian sintaks, banyak mesin virtual seperti JVM berorientasi pada tumpukan.

Antrian - Riset transportasi dan operasi di mana berbagai entitas disimpan dan diadakan untuk diproses kemudian, yaitu antrian menjalankan fungsi sebagai buffer.

Antrian prioritas - penjadwalan proses di kernel

Pohon - Parser, Sistem File

Pohon radix - tabel perutean IP

Pohon BSP - Grafik komputer 3D

Grafik - Koneksi / relasi di situs jejaring sosial, Routing, jaringan komunikasi, organisasi data dll.

Heap - Alokasi memori dinamis dalam cadel

Ini adalah jawaban yang awalnya diposting oleh RV Pradeep

Beberapa tautan lain yang kurang berguna:

Aplikasi hanya terdaftar untuk beberapa struktur data

Tidak fokus pada aplikasi, dengan ringkasan yang bagus dan relevan

Saya berada di perahu yang sama dengan Anda. Saya perlu belajar untuk wawancara teknologi, tetapi menghafal daftar tidak terlalu membantu. Jika Anda memiliki waktu luang 3-4 jam, dan ingin menyelam lebih dalam, saya sarankan untuk memeriksanya

mycodeschool
Saya telah melihat Coursera dan sumber daya lain seperti blog dan buku teks, tetapi saya menemukan mereka tidak cukup komprehensif atau di ujung lain spektrum, terlalu padat dengan terminologi ilmu komputer prasyarat.

Pria dalam video tersebut memiliki banyak ceramah tentang struktur data. Jangan pedulikan gambar konyol, atau sedikit aksen sama sekali. Anda perlu memahami tidak hanya struktur data mana yang harus dipilih, tetapi beberapa poin lain yang perlu dipertimbangkan ketika orang berpikir tentang struktur data:

• pro dan kontra dari struktur data umum
• mengapa setiap struktur data ada
• bagaimana sebenarnya itu bekerja dalam memori
• pertanyaan / latihan spesifik dan memutuskan struktur mana yang akan digunakan untuk efisiensi maksimum
• penjelasan Big 0 yang jernih

Saya juga memposting catatan di github jika Anda tertarik.

Menurut pemahaman saya, struktur data adalah setiap data yang berada di memori sistem elektronik apa pun yang dapat dikelola secara efisien. Seringkali ini adalah permainan memori atau aksesibilitas data yang lebih cepat. Dalam hal memori, ada pengorbanan yang dilakukan dengan pengelolaan data berdasarkan biaya yang ditanggung perusahaan untuk produk akhir tersebut. Dikelola secara efisien memberi tahu kami cara terbaik data dapat diakses berdasarkan persyaratan utama produk akhir. Ini adalah penjelasan tingkat tinggi tetapi struktur data adalah subjek yang sangat luas. Sebagian besar pewawancara mendalami struktur data yang dapat mereka diskusikan dalam wawancara tergantung pada waktu yang mereka miliki, yaitu daftar terkait dan subjek terkait.

Sekarang, tipe data ini dapat dibagi menjadi primitif, abstrak, komposit, berdasarkan cara mereka dibangun dan diakses secara logis.

• struktur data primitif adalah blok bangunan dasar untuk semua struktur data, mereka memiliki memori berkelanjutan untuk mereka: boolean, char, int, float, double, string.
• struktur data komposit adalah struktur data yang tersusun dari lebih dari satu tipe data primitif. kelas, struktur, gabungan, larik / catatan.
• tipe data abstrak adalah tipe data komposit yang memiliki cara untuk mengaksesnya secara efisien yang disebut sebagai algoritma. Bergantung pada cara data diakses, struktur data dibagi menjadi tipe data linier dan non linier. Daftar tertaut, tumpukan, antrian, dll adalah tipe data linier. heaps, pohon biner dan tabel hash dll adalah tipe data non linier.

Saya harap ini membantu Anda memahami.

Buku luar biasa " Manual Desain Algoritma" oleh Skienna berisi gudang besar Algoritma dan struktur Data.

Untuk banyak masalah, struktur data dan algoritme dijelaskan, dibandingkan, dan membahas penggunaan praktis. Penulis juga memberikan referensi implementasi dan makalah penelitian asli.

Buku ini bagus untuk diletakkan di meja Anda jika Anda mencari struktur data terbaik untuk memecahkan masalah Anda. Ini juga sangat membantu untuk persiapan wawancara.

Sumber daya hebat lainnya adalah Kamus NIST untuk struktur dan algoritma Data .

Beberapa Aplikasi struktur data yang lebih Praktis

Pohon Merah-Hitam (Digunakan ketika sering ada Penyisipan / Penghapusan dan sedikit pencarian) - K-mean Clustering menggunakan pohon merah hitam, Database, database Simple-minded, mencari kata-kata di dalam kamus, mencari di web

Pohon AVL (Lebih Banyak Pencarian dan lebih sedikit Penyisipan / Penghapusan) - Analisis Data dan Penambangan Data dan aplikasi yang melibatkan lebih banyak pencarian

Min Heap - Algoritma Pengelompokan

Peringkat dari berbagai struktur data setidaknya akan sebagian terkait dengan konteks masalah. Ini akan membantu untuk mempelajari bagaimana menganalisis kinerja ruang dan waktu dari algoritma. Biasanya, "notasi O besar" digunakan, misalnya pencarian biner dalam waktu O (log n), yang berarti waktu untuk mencari elemen adalah log (dalam basis 2, secara implisit) dari jumlah elemen. Secara intuitif, karena setiap langkah membuang setengah dari data yang tersisa sebagai tidak relevan, menggandakan jumlah elemen akan meningkatkan waktu sebanyak 1 langkah. (Pencarian biner berskala cukup baik.) Kinerja ruang berkaitan dengan bagaimana jumlah memori tumbuh untuk kumpulan data yang lebih besar. Juga, perhatikan bahwa notasi O besar mengabaikan faktor konstan - untuk kumpulan data yang lebih kecil, algoritme O (n ^ 2) mungkin masih lebih cepat daripada algoritme O (n * log n) yang memiliki faktor konstanta lebih tinggi.

Selain waktu dan ruang, karakteristik lain termasuk apakah struktur data diurutkan (pohon dan skiplist diurutkan, tabel hash tidak), persistensi (pohon biner dapat menggunakan kembali pointer dari versi lama, sementara tabel hash dimodifikasi pada tempatnya), dll.

Meskipun Anda perlu mempelajari perilaku beberapa struktur data untuk dapat membandingkannya, satu cara untuk mengembangkan pemahaman mengapa mereka berbeda dalam kinerja adalah dengan mempelajari beberapa. Saya menyarankan untuk membandingkan daftar tertaut tunggal, hierarki pencarian biner, dan daftar lewati , yang semuanya relatif sederhana, tetapi memiliki karakteristik yang sangat berbeda. Pikirkan tentang berapa banyak pekerjaan yang diperlukan untuk menemukan nilai, menambahkan nilai baru, menemukan semua nilai secara berurutan, dll.

Ada berbagai teks tentang menganalisis algoritme / performa struktur data yang direkomendasikan orang, tetapi yang benar-benar membuatnya masuk akal bagi saya adalah mempelajari OCaml. Berurusan dengan struktur data yang kompleks adalah keunggulan ML, dan perilakunya jauh lebih jelas ketika Anda dapat menghindari pointer dan manajemen memori seperti di C. (Mempelajari OCaml hanya untuk memahami struktur data hampir pasti sudah lama). :))