Datastore dalam memori di Haskell

Saya ingin mengimplementasikan datastore dalam memori untuk layanan web di Haskell. Saya ingin menjalankan transaksi di STMmonad.

Ketika saya google hash table steam Haskell saya hanya mendapatkan ini: Data. BTree. HashTable. STM.Nama modul dan kerumitan menyarankan ini diterapkan sebagai pohon. Saya akan berpikir bahwa array harus lebih efisien untuk tabel hash yang bisa berubah.

Apakah ada alasan untuk menghindari penggunaan array untuk STMhashtable? Apakah saya mendapatkan sesuatu dengan tabel hash uap ini atau haruskah saya menggunakan referensi uap ke IntMap?

data-structures haskell Simon Bergot
sumber

Catatan, jika Anda menggunakan `TVar IntMap

Daniel Gratzer

@ jozefg apa maksudmu

Simon Bergot

Oh maaf, rupanya saya kehilangan sisanya, saya akan mengatakan Anda akan mendapatkan paralelisme jelek karena memodifikasi Store ! blahdan Store ! bazharus berurutan

Daniel Gratzer

Ketika Anda mengatakan "data dalam memori", apakah maksud Anda seperti keadaan asam ?

Api Ptharien

@ Ptharien'sFlame Saya mencari sesuatu yang benar-benar lebih sederhana dari itu. Sebenarnya saya mencari peta bisa berubah sederhana yang berjalan di stm monad. Saya tahu saya memiliki beberapa opsi untuk ini, dan saya mencoba mengevaluasi mana yang lebih baik.

Simon Bergot

Jawaban:

Masalah dengan implementasi tabel hash berdasarkan langsung pada array adalah bahwa beberapa operasi di atasnya pasti akan memerlukan pengubahan ukuran array waktu linier (yaitu, menciptakan array yang lebih besar / lebih kecil dan menyalin semua data ke dalamnya). Ada beberapa algoritma standar yang mendekati masalah ini, seperti Linear Hashing atau Cuckoo Hashing .

Belum lama ini algoritma lain bernama Hash Array Mapped Trie muncul, yang memperoleh popularitas besar di berbagai bahasa fungsional seperti Clojure, Scala dan, tentu saja, Haskell (dengan perpustakaan "wadah tidak berurutan" dan "hamtmap") karena dukungan dari persisten struktur data.

Belum lama ini saya merilis perpustakaan kontainer khusus-STM berdasarkan algoritma yang bernama "stm-container", yang seharusnya sesuai dengan tugas Anda dengan sempurna. Anda juga dapat melihat posting blog pengantar , yang mencakup motivasi di belakang perpustakaan dan memberikan tolok ukur.

Nikita Volkov
sumber

Terima kasih telah membalas! Saya belum menguji paket Anda tetapi terlihat menarik. Saya akan memeriksanya nanti, tetapi berdasarkan posting Anda, saya siap untuk percaya bahwa itu sesuai dengan tujuan awal saya.

Simon Bergot

Referensi implementasi Anda adalah bagian dari paket untuk mengimplementasikan B-Tree bersamaan. The HashTable sendiri diimplementasikan sebagai array objek TVars Data.Map.

Nilai kompleksitas yang dikutip adalah yang terburuk . Ingat bahwa hashtables biasanya O (N) kasus terburuk untuk pencarian, penyisipan, dan penghapusan. Menggunakan Map untuk bucket membawanya ke O (log (N)).

pengguna2313838
sumber