Wyliczenie zakresu ImmutableSortedDictionary według klucza

11

Czytałam o C # 's ImmutableSortedDictionaryw System.Collections.Immutablei myślenie o tym, jak ją stosować w moim programie. Bardzo lubię C ++ lower_boundi upper_bound(patrz tutaj ), i raczej spodziewałem się czegoś w rodzaju wyszukiwania zakresów. Jednak podobne metody wydają się dziwnie nieobecne w dokumentacji . Czy coś brakuje? Czy też MS naprawdę zapewnia posortowany słownik bez skutecznego dostępu do posortowanych zakresów? Nie wydaje się, że to coś, co można zrobić na jednym IEnumerablez klawiszy, jak powiedzmy metodę rozszerzenia, więc jestem trochę zaskoczony, że nie widzę czegoś dostarczonego bezpośrednio przez kolekcję.

c# .net algorithm immutability immutable-collections J Trana
źródło
Eric Lippert udostępnił niezmienną implementację drzewa AVL w 2008 roku. Z komentarzy nie sądzę, aby była jeszcze zoptymalizowana pod kątem szybkości lub wydajności, ale IBinarySearchTree<K,V>implementacja wygląda bliżej tego, czego się spodziewałam. Zastanawiam się, czy kiedykolwiek w dalszym ciągu majstrował przy tym?
J Trana,
ImmutableList<T>Klasa jest również zaimplementowany jako drzewo AVL. Z kodu źródłowego :/// The root node of the AVL tree that stores this set.
Theodor Zoulias,
Czy wiesz, czy oznaczają one, że lista używa wartości AVL true do implementacji niezmienności, czy też samo drzewo AVL jest niezmienne? (może to nie ma znaczenia, ponieważ i tak nie wystawiają drzewa).
J Trana
Oto zalety ImmutableList<T>(wspierane przez drzewo AVL) nad ImmutableArray<T>(wspierane przez tablicę), zgodnie z dokumentacją . Powody korzystania z niezmiennej listy: 1) Aktualizowanie danych jest powszechne lub liczba elementów nie powinna być niewielka. 2) Aktualizacja kolekcji ma większe znaczenie dla wydajności niż iteracja zawartości.
Theodor Zoulias
Wynika to z faktu, że dodając lub usuwając element z dużego drzewa AVL, można uzyskać nowe drzewo bez niszczenia oryginalnego, udostępniając większość węzłów i tworząc tylko kilka nowych węzłów. ( Trwała struktura danych - Drzewa )
Theodor Zoulias

Odpowiedzi:

9

To irytujące, że dostępne wbudowane kolekcje nie oferują pełnego zestawu funkcji (takich jak SortedDictionarybrak BinarySearchmetody), zmuszając nas do szukania rozwiązań innych firm (takich jak biblioteka C5 ).

W twoim przypadku zamiast ImmutableSortedDictionarymożesz prawdopodobnie użyć a ImmutableSortedSet, osadzając wartości w kluczach i używając odpowiedniego modułu porównującego. Przynajmniej interfejs API tej klasy zawiera właściwości Mini Max.

Theodor Zoulias
źródło
2
Na marginesie, inna niezmienna klasa ImmutableList<T>, jest zaimplementowana wewnętrznie jako drzewo . Jest więc 10 razy wolniejszy i przydziela 12 razy więcej pamięci niż a List<T>. Użyj ImmutableArray<T>zamiast tego.
Theodor Zoulias
1
Hehe, używam już C5, ale chcę zobaczyć, co było dostępne dla niezmiennych kolekcji (poza migawkami). Dzięki! Mam nadzieję, że ktoś rozwiązał to w jakikolwiek sposób, ale będę pamiętaćImmutableSortedSet
J Trana
@TheodorZoulias jaki jest sens posiadania metody BinarySearch w SortedDictionary, kiedy metoda TryGetValue działa w log (N)? patrz tutaj
Giorgi Chkhikvadze
2
@GiorgiChkhikvadze BinarySearch może dać ci następny element, który jest większy niż szukany element, na wypadek, gdyby nie znaleziono dokładnego dopasowania.
Theodor Zoulias
1
@GiorgiChkhikvadze Prawdopodobnie największą różnicą tutaj jest to, że zwracana wartość nie jest tylko pojedynczą wartością w kolekcji, ale raczej sposobem skutecznego indeksowania w kolekcji. Metoda BinarySearch jest wyjątkowa nie tylko dlatego, że efektywnie znajduje wartość, ale także dlatego, że znajduje indeks nawet w przypadku braku, jak zauważył Theodor - co pozwala na szybki dostęp np. Do tablicy. Jednak w przypadku drzewa indeks całkowity może nie być skutecznym sposobem dostępu do struktury; C ++ rozwiązuje to poprzez użycie obiektu iteratora (choć z jego własną złożonością).
J Trana