Wydajna niezmienna implementacja mapy?

Question

Zastanawiam się, czy jest realizacja mapie który jest:

• niezmienne, dzięki czemu można go używać w programowania funkcyjnego, a wysiłku zapewnić transakcji i współbieżności.
• Szybki. Sprawdziłem Binary Search Trees (RB, AVL) i Próby, ale żadne z nich nie wydawało się tak szybkie jak Hash Tables. Czy istnieje implementacja mapy obsługującej stały czas dla aktualizacji i wyszukiwania? (Lub przynajmniej bardzo szybki czas logarytmiczna)

W skrócie, jest tam funkcjonalna struktura danych, które można porównać z Hash Maps w wydajności?

Answer 1

Clojure ma niezmienne mapy. (link). Nie wiesz, z której struktury danych korzysta. Kod źródłowy Clojure da ci więcej informacji!

Answer 2

Scala ma także immutable maps, ale są one wolniejsze niż tablice hash. Podejrzewam, że odpowiedź na twoje pytanie brzmi: nie, nie znajdziesz niezmiennej implementacji mapy z O (1) oczekiwanym czasem operacji wstawiania/zapytania.

Answer 3

W każdym razie, aby podzielić się z ludźmi, są to dwa interesujące wpisy do blogów na temat implementacji Persistent Vectors w Scali przy użyciu Tries. Wspominają także o wdrożeniu Clojure, a także o nowej wersji IntMap w ostatnich wydaniach Scali.

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

Dla tych struktur danych, ja testowałem z kluczem jako liczby całkowite, ale jeszcze nie ciągi. Ponieważ moja prawdziwa aplikacja będzie używać łańcuchów jako kluczy, nie jestem pewien, czy implementacja będzie bardziej wydajna niż mapa skrótu. Co jeśli używam HashCode ciągu jako klucza, a następnie używam Persistent Vector do obsługi mapy? Będę używał 32-way trie do implementacji Persistent Vector. Zdaje się, że kolizja byłaby bardzo rzadka, a pamięć byłaby wydawana tylko odpowiednio. Ale nie jestem pewien co do faktycznej ilości potrzebnej do kopiowania aktualizacji.

Wkrótce opublikuję moje wyniki.

Answer 4

Nie czytałem tego, ale myślę, że niektórzy ludzie uważają Purely Functional Data Structures za Biblię dla tego rodzaju rzeczy.