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. :-)
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.
źródło
Drzewa binarne o zrównoważonej wysokości i ich próby są dobrym kompromisem. Również:
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.
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.
źródło