将C#字典与"黄金标准"字典进行比较的最快方法是什么？

Question

我有一个已知良好的字典,并在运行时我需要建立一个新的字典和运行检查,看它是否具有相同的键值对作为已知的正确解释(按不同的顺序潜在的插入),并采取如果它有一条路径,如果没有则另一条路径.我不一定需要序列化整个已知良好的字典(我可以使用哈希,例如),但我需要的是具有对已知良好的字典足够的信息,一些磁盘上的数据,以便进行比较,如果不娱乐.最快的方法是什么？我可以使用SortedDictionary,但初始化和添加值所需的时间量计入此任务的速度.

具体例子:

考虑一个<String,List<String>>看起来像这样的字典(显然没有特定的顺序):

{ {"key1", {"value1", "value2"} }, {"key2", {"value3", "value4"} } }  

我创建了一次Dictionary并在磁盘上保存了一些关于它的信息(一个完整的序列化,一个哈希,等等).然后,在运行时,我执行以下操作:

Dictionary<String,List<String>> d1 = new Dictionary<String,List<String>> ();
Dictionary<String,List<String>> d2 = new Dictionary<String,List<String>> ();
Dictionary<String,List<String>> d3 = new Dictionary<String,List<String>> ();

String key11 = "key1";
String key12 = "key1";
String key13 = "key1";
String key21 = "key2";
String key22 = "key2";
String key23 = "key2";

List<String> value11 = new List<String> {"value1", "value2"};
List<String> value12 = new List<String> {"value1", "value2"};
List<String> value13 = new List<String> {"value1", "value2"};
List<String> value21 = new List<String> {"value3", "value4"};
List<String> value22 = new List<String> {"value3", "value4"};
List<String> value23 = new List<String> {"value3", "value5"};

dict1.add(key11, value11);
dict1.add(key21, value21);
dict2.add(key22, value22);
dict2.add(key12, value12);
dict3.add(key13, value13);
dict3.add(key23, value23);

dict1.compare(fileName); //Should return true
dict2.compare(fileName); //Should return true
dict3.compare(fileName); //Should return false

同样,如果在启动的总时间,从比较收益()更快,我可以更改此代码以使用SortedDictionary(或其他任何东西)来代替,但我不能保证订货,我需要一些比较一致.compare()可以加载序列化并遍历字典,它可以序列化内存中的字典并将序列化与文件名进行比较,或者它可以执行任何其他操作.

Answer 1

解决方案一:使用set equality.

如果词典的大小不同,你知道它们是不相等的.

如果它们具有相同的大小,则从一个字典构建一个可变的哈希密钥集.从中删除其他字典中的所有键.如果您尝试删除不存在的密钥,则密钥集不相等,您知道哪个密钥是问题所在.

或者,构建两个哈希集并获取它们的交集; 生成的交集应该是原始集的大小.

这需要O(n)时间和O(n)空间.

一旦你知道密钥集是相等的,那么一次一个地检查所有密钥,获取值,并进行值的比较.由于值是序列,因此请使用SequenceEquals.这需要O(n)时间和O(1)空间.

解决方案二:对密钥进行排序

同样,如果字典大小不同,你知道它们是不相等的.

如果它们具有相同的大小,则对两组键进行排序并对它们执行SequenceEquals; 如果密钥序列不相等,则字典不相等.

这需要O(n lg n)时间和O(n)空间.

如果成功,那么再次,一次检查一个键并比较值.

解决方案三:

再次,检查字典,看它们是否大小相同.

如果是,则迭代一个字典的键并检查该键是否存在于另一个字典中.如果没有,那么他们就不平等了.如果是,则检查相应的值是否相等.

这是时间上的O(n)和空间中的O(1).

如何选择这些可能的解决方案？这取决于可能的故障模式是什么,以及您是否需要知道丢失或额外密钥是什么.如果可能的故障模式是坏密钥,那么选择一个专注于首先找到坏密钥的解决方案可能更有效,并且如果所有密钥都没有问题,则仅检查错误值.如果可能的故障模式是一个错误的值,那么第三个解决方案可能是最好的,因为它会优先考虑提前检查值.