Magazyn danych w pamięci w Haskell

Chcę wdrożyć magazyn danych w pamięci dla usługi internetowej w Haskell. Chcę uruchamiać transakcje w STMmonadzie.

Kiedy google hash table steam Haskell otrzymuję tylko to: Data. BTree. HashTable. STM.nazwa modułu i złożoność sugerują, że jest to zaimplementowane jako drzewo. Myślę, że tablica powinna być bardziej wydajna dla zmiennych tablic mieszających.

Czy istnieje powód, dla którego należy unikać używania tablicy jako tablicy STMmieszającej? Czy mogę coś zyskać dzięki temu stołowi mieszającemu, czy powinienem po prostu użyć referencji Steam IntMap?

data-structures haskell

— Simon Bergot
źródło

Uwaga: jeśli używasz `TVar IntMap

— Daniel Gratzer

@ jozefg co masz na myśli?

— Simon Bergot,

Och, przepraszam, najwyraźniej straciłem resztę tego, miałem powiedzieć, że dostaniesz gównianą równoległość, ponieważ modyfikowanie Store ! blahi Store ! bazbędzie musiało być sekwencyjne

— Daniel Gratzer

Kiedy mówisz „magazyn danych w pamięci”, masz na myśli stan kwasowy ?

— Ptharien's Flame

@ Ptharien'sFlame Szukam czegoś naprawdę prostszego niż to. Właściwie szukam prostej mapy, która może być zmienna, która działa w stm monada. Wiem, że mam na to kilka opcji i próbuję ocenić, która z nich jest lepsza.

— Simon Bergot,

Odpowiedzi:

Problem z implementacją tablicy skrótów opartej bezpośrednio na tablicy polega na tym, że niektóre operacje na niej nieuchronnie wymagają liniowego zmiany rozmiaru tablicy czasu (tj. Utworzenie większej / mniejszej tablicy i skopiowanie do niej wszystkich danych). Istnieje wiele standardowych algorytmów, które podchodzą do tego problemu, takich jak Hashing liniowy lub Hashing z kukułką .

Nie tak dawno temu pojawił się inny algorytm o nazwie Hash Array Mapped Trie , który zyskał dużą popularność w językach funkcjonalnych, takich jak Clojure, Scala i, oczywiście, Haskell (z bibliotekami „nieuporządkowanych” i „hamtmap”) dzięki obsłudze trwałych struktury danych.

Niedawno wydałem wyspecjalizowaną bibliotekę kontenerów STM opartą na tym algorytmie o nazwie „stm-container”, która powinna idealnie pasować do twojego zadania. Możesz także zapoznać się ze wstępnym postem na blogu , który dotyczy motywacji związanej z biblioteką i zapewnia standardy.

— Nikita Volkov
źródło

Dzięki za odpowiedź! Nie przetestowałem twojego pakietu, ale wygląda interesująco. Sprawdzę to później, ale w oparciu o Twój post jestem gotów uwierzyć, że pasuje do mojego pierwotnego celu.

— Simon Bergot,

Implementacja, do której się odwołujesz, jest częścią pakietu do implementacji współbieżnego B-drzewa. Sam HashTable jest zaimplementowany jako tablica TVarów obiektów Data.Map.

Podane wartości złożoności są najgorsze . Pamiętaj, że tablice skrótów to zazwyczaj najgorszy przypadek O (N) wyszukiwania, wstawiania i usuwania. Użycie mapy dla segmentów sprowadza ją do O (log (N)).

— użytkownik2313838
źródło