Jak wybrać funkcjonalną strukturę danych słownika?

Przeczytałem trochę o następujących strukturach danych:

Bagwell's Ideal Hash Próby
Dynamiczne tabele skrótów Larsona
Czerwono-czarne drzewa
Drzewa Patricia

... i jestem pewien, że jest tam wielu innych. Niewiele widziałem na temat tego, do czego każdy jest bardziej odpowiedni, ani dlaczego wybieram siebie nawzajem. Oto kilka pytań w tym zakresie:

O jakich strukturach funkcjonalnych słownika warto wiedzieć?
Jakie są zalety i wady tych podejść?
Kiedy warto zastosować bardziej imperatywną strukturę danych?

Liczby 2 i 3 są jednak ważniejsze. :-)

— Jason
źródło

Powiązane: Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki? (To pytanie nie ogranicza się do słowników.)

— Tsuyoshi Ito,

To pytanie (inne niż pozycja 3) ma wrażenie [dużej listy].

— Kaveh

dobrze byłoby wiedzieć, czy powyższe powiązane pytanie dotyczy twoich obaw, a jeśli nie, to dlaczego?

— Suresh Venkat

@Suresh - Odpowiedzi nr 1, ale 2 i 3 były ważniejsze. Głównie szukam ogólnego widoku, dzięki czemu mogę bardziej szczegółowo określić, które z nich warto zbadać.

— Jason

ok. więc może warto w takim razie edytować pytanie.

— Suresh Venkat

Odpowiedzi:

Naprawdę nie potrafię odpowiedzieć na nr 2, nie gubiąc się (istnieje zbyt wiele wymiarów, wzdłuż których można porównać te struktury), ale dla nr 3 odpowiedź jest dość prosta.

Użyj imperatywnej struktury danych, jeśli: (a) absolutnie nie ma aliasingu, lub (b) naprawdę musisz użyć aliasingu, aby uzyskać skuteczną transmisję.

Jeśli w ogóle nie ma aliasingu w strukturze danych, nie wykorzystuje się faktu, że funkcjonalne struktury danych są trwałe. Nie ma więc powodu, aby płacić za ich koszt. Istnieją dwa zastrzeżenia do tej rady. Po pierwsze, możesz preferować prostotę implementacji funkcjonalnej struktury danych: wdrożenie usuwania funkcjonalnego drzewa czerwono-czarnego sprawi, że będziesz przeklinać, ale wdrożenie usunięcia imperatywnego drzewa czerwono-czarnego ze wskaźnikami nadrzędnymi sprawi, że będziesz rozważać samobójstwo. Po drugie, przypisanie może być droższe niż się spodziewasz w języku gc'd, ponieważ zapisy mogą spowodować przeniesienie struktur danych z młodego pokolenia. Naprawdę nie mamy dobrej teorii efektów pamięci podręcznej i gc, więc nie masz wyboru, jak tylko przeprowadzić testy porównawcze.

Po drugie, jeśli potrzebujesz kanału rozgłoszeniowego, to wspólna struktura danych jest doskonałym sposobem na to. Dzięki aktualizacji o stałym czasie możesz arbitralnie powiedzieć wielu innym osobom, że wartość się zmieniła. (Właśnie dlatego union-find jest tak świetną strukturą danych.) Przy czysto funkcjonalnej konfiguracji albo musisz zmodyfikować wszystkie inne osoby, albo nadać im abstrakcyjne wskaźniki do stanu, w którym kodujesz ręcznie (co jest rodzajem rozwartości rzecz do zrobienia).

Jeśli albo nie chcesz uzasadniać aliasingu i własności obiektu, albo potrzebujesz wielu wersji tej samej struktury danych (powiedzmy, że potrzebujesz zarówno nowej, jak i starej wersji), po prostu użyj funkcjonalnej struktury danych.

Miejsce, w którym najtrudniej jest znaleźć tę radę, to algorytmy graficzne. Istnieje wiele naprawdę eleganckich algorytmów grafów imperatywnych, ale często zdarza się (np. Przy pisaniu kompilatorów), że chcesz także trwałości. Ludzie zazwyczaj próbują rozdzielić różnicę i używać fajnego algorytmu imperatywnego, ale próbują odrzucić wersję na bok, aby uzyskać wytrwałość. Jest to na ogół dość okropne, pełne błędów i podatne na utratę przewagi wydajności nadrzędnego algorytmu.

