177

我想比较两个集合（在 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#），但可以用任何您希望的语言给出答案，没关系。

注意：为了简单起见，我在示例中使用了整数，但我也希望能够使用引用类型的对象（它们不能正确地作为键，因为只比较对象的引用，而不是内容）。

4

20 回答 20

122

事实证明，微软已经在其测试框架中包含了这一点：CollectionAssert.AreEquivalent

评论

如果两个集合具有相同数量的相同元素，但顺序不限，则它们是等价的。如果它们的值相等，则元素相等，而不是如果它们引用同一个对象。

使用反射器，我修改了 AreEquivalent() 背后的代码以创建相应的相等比较器。它比现有答案更完整，因为它考虑了空值，实现了 IEqualityComparer 并具有一些效率和边缘情况检查。另外，它是微软:)

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)
            hash ^= (val == null ? 42 : m_comparer.GetHashCode(val));

        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
于 2010-09-24T20:10:30.170 回答
105

一个简单且相当有效的解决方案是对两个集合进行排序，然后比较它们是否相等：

bool equal = collection1.OrderBy(i => i).SequenceEqual(
                 collection2.OrderBy(i => i));

这个算法是 O(N*logN)，而你上面的解决方案是 O(N^2)。

如果集合具有某些属性，您可能能够实现更快的解决方案。例如，如果您的两个集合都是哈希集，则它们不能包含重复项。此外，检查散列集是否包含某些元素非常快。在这种情况下，类似于您的算法可能会是最快的。

于 2008-09-08T17:07:36.263 回答
32

创建一个字典“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(N)，假设 Dictionary 使用 O(1) 查找。

于 2008-09-08T17:00:55.627 回答
18

这是我（受 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;
    }
}
于 2008-09-08T19:18:55.857 回答
11

您可以使用Hashset。查看SetEquals方法。

于 2008-10-04T04:38:31.400 回答
7 
static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
    var setXOR = new HashSet<T>(set1);
    setXOR.SymmetricExceptWith(set2);
    return (setXOR.Count == 0);
}

解决方案需要 .NET 3.5 和System.Collections.Generic命名空间。根据 Microsoft的说法，SymmetricExceptWith是一个O(n + m)操作，其中n表示第一个集合中的元素数，m表示第二个集合中的元素数。如有必要，您始终可以向此函数添加相等比较器。

于 2016-06-24T00:18:20.427 回答
7

如果您使用Shouldly，则可以将 ShouldAllBe 与 Contains 一起使用。 

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1.ShouldAllBe(item=>collection2.Contains(item)); // true

最后，您可以编写扩展程序。 

public static class ShouldlyIEnumerableExtensions
{
    public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
    {
        list.ShouldAllBe(l => equivalent.Contains(l));
    }
}

更新

ShouldBe方法上有一个可选参数。

collection1.ShouldBe(collection2, ignoreOrder: true); // true
于 2017-11-14T15:09:18.637 回答
5

编辑：我一提出就意识到这真的只适用于集合——它不能正确处理具有重复项目的集合。例如 { 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
于 2009-06-18T23:20:02.803 回答
5

在没有重复和没有顺序的情况下，可以使用以下 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() 实现。哈希码算法来自 Effective Java（通过 Jon Skeet）。

于 2010-04-01T23:51:23.167 回答
4

为什么不使用 .Except()

// Create the IEnumerable data sources.
string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");
// Create the query. Note that method syntax must be used here.
IEnumerable<string> differenceQuery =   names1.Except(names2);
// Execute the query.
Console.WriteLine("The following lines are in names1.txt but not names2.txt");
foreach (string s in differenceQuery)
     Console.WriteLine(s);

http://msdn.microsoft.com/en-us/library/bb397894.aspx

于 2011-08-08T16:06:15.003 回答
2

各种各样的重复帖子，但请查看我的解决方案来比较集合。这很简单：

无论顺序如何，这将执行相等比较：

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

原帖在这里。

于 2010-04-29T20:35:22.600 回答
1

这是我的 ohadsc 答案的扩展方法变体，以防它对某人有用

static public class EnumerableExtensions 
{
    static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second)
    {
        if ((first == null) != (second == null))
            return false;

        if (!object.ReferenceEquals(first, second) && (first != null))
        {
            if (first.Count() != second.Count())
                return false;

            if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second))
                return false;
        }

        return true;
    }

    private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second)
    {
        int firstCount;
        int secondCount;

        var firstElementCounts = GetElementCounts<T>(first, out firstCount);
        var secondElementCounts = GetElementCounts<T>(second, out secondCount);

        if (firstCount != secondCount)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            firstCount = kvp.Value;
            secondElementCounts.TryGetValue(kvp.Key, out secondCount);

            if (firstCount != secondCount)
                return true;
        }

        return false;
    }

    private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount)
    {
        var dictionary = new Dictionary<T, int>();
        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;
    }

    static private int GetHashCode<T>(IEnumerable<T> enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + val.GetHashCode();

        return hash;
    }
}
于 2012-03-11T21:01:59.863 回答
1

