Performant Haskell hashed struktury.

Question

Performant Haskell hashed struktury.

Piszę program, który wykonuje Wiele wyszukiwania tabeli. W związku z tym przeglądałem dokumentację Haskella, kiedy natknąłem się na Data.Map (oczywiście), ale także Data.HashMap i Data.Hashtable. Nie jestem ekspertem od algorytmów haszujących i po sprawdzeniu pakietów wszystkie wydają się bardzo podobne. Tak się zastanawiałem:

1: Jakie są główne różnice, jeśli w ogóle?

2: który byłby najbardziej wydajny z dużą ilością wyszukiwań na mapach /tabelach ~ 4000 par klucz-wartość?

38

haskell hashmap hashtable

Author: providence, 2011-10-25

Source

3 answers

Oczywistą różnicą między Data.Map i Data.HashMap jest to, że pierwszy potrzebuje kluczy w Ord, drugi Hashable klucze. Większość wspólnych kluczy To oba, więc nie jest to decydujące kryterium. Nie mam żadnego doświadczenia z Data.HashTable, więc nie mogę tego skomentować.

API Data.HashMap i Data.Map są bardzo podobne, ale Data.Map eksportuje więcej funkcji, niektóre, takie jak alter są nieobecne w Data.HashMap, inne są dostarczane w strict i non-strict wariantach, podczas gdy Data.HashMap (zakładam, że miałeś na myśli hashmap z unordered-containers ) dostarcza leniwe i ścisłe API w oddzielnych modułach. Jeśli używasz tylko wspólnej części API, przełączanie jest naprawdę bezbolesne.

Jeśli chodzi o wydajność, Data.HashMap z unordered-containers ma dość szybkie wyszukiwanie, ostatnio mierzyłem, było wyraźnie szybsze niż Data.IntMap lub Data.Map, które posiada w szczególności (jeszcze nie wydany) oddział HAMT unordered-containers . Myślę, że dla wkładek, to było mniej więcej na równi z Data.IntMap i trochę szybszy niż Data.Map, ale jestem trochę rozmyty w tym.

Oba są wystarczająco wydajne dla większości zadań, dla tych zadań, gdzie nie są, prawdopodobnie będziesz potrzebował rozwiązania szytego na miarę. Biorąc pod uwagę, że pytasz konkretnie o poszukiwania, dałbym Data.HashMap krawędzi.

10

Author: Daniel Fischer,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-25 20:17:58

Data.HashTable'w dokumentacji S jest teraz napisane" użyj pakietu hashtables ". Jest fajny wpis na blogu wyjaśniający, dlaczego hashtables jest dobrym pakietem tutaj . Używa ST monad.

2

Author: gatoatigrado,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-06-29 14:10:18

score 46 · Accepted Answer

1: Jakie są główne różnice, jeśli w ogóle?

Data.Map.Map jest wewnętrznie zbalansowanym drzewem binarnym, więc jego złożoność czasowa dla wyszukiwań wynosi O (log n). Wierzę, że jest to struktura danych" persistent ", co oznacza, że jest zaimplementowana w taki sposób, że operacje mutacyjne dają nową kopię z zaktualizowanymi tylko odpowiednimi częściami struktury.
Data.HashMap.Map jest wewnętrznie Data.IntMap.IntMap, który z kolei jest zaimplementowany jako drzewo Patrycji; jego złożoność czasowa dla lookupów wynosi O(min (n, W)) gdzie W jest liczbą bitów w liczbie całkowitej. Jest też " wytrwały."
Data.HashTable.HashTable jest rzeczywistą tabelą skrótów, ze złożonością czasową O(1)dla wyszukiwań. Jest to jednak zmienna struktura danych-operacje są wykonywane na miejscu - więc utknąłeś w monadzie IO, Jeśli chcesz jej użyć.

2: który byłby najbardziej wydajny z dużą ilością wyszukiwań na mapach /tabelach ~ 4000 par klucz-wartość?

The best answer I can give you, niestety, jest " to zależy."Jeśli weźmiemy kompleks asymptotyczny dosłownie, otrzymamy O(log 4000) = około 12 dla Data.Map, o(min(4000, 64)) = 64 dla Data.HashMap I O(1) = 1 dla Data.HashTable. Ale to tak naprawdę nie działa... Musisz je wypróbować w kontekście kodu.