Gibt es ein unveränderliches Open Source-Wörterbuch für C# mit schnellen With/Without-Methoden?

Question

Ich bin auf der Suche nach einem richtigen C# unveränderlichen Wörterbuch, mit schnellen Update-Methoden (die eine partielle Kopie des Wörterbuchs mit geringfügigen Änderungen erstellen). Ich habe selbst eine implementiert, mit Reißverschlüssen, um einen rot-schwarzen Baum zu aktualisieren, aber es ist nicht besonders schnell.

Mit 'unveränderlichem Wörterbuch' meine ich nicht nur readonly oder const. Ich möchte etwas, das recht schnell 'Mit' und 'Ohne', oder gleichwertig, Methoden hat, die ein Ding mit leichten Modifikationen zurückgeben, ohne das Original zu verändern.

Ein Beispiel aus einer anderen Sprache ist map in Scala

Answer 1

Es gibt einige implementation of the immutable dictionary auf read-only binäre AVL-Baum basiert.

/** 
* To modify, use the InsertIntoNew and RemoveFromNew methods 
* which return a new instance with minimal changes (about Log C), 
* so this is an efficient way to make changes without having 
* to copy the entire data structure. 
*/ 

Bitte nehmen Sie sich einen Blick auf die InsertIntoNew() Methode:

/** Return a new tree with the key-value pair inserted 
* If the key is already present, it replaces the value 
* This operation is O(Log N) where N is the number of keys 
*/ 
public ImmutableDictionary<K,V> InsertIntoNew(K key, V val) 
{ ... } 

Die RemoveFromNew() Methode:

/** Try to remove the key, and return the resulting Dict 
* if the key is not found, old_node is Empty, else old_node is the Dict 
* with matching Key 
*/ 
public ImmutableDictionary<K,V> RemoveFromNew(K key, out ImmutableDictionary<K,V> old_node) 
{ ... } 

Außerdem gibt es eine weitere Implementierung: Immutable AVL Tree in C#. Es hat dieselben O (log N) Lookup- und Insertionszeiten.