找出两个ICollection 集合是否包含相同对象的最快方法
https://stackoverflow.com/questions/308476
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
找出两个ICollection<T>集合是否包含完全相同的条目的最快方法是什么？蛮力很清楚，我想知道是否有更优雅的方法。
我们正在使用C＃2.0，因此请尽可能不要扩展方法！
编辑：答案对于有序集合和无序集合都是很有趣的，并且希望每个答案都不同。
解决方案
其他提示
如果集合的计数相同，则首先比较集合的。 Count ，然后对所有元素进行蛮力比较。最坏的情况是O（n）。在这种情况下，元素的顺序必须相同。
第二种情况是顺序不相同，您需要使用字典来存储集合中找到的元素数：这是一种可能的算法
- 比较集合计数：如果它们不同则返回false
- 迭代第一个集合
- 如果字典中不存在该项，则添加并输入键=项，值= 1（计数）
- 如果item存在，则将其计数增加到字典中；
- 迭代第二个集合
- 如果项不在词典中，则返回false
- 如果项目在字典的减量计数中
- 如果count== 0，则删除项目；
- 返回Dictionary.Count== 0;
对于有序集合，可以使用SequenceEqual()定义的System.Linq.Enumerable扩展方法：
通用标签
您是指相同的条目还是相同的条目？
无论如何，假设您要比较它们是否包含相同顺序的相同条目，那么“暴力破解”实际上是C＃2.0中的唯一选择。我知道您所说的不优雅是什么意思，但是如果原子比较本身是O（1），则整个过程应该在O（N）中，这并不坏。
如果条目需要具有相同的顺序（除了相同），那么我建议-作为一种优化-您同时迭代两个集合，并比较每个集合中的当前条目。否则，蛮力是必经之路。
哦，还有另一个建议-您可以为集合类重写Equals并在其中实现相等性（不过，这取决于您的项目）。
同样，使用C5库（具有两个集合），您可以使用： 通用标签
C5库包含一个启发式方法，该方法实际上首先测试了这两个集合的未排序哈希码（请参阅C5.ICollection<T>.GetUnsequencedHashCode()），因此，如果两个集合的哈希码不相等，则不需要遍历每个要测试的项目为了平等。
还有一点需要注意的是，C5.ICollection<T>继承自System.Collections.Generic.ICollection<T>，因此您可以在仍使用.NET接口的同时使用C5实现（尽管您可以通过.NET的小巧接口访问较少的功能）。
蛮力为O（n）-比较所有元素（假设它们已排序），我认为这是您可以做的最好的事情-除非数据的某些属性使其变得更容易。
我猜为未排序的情况，它的O（n * n）。
在这种情况下，我认为基于合并排序的解决方案可能会有所帮助
例如，您可以重新建模以便只有一个集合吗？或3个集合，一个仅用于集合A中的集合，一个仅用于集合B中的集合，并且在两个集合中均是-因此，如果仅A和B都是空的，那么它们是相同的...我可能正好选择了错误的切线在这里...
