3 
Dictionary<string, Dictionary<string, ... >...> nestedDictionary;

上記Dictionaryは、one-to-many上から下まで各レベルで関係があります。葉オブジェクトがあり、下から始めて、辞書を作成し、それぞれを関連する親に追加するため、アイテムの追加は非常に簡単です...

私の問題は、内部の辞書でアイテムを見つけたいときです。次の 2 つのオプションがあります。

  1. アイテムをネストforeachして見つけ、アイテムを見つけた時点ですべてのループのスナップショットを作成し、すべてのループを終了します。次に、アイテムの系統が string1->string2->...->stringN であることがわかります。このソリューションの問題は、A) パフォーマンス B) スレッド セーフです (項目を削除したいので、子がない場合は親、子がない場合は親です...)
  2. 逆引き辞書の作成と追加項目の索引付け。Tupleすべての外部辞書の a のようなもの。次に、アイテムをキーとして追加し、すべての外側の親を Tupleメンバーとして追加します。Dictionary問題: A) 冗長性 B) main と同期した逆引き参照を維持するDictionary。

高速でスレッドセーフなソリューションのアイデアはありますか?

4

2 に答える 2

1

実際には のレベルが 2 つ以上あるようですDictionary。このタイプの構文を使用して可変数の辞書をサポートすることはできないため:

 Dictionary<string, Dictionary<string, ... >...> nestedDictionary;

2より大きい数であるとしか考えられません。3つだとしましょう。構築するデータ構造には、効率的に実行したい用途と操作があります。

次のような呼び出しが必要であると仮定します。

var dictionary = new ThreeLevelDictionary();
dictionary.Add(string1, string2, string3, value);
var value = dictionary[string1, string2, string3];
dictionary.Remove(string1, string2, string3);

そして（質問にとって重要）あなたが説明している逆引き：

var strings = dictionary.FindKeys(value);

これらが実行する必要があり、迅速に実行する必要がある操作である場合、使用できる 1 つのデータ構造はキーDictionary付きです。Tuple

public class ThreeLevelDictionary<TValue> : Dictionary<Tuple<string, string, string>, TValue>
{
    public void Add(string s1, string s2, string s3, TValue value)
    {
        Add(Tuple.Create(s1, s2, s3), value);
    }

    public TValue this[string s1, string s2, string s3]
    {
        get { return this[Tuple.Create(s1, s2, s3)]; }
        set { value = this[Tuple.Create(s1, s2, s3)]; }
    }

    public void Remove(string s1, string s2, string s3)
    {
        Remove(Tuple.Create(s1, s2, s3);
    }

    public IEnumerable<string> FindKeys(TValue value)
    {
        foreach (var key in Keys)
        {
            if (EqualityComparer<TValue>.Default.Equals(this[key], value))
                return new string[] { key.Item1, key.Item2, key.Item3 };
        }
        throw new InvalidOperationException("missing value");
    }
}

これで、パフォーマンスがボトルネックであることが示された場合に、別のハッシュテーブルを使用して逆引き参照ハッシュテーブルを作成する準備が整いました。 Dictionary

前の好きな操作が実行したいものではない場合、このデータ構造はニーズを満たさない可能性があります。いずれにせよ、データ構造で何をしたいのかを要約したインターフェースを最初に記述すれば、他の選択肢があるかどうかを簡単に確認できます。

于 2011-05-21T02:58:44.793 に答える
1

私はC5 コレクション ライブラリを直接使用した経験はほとんどありませんが、 TreeDictionaryクラスを使用できるようです。ツリーを検索、反復、および変更するための一連の便利なメソッドが付属しており、驚くほど詳細に文書化されています。

もう 1 つのオプションは、QuickGraph ライブラリ (NuGet または codeplex で見つけることができます) を使用することです。これにはグラフ理論の知識が必要ですが、それ以外は非常に便利なライブラリです。

どちらのライブラリでも、標準の BCL コレクションと同様に同時実行を処理する必要があります。

于 2011-05-21T03:40:09.717 に答える