从字典中检索原始密钥
本文关键字:原始 密钥 检索 字典 | 更新日期: 2023-09-27 18:33:07
有没有办法直接从 C# 字典(其中键是引用类型(访问原始键对象?我在不同的网站(http://www.pcreview.co.uk/forums/get-original-key-object-dictionary-t3351718.html(上看到过这个问题,由于大多数回复者不明白为什么这是一个合理的问题/不是糟糕的底层设计的症状,所以我在下面给出了背景细节。
到目前为止,我有的解决方法是:
(a( 遍历键检查相等性,这是 O(n( 复杂度:(
(b( 维护一个额外的实习生池(例如,另一个将密钥映射到自己的词典(。这使我们达到 O(1( 的复杂性,但需要额外的内存、将项目添加到字典时的额外工作、无法正确进行这种协调的风险......这些都不是致命的,但它并不理想,如果字典<>提供了一种按键检索密钥的方法,则没有必要。
具体来说,我有一个字典<状态,列表><状态>>它代表一个状态图:每个键代表状态机的状态,关联的值是可以从那里直接访问的邻居状态的列表。 例如,状态可以代表棋盘的配置,而邻国将是单步即可到达的配置。状态>
我通过从初始状态开始填充状态图,构建邻居列表,然后递归调用每个邻居的人口例程。在每个阶段,算法都会检查邻居状态是否已经是字典中的键(否则我们将永远无法完成(。状态是具有重写的 GetHashCode 和 Equals 方法的引用类型(即类(。
从语义上讲,这工作正常。但是现在邻居列表是状态的不同副本而不是原始副本,所以如果有 N 个状态,每个状态平均有 M 个邻居,那么内存中有 NxM State 对象,而我们实际上只需要 N 个状态对象和 NxM 对 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... */ }
}
}
您可以创建一个State
的"池",然后在创建时使用 exist(如果已经创建了一个(。样本:
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];
}
}