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
źródło
Store ! blahiStore ! bazbędzie musiało być sekwencyjneOdpowiedzi:
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.
źródło
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)).
źródło