Извлечь исходный ключ из словаря

Question

Есть ли способ прямого доступа к исходному ключевому объекту из словаря C# (где ключ является ссылочным типом)? Я видел этот вопрос на другом сайте (http://www.pcreview.co.uk/forums/get-original-key-object-dictionary-t3351718.html), и поскольку большинство респондентов не понимали, почему это разумный вопрос/не является симптомом плохого базового дизайна, я подробно расскажу ниже.

В обходных у меня до сих пор являются:

(а) перебрать ключи проверки равенства, что О (п) сложность :(

(б) поддерживать дополнительный пул стажера (например, другой словарь, который отображает ключи для себя). Это приводит нас к сложности O (1), но требует дополнительной памяти, дополнительной работы, когда элементы добавляются в словарь, риск неспособности получить эту координацию правильно ... ничто из этого не является фатальным но он не идеален и не понадобится, если словарь <> предложил метод извлечения ключа ключом.

В частности, у меня есть словарь < Состояние, список < Состояние >>, которое представляет граф состояний: каждый ключ представляет состояние конечного автомата, а связанное с ним значение представляет собой список соседних состояний, которые можно достичь непосредственно оттуда. например государство может представлять конфигурацию шахматной доски, а соседние состояния - это конфигурации, достижимые за один ход.

Я заполняю граф состояний, начиная с исходного состояния, строя список соседей, а затем рекурсивно вызывая подпрограмму народонаселения для каждого из этих соседей. На каждом этапе алгоритм проверяет, является ли соседнее состояние уже ключевым в словаре (иначе мы никогда не закончим). Состояние - это ссылочный тип (то есть класс) с переопределенными методами GetHashCode и Equals.

Семантически это работает нормально. Но теперь списки соседей - это разные копии состояний, а не оригинальная копия, поэтому, если есть N состояний со средним числом соседей M каждый, у нас есть объекты состояния NxM в памяти, когда нам действительно нужны только N объектов State и NxM ссылки на объекты государства. Помимо раздувания памяти, это замедляет тестирование равенства, потому что вы не можете воспользоваться ярлыком ссылки-равенства в 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... */ } 
    } 
} 

Answer 1

Вы можете создать «пул» из 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]; 
    } 
}