LINQ中的集合相等性

Question

我有两个列表 A 和 B（List），如何以最便宜的方式确定它们是否相等？我可以写类似于“(A 减去 B)并集(B 减去 A)=空集”的代码，或者将它们合并在一起并计算元素数量，但这些都比较耗费资源。是否有更好的解决方法？

- Alsin

Answer 1

如果列表项的顺序很重要：

bool areEqual = a.SequenceEqual(b);

如果列表要被视为无序集合：

// assumes that the list items are ints
bool areEqual = new HashSet<int>(a).SetEquals(b);

(如果您需要该功能，SequenceEqual方法和HashSet<T>构造函数都有接受IEqualityComparer<T>参数的重载。)

- LukeH

Answer 2

这取决于你如何解释你的列表。

如果你将它们视为元组（因此列表中元素的顺序很重要），那么你可以使用以下代码：

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        if (A.Count != B.Count)
            return false;
        for (int i = 0; i < A.Count; i++)
            if (!A[i].Equals(B[i])) 
                return false;
    }

如果您将列表视为集合（因此元素的顺序不重要），那么...我猜您正在使用错误的数据结构：

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        HashSet<T> setA = new HashSet<T>(A);
        return setA.SetEquals(B);
    }

- Massimiliano

---

如果你要切换到HashSets，请确保你的集合对象上的GetHashCode()函数正常工作。 - Massimiliano

第二种解决方案实际上并没有检查列表是否相等，例如它声明{1,3}等于{1,1,3,3,3}，因为它不关心任何给定项的数量。也许将名称更改为“HasSameUniqueElements”？ - Ian Mercer

从数学上讲，那不应该是“向量”而不是“元组”吗？因为在元组中，元素可以具有不同的类型，但在向量中，所有元素必须是相同的类型 - 而List<T>是一个向量，而不是元组。 - Dai

Answer 3

这里真的没有捷径，除非列表已经排序，否则您只能逐个比较元素。显然，我假设顺序不重要，否则您也可以逐个比较它们。

否则，我建议对于大量项目的最有效算法可能是使用哈希表来跟踪您所见过的内容（警告：未经测试，但应该清楚我的意思）。

public static bool IsEqual<T>(this List<T> x1, List<T> x2)
{
    if(x1.Count != x2.Count) return false;

    var x1Elements = new Dictionary<T, int>();

    foreach(var item in x1)
    {
        int n; x1Elements.TryGetValue(item, out n);
        x1Elements[item] = n+1;
    }

    foreach(var item in x2)
    {
        int n; x1Elements.TryGetValue(item, out n);
        if(n <= 0) return false; // this element was in x2 but not x1
        else x1Elements[item] = n-1;
    }

    // make sure x1 didn't have any elements
    // that weren't in x2

    return x1Elements.Values.All(x => x == 0);
}

- mqp

---

是的，我目前正在使用类似这样的东西。 - Alsin

最后一行可能只需要写成 return true，因为你已经检查了它们在开头是否有相同的数字。你放进去一个n，又拿出来一个n，所以你必须是零。 - Ian Mercer

Answer 4

这取决于你所说的“列表相等”的含义。如果你的意思是它们包含相同的对象，那么Daniel建议的解决方案就可以了，只需将两个列表Union()起来并计算项目数。

如果你所说的“相等”是指它们具有相同的项目按相同的顺序，那么最好比较两个列表的计数，然后如果它们具有相同的计数，只需使用普通的for循环迭代以比较两个列表中在相同索引处的每个元素。不太美观，但你几乎无法更快。

- Yann Schwartz

---

我的意思是集合的相等，它们是否包含相同的元素。Union() 仍然过于复杂。 - Alsin

Answer 5

第一次尝试 - 如果它们包含相同的项目，则两个列表的并集应该具有与任何一个列表相同数量的项目。

listA.Union(listB).Count() == listA.Count()

注意：如果一个列表为空，将会失败。

但它可能仍然是一个O(n²)操作。

另一个解决方案 - 列表必须具有相同的长度，并且列表A减去列表B不能包含任何元素。

(listA.Count() == listB.Count()) && !listA.Except(listB).Any()

- Daniel Brückner

---

让它成为交集——您的版本允许在listA中比listB中有更多的项目。 - Ryan Versaw

如果ListB为空，则此代码错误地返回true。 - Robert