— Neel Krishnaswami
źródło

czym jest aliasing w tym kontekście?

— Suresh Venkat

Aliasing ma miejsce, gdy masz wiele odniesień do tego samego fragmentu danych. Jeśli dane te można modyfikować, wówczas rozumowanie dotyczące programu, który ich używa, musi wyraźnie uwzględniać wszystkie inne podprogramy, które mogą uzyskać do nich dostęp i je modyfikować. Jeśli ten fragment danych jest niezmienny, możesz lokalnie uzasadnić program, który go używa, ignorując aliasing, ponieważ nie znasz nikogo, kto może uzyskać dostęp do danych, nie może go zmodyfikować.

— Neel Krishnaswami

„ale implementacja usuwania w bezwzględnie czerwono-czarnym drzewie z nadrzędnymi wskaźnikami sprawi, że będziesz rozważać samobójstwo” Sprawdź lewostronne czerwono-czarne drzewa Sedgewick. Ogólny przypadek usuwania jest zredukowany do standardowego triku do delete-min, a samo usuwanie-min jest bardzo proste dla drzew LLRB. Nie są potrzebne wskaźniki nadrzędne.

— Per Vognsen

„Jest to ogólnie dość okropne, pełne błędów i podatne na utratę przewagi wydajności nadrzędnego algorytmu”. Artykuł Normana Ramseya na temat używania suwaków do grafów kontrolnych w optymalizującym kompilatorze stanowi przykład przekonującego kompromisu. W rzeczywistości masz lokalną stertę do obsługi łatwego i wydajnego przeplatania referencji między podstawowymi blokami w CFG, ale manipulowanie zawartością podstawowych bloków jest funkcjonalne (lub półfunkcyjne, w zależności od twojego filozoficznego poglądu na zamki błyskawiczne).

— Per Vognsen

O jakich strukturach funkcjonalnych słownika warto wiedzieć?

Drzewa binarne o zrównoważonej wysokości i ich próby są dobrym kompromisem. Również:

Drzewa Patricia.
Hash próbuje.

Jakie są zalety i wady tych podejść?

Drzewa binarne o zrównoważonej wysokości i ich próby są dobrym kompromisem dla kluczy atomowych. Próby są takie same dla kluczy, które są sekwencjami, np. Klucze ciągów.

Drzewa Patricia mogą być kilka razy szybsze, ale dopuszczają tylko klucze całkowite.

Próby skrótu mogą być kilka razy szybsze niż zrównoważone drzewa binarne, szczególnie jeśli haszowanie jest tańsze niż porównanie, a polimorfizm ma narzut (np. Ciągi w .NET), a zapisywanie wskaźników na stercie jest szybkie (np. Maszyny wirtualne, takie jak JVM i CLR, które zostały zoptymalizowany dla języków imperatywnych zamiast języków funkcjonalnych). Hash próbuje również zezwolić na wewnętrzne wykorzystanie mutacji jako optymalizacji.

Czerwono-czarne drzewa są mniej ważne, ponieważ nie mają żadnych znaczących zalet w porównaniu z drzewami o zrównoważonej wysokości, ale mają znaczną wadę, ponieważ nie pozwalają na skuteczne połączenie, skrzyżowanie i różnicę.

Podobnie drzewa palcowe nie są dużo lepsze w praktyce.

Kiedy warto zastosować bardziej imperatywną strukturę danych?

Gdy słownik zostanie zapełniony jeden raz, a następnie użyty tylko do wyszukiwania, tj. Zamrożony.

Gdy potrzebujesz wydajności (porządna tablica skrótów, taka jak .NET, Dictionaryjest zwykle 10-40 × szybsza niż jakikolwiek zwykły słownik funkcjonalny).

Kiedy potrzebujesz słownika słownika, ponieważ nie ma znanego, czysto funkcjonalnego słownika słownika.

— Jon Harrop
źródło