Bagaimana cara memilih struktur data kamus fungsional?

10

Saya telah membaca sedikit tentang struktur data berikut:

  • Ideal Hash Tries dari Bagwell
  • Tabel hash Dinamis Larson
  • Pohon merah-hitam
  • Pohon Patricia

... dan saya yakin ada banyak orang lain di luar sana. Saya telah melihat sangat sedikit di mana masing-masing lebih cocok untuk, atau mengapa saya akan memilih satu dari yang lain. Jadi, berikut beberapa pertanyaan di bawah ini:

  1. Struktur data kamus fungsional apa yang penting untuk diketahui?
  2. Apa pro dan kontra dari pendekatan ini?
  3. Kapan masuk akal untuk menggunakan struktur data yang lebih penting?

Angka 2 & 3 adalah yang lebih penting. :-)

ds.data-structures functional-programming tree hash-function Jason
sumber
Terkait: Apa yang baru dalam struktur data murni fungsional sejak Okasaki? (Pertanyaan itu tidak terbatas pada kamus.)
Tsuyoshi Ito
Pertanyaan ini (selain item bernomor 3) memiliki perasaan [daftar besar].
Kaveh
2
akan sangat membantu untuk mengetahui apakah pertanyaan terkait di atas mengatasi masalah Anda, dan jika tidak mengapa tidak
Suresh Venkat
@ Suresh - Jawaban itu # 1, tetapi 2 dan 3 adalah yang lebih penting. Saya kebanyakan mencari gambaran besar sehingga saya bisa menentukan mana yang layak dipelajari secara lebih mendalam.
Jason
2
baik. jadi mungkin ada baiknya mengedit pertanyaan itu.
Suresh Venkat

Jawaban:

16

Saya benar-benar tidak dapat menjawab # 2 tanpa tersesat (ada terlalu banyak dimensi di mana Anda dapat membandingkan struktur ini), tetapi untuk # 3 jawabannya cukup sederhana.

Gunakan struktur data imperatif jika: (a) sama sekali tidak ada alias, atau (b) Anda benar-benar perlu menggunakan alias untuk siaran yang efisien.

Jika tidak ada alias struktur data sama sekali, maka Anda tidak mengambil keuntungan dari fakta bahwa struktur data fungsional bersifat persisten. Jadi tidak ada alasan untuk membayar biayanya. Ada dua peringatan untuk saran ini. Pertama, Anda mungkin lebih suka kesederhanaan implementasi struktur data fungsional: menerapkan penghapusan untuk pohon merah-hitam fungsional akan membuat Anda mengutuk, tetapi menerapkan penghapusan di pohon merah-hitam imperatif dengan pointer orangtua akan membuat Anda berpikir untuk bunuh diri. Kedua, penugasan bisa lebih mahal dari yang Anda harapkan dalam bahasa gc'd, karena menulis bisa membuat struktur data dipindahkan dari generasi muda. Kami benar-benar tidak memiliki teori efek cache dan gc yang baik, jadi Anda tidak punya pilihan selain melakukan benchmarking.

Kedua, jika Anda membutuhkan saluran siaran, maka struktur data bersama adalah cara terbaik untuk melakukannya. Dengan pembaruan waktu-konstan, Anda dapat memberi tahu banyak orang secara sewenang-wenang bahwa suatu nilai telah berubah. (Inilah sebabnya mengapa union-find adalah struktur data yang hebat.) Dengan pengaturan yang murni fungsional, Anda perlu memodifikasi semua orang lain, atau memberi mereka pointer abstrak ke dalam keadaan yang Anda kode secara manual (yang merupakan jenis tumpul sesuatu yang harus dikerjakan).

Jika Anda tidak ingin beralasan tentang aliasing dan kepemilikan objek, atau jika Anda memerlukan beberapa versi dari struktur data yang sama (katakanlah Anda membutuhkan versi baru dan lama, katakanlah), maka gunakan saja struktur data fungsional.

