3

C# ディクショナリ (キーが参照型の場合) から元のキー オブジェクトに直接アクセスする方法はありますか? この質問が別のサイト ( http://www.pcreview.co.uk/forums/get-original-key-object-dictionary-t3351718.html ) で行われているのを見たことがありますが、ほとんどの回答者はこの理由を理解していませんでした。は合理的な質問です/根本的な設計が悪いことを示すものではありません.背景の詳細​​を以下に示します.

これまでの回避策は次のとおりです。

(a) O(n) の複雑さである等価性をチェックするキーを繰り返します:(

(b) 追加のインターン プール (たとえば、キーを自分自身にマップする別の辞書) を維持します。これにより、O(1) の複雑さが得られますが、追加のメモリ、アイテムが辞書に追加されるときの追加の作業、この調整を正しく行わないリスクが必要です...これはいずれも致命的ではありませんが、理想的ではなく、次の場合には必要ありません。 Dictionary<> は、キーごとにキーを取得するメソッドを提供しました。

具体的には、状態グラフを表す Dictionary< State, List< State>> があります。各キーは状態マシンの状態を表し、関連付けられた値はそこから直接到達可能な隣接状態のリストです。たとえば、状態はチェス盤の構成を表すことができ、隣接する状態は 1 回の移動で到達可能な構成になります。

初期状態から開始し、近隣のリストを作成してから、それらの近隣のそれぞれに対して人口ルーチンを再帰的に呼び出すことで、状態グラフにデータを入力しています。各段階で、アルゴリズムは隣接状態がすでに Dictionary のキーであるかどうかをチェックします (そうでない場合は終了しません)。State は、オーバーライドされた GetHashCode および Equals メソッドを持つ参照型 (つまり、クラス) です。

意味的には、これは正常に機能します。しかし、現在、近隣のリストは元のコピーではなく状態の個別のコピーであるため、それぞれ平均 M の近隣を持つ N の状態がある場合、実際には N の State オブジェクトと NxM のみが必要な場合でも、メモリには NxM の State オブジェクトがあります。 State オブジェクトへの参照。メモリ フットプリントを爆破するだけでなく、Equals() の参照等価ショートカットを利用できないため、等価テストが遅くなります。

コメントからは、問題が明確ではないように思われるため、よりよく説明するための疑似コードを次に示します。

public class StateGraphExample
{
    public static void Main()
    {
        State initialState = State.GetInitialState();
        var graph = new Dictionary<State, List<State>>();
        BuildGraph(initialState, graph);
    }

    public static void BuildGraph(State state, Dictionary<State, List<State>> graph)
    {
        var neighbours = new List<State>();

        foreach (State.Move move in state.GetValidMoves())
            neighbours.Add(state.ApplyMove(move));

        graph[state] = neighbours;

        foreach (State neighbour in neighbours)
            if (!graph.ContainsKey(neighbour))
                BuildGraph(neighbour, graph);
    }

    public class State
    {
        //Lots of data members here...

        public static State GetInitialState()
        { /* Return State object representing initial state... */ }

        public class Move
        { /* Representation of a move that takes us from one State to another... */ }

        public List<State.Move> GetValidMoves()
        { /* Return valid moves from this State object... */ }

        public State ApplyMove(State.Move move)
        { /* Clones this State object, applies move to it and returns the result... */ }

        public override int GetHashCode()
        { /* Compute hash... */ }

        public override bool Equals(object obj)
        { /* Test equality... */ }

        private State Clone()
        { /* Clone self... */ }
    }
}
4

1 に答える 1

2

の「プール」を作成しState、作成するときに、すでに作成されている場合は既存のものを使用できます。サンプル:

class Sample : IEquatable<Sample>
{
  private int _params;
  private Sample(int params) { _params = params; }

  private static HashSet<Sample> _samples = new HashSet<Sample>();

  public static GetSample(int params)
  {
    Sample s = new Sample(params);
    if (!_samples.ContainsKey(s))
      _samples.Add(s);

    return _samples[s];
  }
}
于 2012-05-03T13:35:51.233 に答える