首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >比较两个集合是否相等,而不考虑其中项的顺序

比较两个集合是否相等,而不考虑其中项的顺序
EN

Stack Overflow用户
提问于 2008-09-08 16:36:16
回答 20查看 108.4K关注 0票数 177

我想比较两个集合(在C#中),但我不确定有效地实现这一点的最佳方法。

我读过另一个关于Enumerable.SequenceEqual的帖子,但这并不是我想要的。

在我的例子中,如果两个集合都包含相同的项(无论顺序如何),则它们是相等的。

示例:

代码语言:javascript
复制
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1 == collection2; // true

我通常做的是遍历一个集合中的每个项,看看它是否存在于另一个集合中,然后遍历另一个集合中的每个项,看看它是否存在于第一个集合中。(我从比较长度开始)。

代码语言:javascript
复制
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

然而,这并不完全正确,而且这可能不是比较两个集合是否相等的最有效方法。

我能想到的一个错误的例子是:

代码语言:javascript
复制
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}

这将与我的实现相同。我是否应该只计算找到每一项的次数,并确保两个集合中的计数相等?

示例是用某种C#编写的(让我们称之为伪C#),但是用您想要的任何语言给出答案,这都无关紧要。

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

EN

回答 20

Stack Overflow用户

回答已采纳

发布于 2010-09-25 04:10:30

事实证明,微软的测试框架已经涵盖了这一点:CollectionAssert.AreEquivalent

备注

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

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

代码语言:javascript
复制
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;
    }
}

示例用法:

代码语言:javascript
复制
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

或者,如果您只想直接比较两个集合:

代码语言:javascript
复制
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

最后,您可以使用您选择的等式比较器:

代码语言:javascript
复制
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
票数 122
EN

Stack Overflow用户

发布于 2008-09-08 17:07:36

一种简单而高效的解决方案是对两个集合进行排序,然后比较它们是否相等:

代码语言:javascript
复制
bool equal = collection1.OrderBy(i => i).SequenceEqual(
                 collection2.OrderBy(i => i));

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

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

票数 105
EN

Stack Overflow用户

发布于 2008-09-08 17:00:56

创建一个字典"dict“,然后对第一个集合中的每个成员执行dictmember++;

然后,以同样的方式遍历第二个集合,但对于每个成员都要指定成员--。

最后,循环遍历字典中的所有成员:

代码语言:javascript
复制
    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),假设字典使用O(1)个查找。

票数 32
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50098

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档