比较两个集合的相等性，不考虑其中项目的顺序，涉及到IT技术。

Question

比较两个集合的相等性，不考虑其中项目的顺序，涉及到IT技术。

.netcollectionscomparisonequality

185

我想比较两个集合（在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# 伪代码，但是你可以使用任何语言回答，都没有关系。

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

- Mono

1

算法怎么样？所有的答案都涉及比较某些东西，如通用列表比较LINQ等。我们真的向某人承诺过永远不会像老式程序员一样使用算法吗？ - Nuri YILMAZ

你不是在检查相等性，而是在检查等价性。这可能有点挑剔，但这是一个重要的区别。而且这是很久以前的事了。这是一个好的问答。 - CAD bloke

您可能会对这篇文章感兴趣，它讨论了下面描述的基于字典的方法的优化版本。大多数简单的字典方法存在一个问题，即它们不能正确处理null值，因为.NET的Dictionary类不允许使用null键。 - ChaseMedallion

21个回答

109

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

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

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

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

- Igor Ostrovsky

1

你只需要先添加 using System.Linq; 就可以让它工作了。 - Junior Mayhé

如果此代码位于循环内部，并且 collection1 被更新而 collection2 保持不变，请注意即使两个集合具有相同的对象，调试器也会显示 "equal" 变量为 false。 - Junior Mayhé

6

@Chaulky - 我认为需要使用 OrderBy。请参考：https://dotnetfiddle.net/jA8iwE - Brett

1

另一个被称为“上面”的答案可能是 https://dev59.com/jHVD5IYBdhLWcg3wNY1Z#50465 吗？ - StayOnTarget

请注意仔细选择比较方式。如果两个元素相似但是不同对象，则可能根本无法重新排序。 - Reyhn

34

创建一个名为“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)。

- Daniel Jennings

这几乎是我想要的。但是，即使我不使用整数，我也希望能够做到这一点。我想使用引用对象，但它们在字典中作为键时无法正常工作。 - mbillard

Mono，如果您的项目不可比较，则您的问题是无意义的。如果它们不能用作字典中的键，则没有可用的解决方案。 - skolima

1

我认为Mono的意思是键不可排序。但是Daniel的解决方案明显是要使用哈希表而不是树来实现的，只要有等价测试和哈希函数就可以工作。 - erickson

当然感谢您的帮助并点赞，但由于缺少一个重要的点（我在我的答案中涵盖了），所以不予接受。 - mbillard

1

顺便说一句，你可以使用以下代码简化你的最后一个foreach循环和return语句：return dict.All(kvp => kvp.Value == 0); - Tyson Williams

如果集合包含空元素，则字典会抛出异常，因为字典键不能为null。 - Skarllot

17

这是我（受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;
    }
}

- Mono

12

做得很好，但请注意：1. 与Daniel Jennings的解决方案相比，这不是O(N)，而是O(N^2)，因为foreach循环中的find函数在bar集合中进行了查找；2. 您可以将该方法泛型化以接受IEnumerable<T>而无需对代码进行进一步修改。 - Ohad Schneider

“字典的键是通过引用进行比较的，因此我们必须找到与'item'等效的原始键” - 这并不是真的。该算法基于错误假设，虽然有效，但效率极低。 - Antonín Lejsek

13

你可以使用一个哈希集合。查看SetEquals方法。

- Joel Gauvreau

3

当然，使用 HashSet 假定没有重复项，但如果有的话，HashSet 是最好的选择。 - Mark Cidade

由于ToHashSet()现在已经内置在Linq中，SetEquals()的解决方案可以写成非常简洁高效的一行代码：collection1.ToHashSet().SetEquals(collection2)。虽然这种方法不支持重复元素，但它无疑是最简短的答案，不需要使用外部库，并且在摊还的O(n)时间内运行。 - undefined

8

如果您使用Shouldly，则可以使用Contains的ShouldAllBe。

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

- Pier-Lionel Sgard

1

我刚在最新版本上发现ShouldBe方法有一个参数bool ignoreOrder。 - Pier-Lionel Sgard

Shouldly 是一个非常棒的参考库。 - Lesair Valmont

8

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名称空间。根据微软公司的说法，SymmetricExceptWith是一项O(n+m)的操作，其中n代表第一个集合中元素的数量，m代表第二个集合中元素的数量。如果需要的话，您可以向该函数添加相等比较器。

- palswim

有趣且罕见的事实。感谢您的知识。 - Emmanuel DURIN

最佳答案在这里，简洁、正确且快速。应该被点赞。 - Mick Byrne

7

编辑：我刚发布时就意识到，这只适用于集合——它无法正确处理具有重复项的集合。例如，{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

- Schmidty

这段代码唯一的问题是它只适用于比较值类型或比较引用类型的指针。我可能会在集合中有两个不同的相同对象实例，因此我需要能够指定如何比较每个对象。你能把一个比较委托传递给交集方法吗？ - mbillard

当然，您可以传递一个比较器委托。但是，请注意我添加的关于集合的限制，这会对其适用性产生重大影响。 - Schmidty

Intersect方法返回一个不同的集合。假设a = {1,1,2}和b ={2,2,1}，a.Intersect(b).Count() != a.Count，这会导致您的表达式正确地返回false。{1,2}.Count != {1,1,2}.Count 请参见链接（注意，在比较之前两侧都被区分开）。 - Griffin

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的方式）（参考链接）。

- Ohad Schneider

Serializable 对于 Comparer 类有什么意义呢？另外，您可以将输入更改为 ISet<T>，以表明它适用于集合（即无重复项）。 - nawfal

@nawfal 谢谢，当我标记它为Serializable时，我不知道自己在想什么...至于ISet，这里的想法是将IEnumerable视为一个集合（因为你一开始就得到了一个IEnumerable），尽管考虑到在5年内没有获得任何赞成票，这可能不是最明智的想法 :P - Ohad Schneider

4

Why not use .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

- Korayem

2

"Except" 无法用于计算重复项。它将对集合 {1,2,2} 和 {1,1,2} 返回 true。 - Cristian Diaconescu

@CristiDiaconescu，你可以先使用“.Distinct()”来删除任何重复项。 - Korayem

OP正在询问[1, 1, 2] != [1, 2, 2]。使用Distinct会使它们看起来相等。 - Cristian Diaconescu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ohad Schneider · Accepted Answer

原来在其测试框架中，微软已经涵盖了这一点：CollectionAssert.AreEquivalent 备注：如果两个集合中拥有相同数量的元素，但顺序不同，则它们是等效的。元素相等指它们的值相等，而非引用相同的对象。

使用反射，我修改了AreEquivalent()后面的代码，以创建一个对应的相等比较器。它比现有答案更完整，因为它考虑到了null值，实现了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