使用具有虚拟价值的字典是不好的做法

Question

假设我有两个项目集合,我想找到它们的交集.

由于这些只是值,而不是键值对,因此通常使用List而不是Dictionary.

然而,找到两个列表的交集需要嵌套循环,因此O(n ^ 2)复杂度,而对于Dictionary,所需时间是O(n).

如果我们处理大量项目,显然我们会尽量避免使用O(n ^ 2),所以答案很简单.我的问题更多的是项目数量很少而且不太可能增长的情况.

使用词典是否被认为是一种不好的做法:

即使性能不是一个问题,只是为了不断查找能力？我能想到的缺点是:

Answer 1

在几乎每种情况下,您都应该倾向于可读性和可维护性而不是性能,特别是在这种情况下,除非您的集合很大,否则差异可能是微不足道的.

因此,除非您通过使用列表的交集来证明存在重大的性能问题,否则您将引入一个很大的可维护性问题而几乎没有获得.

最后,考虑如果使用具有虚拟值的字典,则已经为cpu/time交换了内存.在某些情况下这可能无关紧要,在其他情况下可能会成为交易破坏者.

在一天结束时,这感觉就像过早优化,应该避免.正如评论中其他人所提到的,其他选项HashSet<T>可以满足您的性能目标,而无需编写混淆代码,并且可以利用更少的内存.

Answer 2

该HashSet<T>班是功能就像一个Dictionary<T>虚拟值。它也是专为这些类型的集合操作而设计的：

var hashset = new HashSet(myList1);    // this is O(n)
hashset.IntersectWith(myList2);        // this is O(n+m)

但是正如@DavidL 的回答一样，如果您的收藏量相对较小，那么麻烦确实不值得。