比较两个集合是否相等，无论它们中的项顺序如何
我想比较两个集合(在C＃中)，但是我不确定有效实现这一点的最佳方法。
我已经阅读了有关Enumerable.SequenceEqual的其他主题，但这并不是我想要的。
在我的情况下，如果两个集合都包含相同的项(无论顺序如何)，则它们将相等。
例子：
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1 == collection2; // true
我通常要做的是遍历一个集合的每个项目，看是否在另一个集合中，然后遍历另一个集合的每个项目，看它是否在第一个集合中。 (我先比较一下长度)。
if (collection1.Count != collection2.Count)
return false; // the collections are not equal
foreach (Item item in collection1)
{
if (!collection2.Contains(item))
return false; // the collections are not equal
}
foreach (Item item in collection2)
{
if (!collection1.Contains(item))
return false; // the collections are not equal
}
return true; // the collections are equal
但是，这并不完全正确，并且可能不是比较两个集合是否相等的最有效方法。
我能想到的一个例子是错误的：
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}
这将与我的实现相同。我应该只计算找到每个项目的次数并确保两个集合中的计数相等吗？
这些示例使用某种C语言(我们称其为伪C＃)，但是用我们希望使用的任何语言给出答案，都没有关系。
注意：为了简单起见，我在示例中使用了整数，但是我也希望能够使用引用类型的对象(它们不能正确用作键，因为仅比较对象的引用，而不是内容)。
解决方案
回答
创建一个字典" dict"，然后为第一个集合中的每个成员执行dict [member] ++;
然后，以相同的方式遍历第二个集合，但是对每个成员执行dict [member]-。
最后，遍历字典中的所有成员：
private bool SetEqual (List<int> left, List<int> right) {
if (left.Count != right.Count)
return false;
Dictionary<int, int> dict = new Dictionary<int, int>();
foreach (int member in left) {
if (dict.ContainsKey(member) == false)
dict[member] = 1;
else
dict[member]++;
}
foreach (int member in right) {
if (dict.ContainsKey(member) == false)
return false;
else
dict[member]--;
}
foreach (KeyValuePair<int, int> kvp in dict) {
if (kvp.Value != 0)
return false;
}
return true;
}
编辑：据我所知，这与最有效的算法的顺序相同。假设字典使用O(1)查找，此算法为O(N)。
回答
埃里克森几乎是对的：由于我们希望匹配重复项，因此我们需要一个手提袋。在Java中，这看起来像：
(new HashBag(collection1)).equals(new HashBag(collection2))
我确定Chas是内置的Set实现。我会先使用它；如果性能存在问题，则可以始终使用其他Set实现，但可以使用相同的Set接口。
回答
一个简单而有效的解决方案是对两个集合进行排序，然后比较它们是否相等：
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));
该算法为O(N * logN)，而上述解决方案为O(N ^ 2)。
如果集合具有某些属性，则可以实现更快的解决方案。例如，如果两个集合都是哈希集，则它们不能包含重复项。同样，检查哈希集是否包含某些元素也非常快。在这种情况下，类似于算法可能最快。
回答
这是我(在D.Jennings的大力影响下)比较方法的通用实现(在C＃中)：
/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
/// <summary>
/// Compares the content of two collections for equality.
/// </summary>
/// <param name="foo">The first collection.</param>
/// <param name="bar">The second collection.</param>
/// <returns>True if both collections have the same content, false otherwise.</returns>
public bool Execute(ICollection<T> foo, ICollection<T> bar)
{
// Declare a dictionary to count the occurence of the items in the collection
Dictionary<T, int> itemCounts = new Dictionary<T,int>();
// Increase the count for each occurence of the item in the first collection
foreach (T item in foo)
{
if (itemCounts.ContainsKey(item))
{
itemCounts[item]++;
}
else
{
itemCounts[item] = 1;
}
}
// Wrap the keys in a searchable list
List<T> keys = new List<T>(itemCounts.Keys);
// Decrease the count for each occurence of the item in the second collection
foreach (T item in bar)
{
// Try to find a key for the item
// The keys of a dictionary are compared by reference, so we have to
// find the original key that is equivalent to the "item"
// You may want to override ".Equals" to define what it means for
// two "T" objects to be equal
T key = keys.Find(
delegate(T listKey)
{
return listKey.Equals(item);
});
// Check if a key was found
if(key != null)
{
itemCounts[key]--;
}
else
{
// There was no occurence of this item in the first collection, thus the collections are not equal
return false;
}
}
// The count of each item should be 0 if the contents of the collections are equal
foreach (int value in itemCounts.Values)
{
if (value != 0)
{
return false;
}
}
// The collections are equal
return true;
}
}
回答
我们可以使用哈希集。查看SetEquals方法。
回答
有许多解决此问题的方法。
如果我们不关心重复项，则不必对两者都进行排序。首先，请确保它们具有相同数量的项目。之后，对其中一个集合进行排序。然后对已排序集合中第二个集合中的每个项目进行bin搜索。如果找不到给定的项目，则停止并返回false。
其复杂性：
对第一个集合进行排序：NLog(N)
从第二个到第一个搜索每个项目：NLOG(N)
因此，假设它们匹配，我们最终得到2 * N * LOG(N)，然后查找所有内容。这类似于对两者进行分类的复杂性。如果有区别，这也使我们可以尽早停止。
但是，请记住，如果在进行此比较之前对两者都进行了排序，并且尝试使用qsort之类的方法进行排序，则排序会更加昂贵。为此进行了优化。
另一个选择对我们知道元素范围的小型集合非常有用，这是使用位掩码索引。这将为我们提供O(n)性能。
另一种选择是使用哈希并查找它。对于小型集合，通常最好进行排序或者位掩码索引。哈希表的缺点是位置较差，因此请记住这一点。
同样，只有在我们不关心重复项的情况下。如果要考虑重复项，请对两者进行排序。
回答
编辑：我意识到，一旦我提出这确实只适用于集-它不会正确处理具有重复项的集合。例如，从该算法的角度来看，{1，1，2}和{2，2，1}被认为是相等的。但是，如果集合是集合(或者可以通过这种方式来衡量它们的相等性)，希望以下内容对我们有用。
我使用的解决方案是：
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;
Linq在后台执行字典操作，所以它也是O(N)。 (请注意，如果集合的大小不同，则为O(1))。
我使用Daniel建议的" SetEqual"方法，Igor建议的OrderBy / SequenceEquals方法以及我的建议进行了完整性检查。结果如下，显示了Igor的O(N * LogN)和我的和Daniel的O(N)。
我认为Linq相交代码的简单性使其成为首选的解决方案。
__Test Latency(ms)__ N, SetEquals, OrderBy, Intersect 1024, 0, 0, 0 2048, 0, 0, 0 4096, 31.2468, 0, 0 8192, 62.4936, 0, 0 16384, 156.234, 15.6234, 0 32768, 312.468, 15.6234, 46.8702 65536, 640.5594, 46.8702, 31.2468 131072, 1312.3656, 93.7404, 203.1042 262144, 3765.2394, 187.4808, 187.4808 524288, 5718.1644, 374.9616, 406.2084 1048576, 11420.7054, 734.2998, 718.6764 2097152, 35090.1564, 1515.4698, 1484.223
回答
在没有重复和没有顺序的情况下，可以使用以下EqualityComparer允许将集合用作字典键：
public class SetComparer<T> : IEqualityComparer<IEnumerable<T>>
where T:IComparable<T>
{
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == second)
return true;
if ((first == null) || (second == null))
return false;
return first.ToHashSet().SetEquals(second);
}
public int GetHashCode(IEnumerable<T> enumerable)
{
int hash = 17;
foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();
return hash;
}
}
这是我使用的ToHashSet()实现。哈希码算法来自有效Java(通过Jon Skeet)。
回答
重复的帖子，但请查看我的解决方案以比较收藏集。很简单：
这将执行相等比较，而不考虑顺序：
var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;
这将检查是否已添加/删除项目：
var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added; //Sally
var inbothlists = diff.Equal; //Bob
这将查看字典中的哪些项目已更改：
var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa
原始帖子在这里。
回答
事实证明，Microsoft已经在其测试框架中对此进行了介绍：CollectionAssert.AreEquivalent
Remarks Two collections are equivalent if they have the same elements in the same quantity, but in any order. Elements are equal if their values are equal, not if they refer to the same object.
使用反射器，我修改了AreEquivalent()背后的代码以创建相应的相等比较器。它比现有的答案更完整，因为它考虑了空值，实现了IEqualityComparer并具有一些效率和边缘情况检查。另外，它是Microsoft :)
public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
private readonly IEqualityComparer<T> m_comparer;
public MultiSetComparer(IEqualityComparer<T> comparer = null)
{
m_comparer = comparer ?? EqualityComparer<T>.Default;
}
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == null)
return second == null;
if (second == null)
return false;
if (ReferenceEquals(first, second))
return true;
if (first is ICollection<T> firstCollection && second is ICollection<T> secondCollection)
{
if (firstCollection.Count != secondCollection.Count)
return false;
if (firstCollection.Count == 0)
return true;
}
return !HaveMismatchedElement(first, second);
}
private bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
{
int firstNullCount;
int secondNullCount;
var firstElementCounts = GetElementCounts(first, out firstNullCount);
var secondElementCounts = GetElementCounts(second, out secondNullCount);
if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count)
return true;
foreach (var kvp in firstElementCounts)
{
var firstElementCount = kvp.Value;
int secondElementCount;
secondElementCounts.TryGetValue(kvp.Key, out secondElementCount);
if (firstElementCount != secondElementCount)
return true;
}
return false;
}
private Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount)
{
var dictionary = new Dictionary<T, int>(m_comparer);
nullCount = 0;
foreach (T element in enumerable)
{
if (element == null)
{
nullCount++;
}
else
{
int num;
dictionary.TryGetValue(element, out num);
num++;
dictionary[element] = num;
}
}
return dictionary;
}
public int GetHashCode(IEnumerable<T> enumerable)
{
if (enumerable == null) throw new ArgumentNullException(nameof(enumerable));
int hash = 17;
foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + (val?.GetHashCode() ?? 42);
return hash;
}
}
用法示例：
var set = new HashSet<IEnumerable<int>>(new[] {new[]{1,2,3}}, new MultiSetComparer<int>());
Console.WriteLine(set.Contains(new [] {3,2,1})); //true
Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false
或者，如果我们只想直接比较两个集合：
var comp = new MultiSetComparer<string>();
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","c","b"})); //true
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","b"})); //false
最后，我们可以使用自己选择的相等比较器：
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
