Apa struktur data paling rumit yang Anda gunakan dalam situasi praktis? [Tutup]

Bibit untuk pertanyaan ini muncul dari diskusi yang saya lakukan dengan beberapa rekan pengembang dari industri.

Ternyata di banyak tempat, manajer proyek khawatir tentang struktur data yang kompleks, dan umumnya bersikeras pada apa pun yang ada di luar kotak dari perpustakaan / paket standar. Gagasan umum tampaknya seperti menggunakan kombinasi apa yang sudah tersedia kecuali kinerja sangat terhambat. Ini membantu menjaga basis kode tetap sederhana, yang bagi non-diplomatik akan berarti "kita memiliki gesekan tinggi, dan yang lebih baru yang kita sewa mungkin tidak sebaik itu".

Jadi tidak ada filter mekar atau lewati daftar atau splay pohon untuk Anda pecandu CS. Jadi inilah pertanyaannya (lagi): Apa struktur data paling rumit yang Anda lakukan atau gunakan di kantor?

Membantu memahami seberapa bagus / canggihnya perangkat lunak dunia nyata.

Telah menggunakan daftar lewati untuk pencarian. Di mana saya bekerja, ada implementasi standar dan semua orang didorong untuk menggunakannya. Telah menggunakan patricia mencoba untuk menyimpan dan mengambil alamat ip secara efisien. Lagi implementasi sudah hadir.

Saya adalah pengembang Java. Java Collection Framework dapat memecahkan 90% masalah struktur data saya, 10% lainnya membutuhkan usaha. Saya pikir jika Anda benar-benar memahami standar lib canggih yang ditulis oleh para ahli, Anda akan menemukan mereka membantu dalam banyak kasus.

Struktur data yang kompleks sulit dipertahankan di dunia nyata. Untuk menghindari mengacaukan kode, saya akan membagi masalah ke beberapa yang lebih kecil. Setiap masalah kecil dapat diselesaikan dengan Java Collection Framework . Mungkin solusinya bukan yang paling cerdas (membutuhkan lebih banyak memori dan lebih lambat), tetapi ini bekerja dan mudah dirawat. Ini pertukaran.

Jika saya harus menulis struktur data yang kompleks, saya akan mengambil buku pelajaran :)

Struktur data paling rumit yang saya gunakan pada pekerjaan adalah trie. Namun, itu dua puluh tahun yang lalu.

Masalah dengan pengembangan perangkat lunak industri adalah bahwa kebanyakan programmer industri bukan lulusan ilmu komputer (CompSci); Oleh karena itu, teknik yang diterima oleh lulusan CompSci rata-rata dianggap terlalu sulit untuk dipelihara oleh programmer roti dan mentega.

Kurangnya pengetahuan CompSci umum di industri adalah masalah serius. Sebagai contoh, saya telah kehilangan hitungan jumlah pengembang perangkat lunak yang saya temui yang tidak mengerti ekspresi seperti! (A! = 5 && b! = 3) dan a == 5 || b == 3 secara logis setara. Siapa pun yang tahu bagaimana menerapkan Teorema DeMorgan dapat mengenali bahwa ekspresi ini setara secara logis. Sebagian besar lulusan non-CompSci belum pernah mendengar Teorema DeMorgan. Jika seseorang mensurvei basis kode yang substansial, seseorang akan menemukan banyak kemunculan ekspresi yang meniadakan subekspresi logis negatif. Keterbacaan kode yang berisi sub-ekspresi logis negatif yang dinegasikan hampir selalu ditingkatkan dengan mengubah ekspresi ini menjadi bentuk yang tidak dinegasikan.

Saya pernah menulis antrian kalender (O (1) antrian prioritas) untuk simulasi berbasis peristiwa di mana profil menunjukkan bahwa tumpukan yang ada adalah hambatan.

Saya juga merilis produk yang berisi mesin negara terbatas dengan sekitar 80000 negara - kode untuk menghasilkannya agak fiddly, untuk sedikitnya.

Lama, lama, lalu, di sebuah galaksi ... Bekerja pada sebuah tim yang menggunakan "teman buddy" Knuth dalam RTOS di assembler.

Juga, Permainan Kehidupan Conway dengan 256 generasi untuk dunia 1024 x 1024.

Tidak benar-benar menggunakan sesuatu yang terlalu istimewa, dari awal akan menjadi daftar yang terhubung dua kali lipat .

Tidak terlalu menarik, saya telah menggunakan struktur lain. Tetapi pertanyaan Anda mengatakan dari awal.

Pohon hashtable yang berisi daftar umum data keuangan - bahkan tidak bertanya. Terkadang saya berharap saya seorang koboi. Ah, kehidupan sederhana di bawah bintang-bintang ...

Saya harus menulis struktur Circular Double-Linked-List dari awal untuk Algoritma Dancing Links untuk pemecah Sudoku. Rasanya seperti merancang kubus Rubik. Seluruh struktur pada dasarnya adalah daftar daftar - dengan masing-masing node menunjuk ke empat lainnya.

Saya pernah menggunakan pohon panjang jalur tertimbang untuk cache khusus. Itu tadi menyenangkan. Juga menulis rutinitas manajemen tumpukan saya sendiri untuk malloc()penggantian, tetapi banyak orang telah melakukan itu.

Setelah memikirkannya, struktur data paling "rumit" yang pernah saya lakukan dari awal adalah pemodelan jaringan elemen yang didasarkan pada daftar yang ditautkan dua kali lipat. Tapi itu bertahun-tahun yang lalu ketika saya biasa melakukan pemrograman tingkat sistem.

Hari ini saya hampir tidak membuat struktur data yang bagus. Sebagian besar terjadi dalam database di mana Anda memutuskan apa yang Anda masukkan ke dalam tabel, mungkin beberapa nilai yang dihitung sebelumnya mungkin ID dari beberapa catatan terkait untuk pengambilan cepat untuk menghindari pencarian yang tidak perlu.

Saya pribadi mengatakan bahwa tugas yang ada mendefinisikan alat. Mengapa berusaha menggunakan beberapa struktur data yang eksotis jika tidak ada gunanya? Dan jika saya dapat mengatakan di sebagian besar pemrograman praktis yang diterapkan mungkin tidak perlu menemukan kembali roda.

Apakah antrian prioritas dihitung? Itu muncul di hampir setiap aplikasi real-time yang saya tulis. Itu menjadi bagian dari perpustakaan Java standar hanya baru-baru ini (Java 1.5).

Selain itu, saya tidak dapat memikirkan hal rumit yang saya benar-benar inginkan sehingga saya belum dapat keluar dari perpustakaan. Saya tidak akan membiarkan hal itu menghentikan saya, tetapi saya akan mempertanyakan mengapa saya membutuhkan struktur data yang terlalu eksotis untuk dimasukkan perpustakaan. Saya pasti akan mencari implementasi open-source dari trie atau bloom filter atau daftar lompatan sebelum saya mencoba menulis sendiri.

Secara umum saya setuju dengan manajer Anda bahwa biaya membangun dan mempertahankan struktur data khusus terlalu esoteris karena tidak ada versi perpustakaan yang cenderung lebih besar daripada manfaat kinerja yang diperoleh darinya. Saya ingin Anda menunjukkan, melalui profil, bahwa struktur pustaka polos menyebabkan penalti kinerja yang signifikan sebelum saya membiarkan Anda maju dan mengoptimalkannya dengan sesuatu yang mewah. Karena sebagai aturan umum, lebih murah untuk membeli siklus prosesor daripada siklus teknik.