Tempat di mana saya menemukan mengikuti saran ini yang paling sulit adalah dengan algoritma grafik. Ada banyak algoritma grafik imperatif yang benar-benar elegan, tetapi sering kali terjadi (misalnya, saat menulis kompiler) Anda juga ingin kegigihan. Orang-orang biasanya mencoba untuk membagi perbedaan dan menggunakan algoritma imperatif keren tetapi mencoba untuk mengaitkan versi ke samping untuk mendapatkan kegigihan. Ini umumnya cukup mengerikan, penuh bug, dan cenderung kehilangan keunggulan kinerja dari algoritma imperatif.

Neel Krishnaswami
sumber
2
apa aliasing dalam konteks ini?
Suresh Venkat
6
Mengasingkan adalah ketika Anda memiliki beberapa referensi ke bagian data yang sama. Jika data itu bisa berubah, maka alasan tentang program yang menggunakannya harus secara eksplisit memperhitungkan semua subprogram lain yang dapat mengakses dan memodifikasinya. Jika sepotong data tidak dapat diubah, maka Anda dapat beralasan secara lokal tentang program yang menggunakannya, mengabaikan alias, karena Anda tahu tidak ada orang yang dapat mengakses data yang dapat memodifikasinya.
Neel Krishnaswami
"tapi menerapkan penghapusan di pohon merah-hitam imperatif dengan pointer orangtua akan membuatmu berpikir untuk bunuh diri" Lihat pohon merah-hitam Sedgewick yang condong ke kiri. Kasus umum penghapusan dikurangi menjadi delete-min oleh trik standar, dan delete-min sendiri sangat sederhana untuk pohon LLRB. Tidak diperlukan pointer orangtua.
Per Vognsen
1
"Ini umumnya cukup mengerikan, penuh bug, dan cenderung kehilangan keunggulan kinerja dari algoritma imperatif." Makalah Norman Ramsey tentang penggunaan ritsleting untuk grafik aliran kontrol dalam kompiler yang mengoptimalkan memberikan contoh kompromi yang menarik. Anda secara efektif memiliki tumpukan lokal untuk mendukung rewiring di tempat yang mudah dan efisien referensi antara blok dasar dalam CFG, tetapi manipulasi isi blok dasar fungsional (atau semi-fungsional, tergantung pada pandangan filosofis ritsleting Anda).
Per Vognsen
1

Struktur data kamus fungsional apa yang penting untuk diketahui?

Pohon biner yang seimbang tinggi dan percobaannya adalah kompromi serba baik. Juga:

  • Pohon Patricia.
  • Hash mencoba.

Apa pro dan kontra dari pendekatan ini?

Pohon biner yang seimbang tinggi dan percobaannya adalah kompromi menyeluruh yang baik untuk kunci atom. Tries sama untuk kunci yang berurutan, misalnya kunci string.

Pohon Patricia bisa beberapa kali lebih cepat tetapi hanya mengizinkan kunci integer.

Percobaan hash bisa beberapa kali lebih cepat daripada pohon biner seimbang, terutama jika hashing lebih murah daripada perbandingan dan polimorfisme memiliki overhead (mis. String pada .NET) dan penulisan pointer ke heap cepat (mis. VM seperti JVM dan CLR yang telah dioptimalkan untuk bahasa imperatif daripada bahasa fungsional). Hash mencoba juga mengizinkan penggunaan internal mutasi sebagai optimisasi.

Pohon merah-hitam kurang penting karena mereka tidak memiliki manfaat yang signifikan atas pohon yang seimbang tinggi tetapi memiliki kelemahan yang signifikan bahwa mereka tidak memungkinkan penyatuan, persimpangan, dan perbedaan yang efisien.

Demikian pula, pohon jari tidak jauh lebih baik dalam praktik.

Kapan masuk akal untuk menggunakan struktur data yang lebih penting?

Ketika kamus Anda diisi sekali dan kemudian hanya digunakan untuk pencarian, yaitu beku.

Ketika Anda membutuhkan kinerja (tabel hash yang layak seperti. NET Dictionarybiasanya 10-40 × lebih cepat daripada kamus fungsional murni umum).

Ketika Anda membutuhkan kamus lemah karena tidak ada kamus lemah murni yang berfungsi.

Jon Harrop
sumber