这是一个比这个改进的解决方案。

public static bool HasSameElementsAs<T>(
        this IEnumerable<T> first, 
        IEnumerable<T> second, 
        IEqualityComparer<T> comparer = null)
    {
        var firstMap = first
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        var secondMap = second
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        if (firstMap.Keys.Count != secondMap.Keys.Count)
            return false;

        if (firstMap.Keys.Any(k1 => !secondMap.ContainsKey(k1)))
            return false;

        return firstMap.Keys.All(x => firstMap[x] == secondMap[x]);
    }
于 2017-05-29T18:27:18.110 回答
0

埃里克森几乎是对的：既然你想匹配重复的数量，你需要一个Bag。在 Java 中，这看起来像：

(new HashBag(collection1)).equals(new HashBag(collection2))

我确信 C# 有一个内置的 Set 实现。我会先使用它；如果性能有问题，您总是可以使用不同的 Set 实现，但使用相同的 Set 接口。

于 2008-09-08T17:05:45.740 回答
0

这个问题有很多解决方案。如果您不关心重复项，则不必对两者进行排序。首先确保它们具有相同数量的项目。在排序之后的集合之一。然后对排序集合中的第二个集合中的每个项目进行 binsearch。如果您没有找到给定的项目，请停止并返回 false。其复杂性： - 对第一个集合进行排序：N Log(N) - 从第二个到第一个搜索每个项目：NLOG(N) 所以你最终得到 2*N*LOG(N) 假设它们匹配并且你查找所有内容。这类似于对两者进行排序的复杂性。如果有差异，这也可以让您提前停止。但是，请记住，如果在您进入此比较之前对两者都进行了排序，并且您尝试使用 qsort 之类的东西进行排序，那么排序将更加昂贵。对此进行了优化。另一种选择是使用位掩码索引，这对于您知道元素范围的小型集合非常有用。这将为您提供 O(n) 性能。另一种选择是使用散列并查找它。对于小型集合，进行排序或位掩码索引通常要好得多。Hashtable 的缺点是局部性较差，因此请记住这一点。再说一次，只有你不这样做 不关心重复。如果要考虑重复项，请对两者进行排序。

于 2008-10-11T20:20:47.660 回答
0

在许多情况下，唯一合适的答案是 Igor Ostrovsky 之一，其他答案基于对象哈希码。但是，当您为对象生成哈希码时，您只能基于他的 IMMUTABLE 字段 - 例如对象 Id 字段（在数据库实体的情况下） - 为什么在重写 Equals 方法时重写 GetHashCode 很重要？

这意味着，如果您比较两个集合，即使不同项目的字段不相等，compare 方法的结果也可能为真。要深入比较集合，您需要使用 Igor 的方法并实现 IEqualirity 。

请阅读我和施奈德先生对他投票最多的帖子的评论。

詹姆士

于 2013-08-30T23:30:19.573 回答
0

允许在IEnumerable<T>（如果集合不可取\可能）和“忽略顺序”中重复，您应该能够使用.GroupBy().

我不是复杂性测量方面的专家，但我的基本理解是这应该是 O(n)。我理解 O(n^2) 来自于在另一个 O(n) 操作中执行 O(n) 操作，例如ListA.Where(a => ListB.Contains(a)).ToList(). ListB 中的每个项目都与 ListA 中的每个项目进行相等性评估。

就像我说的，我对复杂性的理解是有限的，如果我错了，请纠正我。

