Pertanyaan ini terinspirasi oleh pertanyaan lain tentang apa yang baru dalam PFDS sejak penerbitan buku Okasaki pada tahun 1998 .
Saya akan mulai dengan dua pertanyaan yang saya miliki:
- Apakah ada struktur data set fungsional murni yang mendekati kecepatan tabel hash? Mencoba belum ada di sana.
- Apakah ada pohon jari yang berfungsi murni dengan O (1) ditambahkan? Sejauh ini yang terbaik adalah O (lg lg n), dirancang oleh Kaplan dan Tarjan.
Apa masalah struktur data murni fungsional lainnya yang terbuka?
Jawaban:
Saya akan menafsirkan pertanyaan dengan agak bebas. Untuk struktur data gaya Okasaki, memoisasi adalah bentuk mutasi implisit yang memiliki efek samping pada waktu berjalan. Jadi saya akan mengambil pertanyaan untuk memperhatikan struktur data persisten dalam arti yang ketat daripada struktur data dengan implementasi murni fungsional, yang merupakan bagian dari yang sebelumnya. Maksud saya adalah Anda harus dapat mengakses versi lama dari struktur data tanpa penalti, pohon versi dapat bercabang secara sewenang-wenang, dll
Dalam konteks itu, saya menganggap UNION-FIND yang gigih sebagai masalah terbuka yang penting. Ada kertas Conchon-Filliâtre yang disebutkan di utas lainnya. Seorang komentator telah mengemukakan masalah dengan apa yang disebut array persisten mereka: itu benar-benar hanya semi-persisten. Tapi misalkan Anda menggantinya dengan hash trie atau array lain yang benar-benar persisten yang berperilaku lebih baik dalam kasus terburuk (dan bisa dibilang rata-rata) tetapi lebih buruk dalam kasus terbaik. Itu masih menyisakan masalah penting:
Makalah ini memberikan bukti formal kebenaran dalam Coq. Tetapi mereka gagal mengatasi kompleksitas yang diamortisasi baik secara formal maupun informal. Sangat tidak jelas bagi saya bahwa mutasi di balik layar yang rumit menghasilkan kerumitan yang diamortisasi dalam semua kasus. Ketika saya berpikir terakhir tentang hal itu, saya merasa agak percaya diri bahwa saya dapat membuat contoh tandingan jika saya berusaha keras untuk itu. Bahkan jika saya salah tentang bagian terakhir itu, ketiadaan analisis yang tepat adalah kesenjangan besar; jelas bahwa analisis amortisasi klasik Trajan tentang UNION-FIND tidak secara langsung ditransfer.
sumber
Ini dia:
Apa yang setara dengan fungsi murni dari tabel hash yang lemah?
sumber