Aufzählung des ImmutableSortedDictionary-Bereichs nach Schlüssel

Ich lese über C # 's ImmutableSortedDictionaryin System.Collections.Immutableund darüber nachzudenken , wie es in meinem Programm zu bewerben. Ich mag C ++ lower_boundund upper_bound(siehe hier ) sehr, und ich hatte eher erwartet, etwas Ähnliches für Range-Lookups zu sehen. Ähnliche Methoden scheinen jedoch in der Dokumentation seltsamerweise nicht vorhanden zu sein . Vermisse ich etwas Oder bietet MS wirklich ein sortiertes Wörterbuch ohne effizienten Zugriff auf die sortierten Bereiche? Das scheint nicht gerade etwas zu sein, das man an einem IEnumerableder Schlüssel als Erweiterungsmethode tun könnte , also bin ich ein bisschen verwirrt, dass ich etwas nicht sehe, das direkt von der Sammlung bereitgestellt wird.

c# .net algorithm immutability immutable-collections J Trana
quelle

Eric Lippert teilte 2008 eine unveränderliche AVL-Baumimplementierung mit. Aus den Kommentaren geht hervor, dass sie noch nicht besonders auf Geschwindigkeit oder Effizienz optimiert wurde, aber die IBinarySearchTree<K,V>Implementierung sieht näher an dem aus, was ich erwarten würde. Ich frage mich, ob er jemals weiter daran herumgebastelt hat.

J Trana

Die ImmutableList<T>Klasse ist auch als AVL-Baum implementiert. Aus dem Quellcode :/// The root node of the AVL tree that stores this set.

Theodor Zoulias

Wissen Sie, ob sie bedeuten, dass die Liste eine AVL true verwendet, um die Unveränderlichkeit zu implementieren, oder ob der AVL-Baum selbst unveränderlich ist? (Vielleicht spielt es keine Rolle, da sie den Baum sowieso nicht freilegen).

J Trana

Hier sind die Vorteile des ImmutableList<T>(von einem AVL-Baum unterstützt) gegenüber dem ImmutableArray<T>(von einem Array unterstützt) gemäß der Dokumentation . Gründe für die Verwendung einer unveränderlichen Liste: 1) Das Aktualisieren der Daten ist üblich oder es wird nicht erwartet, dass die Anzahl der Elemente gering ist. 2) Das Aktualisieren der Sammlung ist leistungskritischer als das Iterieren des Inhalts.

Theodor Zoulias

Dies liegt daran, dass Sie beim Hinzufügen oder Löschen eines Elements aus einem großen AVL-Baum einen neuen Baum erhalten können, ohne den ursprünglichen zu zerstören, indem Sie die meisten Knoten gemeinsam nutzen und nur wenige neue Knoten erstellen. ( Persistente Datenstruktur - Bäume )

Theodor Zoulias

Antworten:

Es ist irritierend, dass die verfügbaren integrierten Sammlungen nicht alle Funktionen bieten (wie das SortedDictionaryFehlen einer BinarySearchMethode), was uns dazu zwingt, nach Lösungen von Drittanbietern (wie der C5-Bibliothek ) zu suchen .

In Ihrem Fall ImmutableSortedDictionarykönnten Sie anstelle von a wahrscheinlich a verwenden ImmutableSortedSet, die Werte in die Schlüssel einbetten und einen geeigneten Vergleicher verwenden. Zumindest die API dieser Klasse enthält die Eigenschaften Minund Max.

Theodor Zoulias
quelle

Als Randnotiz wird eine andere unveränderliche Klasse, die ImmutableList<T>, intern als Baum implementiert . Es ist also 10-mal langsamer und weist 12-mal mehr Speicher als a zu List<T>. Verwenden Sie ImmutableArray<T>stattdessen.

Theodor Zoulias

Hehe, ich benutze C5 bereits, schaue aber nach, was für unveränderliche Sammlungen verfügbar war (jenseits von Schnappschüssen). Vielen Dank! Ich werde hoffen, dass jemand anderes dies in irgendeiner Form gelöst hat, aber ich werde dieImmutableSortedSet

J Trana

@TheodorZoulias Was bringt es, die BinarySearch-Methode in SortedDictionary zu haben, wenn die TryGetValue-Methode in log (N) arbeitet? siehe hier

Giorgi Chkhikvadze

@GiorgiChkhikvadze Die BinarySearch kann Ihnen das nächste Element geben, das größer ist als das gesuchte Element, falls keine genaue Übereinstimmung gefunden wird.

Theodor Zoulias

@GiorgiChkhikvadze Der wahrscheinlich größte Unterschied besteht darin, dass der Rückgabewert nicht nur ein einzelner Wert in der Sammlung ist, sondern vielmehr eine Möglichkeit, effizient in die Sammlung zu indizieren. Die Methode BinarySearch ist nicht nur deshalb besonders, weil sie den Wert effizient findet, sondern weil sie auch im Falle eines Fehlschlags einen Index findet, wie Theodor betonte - was einen schnellen Zugriff auf z. B. ein Array ermöglicht. Im Fall eines Baums ist ein ganzzahliger Index möglicherweise keine effiziente Möglichkeit, auf die Struktur zuzugreifen. C ++ löst dies durch die Verwendung eines Iteratorobjekts (wenn auch mit seiner eigenen Komplexität).

J Trana