public static bool IsSameAs<T, TKey>(this IEnumerable<T> source, IEnumerable<T> target, Expression<Func<T, TKey>> keySelectorExpression)
    {
        // check the object
        if (source == null && target == null) return true;
        if (source == null || target == null) return false;

        var sourceList = source.ToList();
        var targetList = target.ToList();

        // check the list count :: { 1,1,1 } != { 1,1,1,1 }
        if (sourceList.Count != targetList.Count) return false;

        var keySelector = keySelectorExpression.Compile();
        var groupedSourceList = sourceList.GroupBy(keySelector).ToList();
        var groupedTargetList = targetList.GroupBy(keySelector).ToList();

        // check that the number of grouptings match :: { 1,1,2,3,4 } != { 1,1,2,3,4,5 }
        var groupCountIsSame = groupedSourceList.Count == groupedTargetList.Count;
        if (!groupCountIsSame) return false;

        // check that the count of each group in source has the same count in target :: for values { 1,1,2,3,4 } & { 1,1,1,2,3,4 }
        // key:count
        // { 1:2, 2:1, 3:1, 4:1 } != { 1:3, 2:1, 3:1, 4:1 }
        var countsMissmatch = groupedSourceList.Any(sourceGroup =>
                                                        {
                                                            var targetGroup = groupedTargetList.Single(y => y.Key.Equals(sourceGroup.Key));
                                                            return sourceGroup.Count() != targetGroup.Count();
                                                        });
        return !countsMissmatch;
    }
于 2018-08-09T20:07:31.597 回答
0

这个简单的解决方案强制实现IEnumerable的泛型类型IComparable。因为 OrderBy' 的定义。

如果您不想做出这样的假设但仍想使用此解决方案，则可以使用以下代码：

bool equal = collection1.OrderBy(i => i?.GetHashCode())
   .SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
于 2018-12-19T19:20:04.697 回答
0

如果出于单元测试断言的目的进行比较，那么在进行比较之前将一些效率抛到窗外并简单地将每个列表转换为字符串表示形式 (csv) 可能是有意义的。这样，默认的测试断言消息将显示错误消息中的差异。

用法：

using Microsoft.VisualStudio.TestTools.UnitTesting;

// define collection1, collection2, ...

Assert.Equal(collection1.OrderBy(c=>c).ToCsv(), collection2.OrderBy(c=>c).ToCsv());

助手扩展方法：

public static string ToCsv<T>(
    this IEnumerable<T> values,
    Func<T, string> selector,
    string joinSeparator = ",")
{
    if (selector == null)
    {
        if (typeof(T) == typeof(Int16) ||
            typeof(T) == typeof(Int32) ||
            typeof(T) == typeof(Int64))
        {
            selector = (v) => Convert.ToInt64(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(decimal))
        {
            selector = (v) => Convert.ToDecimal(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(float) ||
                typeof(T) == typeof(double))
        {
            selector = (v) => Convert.ToDouble(v).ToString(CultureInfo.InvariantCulture);
        }
        else
        {
            selector = (v) => v.ToString();
        }
    }

    return String.Join(joinSeparator, values.Select(v => selector(v)));
}
于 2019-08-26T20:29:41.493 回答
0

基于这个重复问题的答案，以及答案下方的评论，以及@brian-genisio 的答案，我想出了这些：

        public static bool AreEquivalentIgnoringDuplicates<T>(this IEnumerable<T> items, IEnumerable<T> otherItems)
        {
            var itemList = items.ToList();
            var otherItemList = otherItems.ToList();
            var except = itemList.Except(otherItemList);
            return itemList.Count == otherItemList.Count && except.IsEmpty();
        }

        public static bool AreEquivalent<T>(this IEnumerable<T> items, IEnumerable<T> otherItems)
        {
            var itemList = items.ToList();
            var otherItemList = otherItems.ToList();
            var except = itemList.Except(otherItemList);
            return itemList.Distinct().Count() == otherItemList.Count && except.IsEmpty();
        }

测试这两个：

        [Test]
        public void collection_with_duplicates_are_equivalent()
        {
            var a = new[] {1, 5, 5};
            var b = new[] {1, 1, 5};

            a.AreEquivalentIgnoringDuplicates(b).ShouldBe(true); 
        }

        [Test]
        public void collection_with_duplicates_are_not_equivalent()
        {
            var a = new[] {1, 5, 5};
            var b = new[] {1, 1, 5};

            a.AreEquivalent(b).ShouldBe(false); 
        }
于 2021-05-11T11:49:51.063 回答