c# - 高速な「With/Without」メソッドを備えたC＃用のオープンソースの不変辞書はありますか？

Question

高速更新メソッド（わずかな変更を加えて辞書の部分的なコピーを作成する）を備えた、適切なC＃不変辞書を探しています。自分で実装し、ジッパーを使用して赤黒木を更新しましたが、それほど高速ではありません。

「不変の辞書」とは、単に読み取り専用または定数を意味するのではありません。元のメソッドを変更せずにわずかな変更を加えたものを返す、適度に高速な「With」メソッドと「Without」メソッド、または同等のメソッドが必要です。

別の言語の例はScalaの地図です

Answer 1

読み取り専用のバイナリAVLツリーに基づく不変辞書の実装がいくつかあります。

/**
 * 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.
 */

方法を見てくださいInsertIntoNew()：

/** 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)
{ ... }

RemoveFromNew()方法：

/** 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)
{ ... }

また、別の実装があります：C＃の不変AVLツリー。O（log N）のルックアップ時間と挿入時間は同じです。

その他の参考資料

• ミラーのようです：マスターのbrunet / ImmutableDictionary.cs・johnynek / brunet・GitHub。
• 似ているようです：マスターのImmutableCollections / ImmutableDictionary.cs・mono / ImmutableCollections・GitHub。