Magazyn danych w pamięci w Haskell


9

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?


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:


1

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.


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,

1

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)).

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.