比较两个通用列表差异的最快方法

Question

什么是比较两个超大型列表（> 50,000个项）最快（且资源消耗最少）的方法，并因此得到类似于下面这样的两个列表：

1. 显示在第一个列表中但不显示在第二个列表中的项目
2. 显示在第二个列表中但不显示在第一个列表中的项目

目前我正在使用List或IReadOnlyCollection并在linq查询中解决此问题：

var list1 = list.Where(i => !list2.Contains(i)).ToList();
var list2 = list2.Where(i => !list.Contains(i)).ToList();

但这个程序的性能不如我所期望的好。 有什么办法可以让它更快速、资源占用更少，因为我需要处理很多列表？

- Frank

---

如果你遇到了这个问题并且考虑添加一个新答案，请注意他们不是在寻求一种方法，而是最快速的方法。 - Gert Arnold

Answer 1

使用 Except 函数：

var firstNotSecond = list1.Except(list2).ToList();
var secondNotFirst = list2.Except(list1).ToList();

我怀疑还有一些方法比这个稍微快一点，但即使是这个方法，速度也会比你的O(N * M)方法快得多。

如果你想将它们组合起来，你可以创建一个以上述方法为基础的方法，并加上一个返回语句：

return !firstNotSecond.Any() && !secondNotFirst.Any();

需要注意的一点是，在问题中的原始代码和这里的解决方案之间存在结果差异：只在一个列表中出现的重复元素将只报告一次，而在原始代码中它们将根据出现次数报告多次。

例如，对于列表[1，2，2，2，3]和[1]，原始代码中“列表1中但不在列表2中的元素”结果将是[2, 2, 2, 3]。 针对我的代码，它只会是[2, 3]。 在许多情况下，这不会成为问题，但值得注意。

- Jon Skeet

---

这真的是一个巨大的性能提升！感谢您的回答。 - Frank

我在想对于两个巨大的列表，在比较之前排序是否有用？或者在Except扩展方法内，传入的列表已经排序了。 - Larry

@Larry: 它没有进行排序；它构建了一个哈希集合。 - Jon Skeet

任何具有适当的相等性的内容都可以使用 - 因此，如果您自定义的类型重写了 Equals(object) 并/或实现了 IEquatable<T>，那么它应该是可以的。 - Jon Skeet

@k2ibegin：它使用默认的相等比较器，该比较器将使用IEquatable<T>实现或object.Equals(object)方法。听起来你应该创建一个带有[mcve]的新问题 - 我们无法在评论中诊断问题。 - Jon Skeet

Answer 2

Enumerable.SequenceEqual 方法

根据相等比较器，确定两个序列是否相等。 MS.Docs

Enumerable.SequenceEqual(list1, list2);

对于所有原始数据类型都适用。如果您需要在自定义对象上使用它，则需要实现IEqualityComparer

定义支持比较对象是否相等的方法。

IEqualityComparer接口

定义支持比较对象是否相等的方法。 MS.Docs for IEqualityComparer

- miguelmpn

---

这应该是被接受的答案。问题不是关于集合，而是关于列表，它可以包含重复的元素。 - Adrian Nasui

考虑到SequenceEqual的结果是一个简单的布尔值，我不认为它能成为答案。原帖中要求得到两个列表的结果，并用集合运算来描述需要的结果：“第一个列表中出现但第二个列表中没有的项”。没有表明顺序很重要，而SequenceEqual会考虑顺序，这似乎回答了完全不同的问题。 - Jon Skeet

是的，正确的，看起来我回答这个问题太快了，没有看到请求的第二部分...和前两条评论一样... - miguelmpn

这是一个可爱的答案（在我看来是最好的答案），而且非常有效。谢谢！ - A. Dzebo

这不是原问题的答案，但常常发生的是，谷歌会带来很多人来到这里寻找有序敏感检查。谢谢！ - Yirkha

还要注意，比较的序列必须按相同的顺序排列。如果序列中的元素不按相同的顺序排列，则即使它们包含完全相同的元素，SequenceEqual也会返回true。 - Oliver Konig

Answer 3

更高效的方法是使用Enumerable.Except：

var inListButNotInList2 = list.Except(list2);
var inList2ButNotInList = list2.Except(list);

此方法是通过使用延迟执行实现的。这意味着你可以编写如下代码：

var first10 = inListButNotInList2.Take(10);

由于内部使用了Set<T>来比较对象，因此它也很高效。 它首先从第二个序列中收集所有不同的值，然后流式处理第一个序列的结果，检查它们之前是否已经出现过。

- Tim Schmelter

---

嗯，不完全是延迟的。我会说它是部分延迟的。完整的 Set<T> 是从第二个序列构建的（即完全迭代并存储），然后可以从第一个序列添加的项被产生。 - spender

@spender，这就像说Where的执行是部分延迟的，因为在list.Where(x => x.Id == 5)中数字5的值是在开始时存储的，而不是惰性地执行。 - jwg

Answer 4

如果您希望结果不区分大小写，可以使用以下方法：

List<string> list1 = new List<string> { "a.dll", "b1.dll" };
List<string> list2 = new List<string> { "A.dll", "b2.dll" };

var firstNotSecond = list1.Except(list2, StringComparer.OrdinalIgnoreCase).ToList();
var secondNotFirst = list2.Except(list1, StringComparer.OrdinalIgnoreCase).ToList();

firstNotSecond将包含b1.dll

secondNotFirst将包含b2.dll

- e.gad

Answer 5

虽然Jon Skeet的回答对于小到中等数量元素（最多几百万个）的日常实践是一条很好的建议，但它并不是最快的方法也不是非常节约资源的方法。显而易见的缺点是获取完整差异需要两次遍历数据（如果还需要得到相等的元素则需三次遍历）。显然，可以通过自定义重新实现Except方法来避免这个问题，但是创建哈希集合需要大量内存，并且计算哈希需要时间。

对于非常大的数据集（十亿级别的元素），通常要考虑特定情况。以下是一些可能提供灵感的想法： 如果可以比较元素（在实践中几乎总是这种情况），则排序列表并应用以下zip方法值得考虑：

/// <returns>The elements of the specified (ascendingly) sorted enumerations that are
/// contained only in one of them, together with an indicator,
/// whether the element is contained in the reference enumeration (-1)
/// or in the difference enumeration (+1).</returns>
public static IEnumerable<Tuple<T, int>> FindDifferences<T>(IEnumerable<T> sortedReferenceObjects,
    IEnumerable<T> sortedDifferenceObjects, IComparer<T> comparer)
{
    var refs  = sortedReferenceObjects.GetEnumerator();
    var diffs = sortedDifferenceObjects.GetEnumerator();
    bool hasNext = refs.MoveNext() && diffs.MoveNext();
    while (hasNext)
    {
        int comparison = comparer.Compare(refs.Current, diffs.Current);
        if (comparison == 0)
        {
            // insert code that emits the current element if equal elements should be kept
            hasNext = refs.MoveNext() && diffs.MoveNext();

        }
        else if (comparison < 0)
        {
            yield return Tuple.Create(refs.Current, -1);
            hasNext = refs.MoveNext();
        }
        else
        {
            yield return Tuple.Create(diffs.Current, 1);
            hasNext = diffs.MoveNext();
        }
    }
}

这可以例如以下方式使用：

const int N = <Large number>;
const int omit1 = 231567;
const int omit2 = 589932;
IEnumerable<int> numberSequence1 = Enumerable.Range(0, N).Select(i => i < omit1 ? i : i + 1);
IEnumerable<int> numberSequence2 = Enumerable.Range(0, N).Select(i => i < omit2 ? i : i + 1);
var numberDiffs = FindDifferences(numberSequence1, numberSequence2, Comparer<int>.Default);

在我的电脑上对 N = 1M 进行基准测试，得到以下结果：

方法	平均值	误差	标准偏差	比率	Gen 0	Gen 1	Gen 2	分配的内存
DiffLinq	115.19 毫秒	0.656 毫秒	0.582 毫秒	1.00	2800.0000	2800.0000	2800.0000	67110744 B
DiffZip	23.48 毫秒	0.018 毫秒	0.015 毫秒	0.20	-	-	-	720 B

而对于 N = 100M：

方法	用时	误差	标准差	比率	Gen 0	Gen 1	Gen 2	已分配内存
DiffLinq	12.146 秒	0.0427 秒	0.0379 秒	1.00	13000.0000	13000.0000	13000.0000	8589937032 字节
DiffZip	2.324 秒	0.0019 秒	0.0018 秒	0.19	-	-	-	720 字节

注意，此示例当然受益于列表已排序并且整数可以非常高效地比较。但这正是关键：如果您有有利的条件，请确保利用它们。

进一步的说明：比较函数的速度显然对整体性能很重要，因此优化它可能会很有益。压缩方法的灵活性就是其中的一个好处。此外，对我来说，并行化似乎更可行，虽然绝不容易，可能并不值得投入工作和开销。尽管如此，加速过程的简单方法是将两个列表分别拆成两半（如果可以高效地完成），并以并行方式进行比较，一个从前往后处理，另一个从后往前处理，总速度大约提高2倍。

- KloppyToppy

Answer 6

using System.Collections.Generic;
using System.Linq;

namespace YourProject.Extensions
{
    public static class ListExtensions
    {
        public static bool SetwiseEquivalentTo<T>(this List<T> list, List<T> other)
            where T: IEquatable<T>
        {
            if (list.Except(other).Any())
                return false;
            if (other.Except(list).Any())
                return false;
            return true;
        }
    }
}

有时您只需要知道两个列表是否不同，而不是它们的差异。在这种情况下，考虑将此扩展方法添加到您的项目中。请注意，列出的对象应实现IEquatable！

用法：

public sealed class Car : IEquatable<Car>
{
    public Price Price { get; }
    public List<Component> Components { get; }

    ...
    public override bool Equals(object obj)
        => obj is Car other && Equals(other);

    public bool Equals(Car other)
        => Price == other.Price
            && Components.SetwiseEquivalentTo(other.Components);

    public override int GetHashCode()
        => Components.Aggregate(
            Price.GetHashCode(),
            (code, next) => code ^ next.GetHashCode()); // Bitwise XOR
}

无论 Component 类是什么，这里展示的 Car 方法都应该以几乎相同的方式实现。

非常重要的一点是要注意我们如何编写 GetHashCode。为了正确实现 IEquatable，Equals 和 GetHashCode 必须以逻辑兼容的方式操作实例的属性。两个具有相同内容的列表仍然是不同的对象，并且将产生不同的哈希码。由于我们希望将这两个列表视为相等，因此必须让 GetHashCode 为它们的每个列表产生相同的值。我们可以通过将哈希码委托给列表中的每个元素，并使用标准位异或运算符将它们组合起来来实现这一点。异或是无序的，因此无论列表是否排序不同，它都不重要。唯一需要的是它们只包含等效成员。

注：这个奇怪的名字是为了暗示方法不考虑列表中元素的顺序。如果您关心列表中元素的顺序，那么这个方法并不适合您！

- Devon Parsons

Answer 7

虽然这不是这个问题的解决方案，但以下代码可以比较列表中相等但不完全相同的对象：

public class EquatableList<T> : List<T>, IEquatable<EquatableList<T>> where    T : IEquatable<T>

/// <summary>
/// True, if this contains element with equal property-values
/// </summary>
/// <param name="element">element of Type T</param>
/// <returns>True, if this contains element</returns>
public new Boolean Contains(T element)
{
    return this.Any(t => t.Equals(element));
}

/// <summary>
/// True, if list is equal to this
/// </summary>
/// <param name="list">list</param>
/// <returns>True, if instance equals list</returns>
public Boolean Equals(EquatableList<T> list)
{
    if (list == null) return false;
    return this.All(list.Contains) && list.All(this.Contains);
}

- Pius Hermit

---

这是您需要能够比较自定义数据类型的内容。然后使用 Except。 - Pranav Singh

你可以使用可排序类型来提高效率。这个程序的时间复杂度是O(n^2)，而你可以做到O(nlogn)。 - yuvalm2

Answer 8

试试这种方式：

var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
            .Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));

- Alex

---

这段代码表现非常糟糕，需要对第二个列表中的每个项进行扫描以匹配第一个列表中的每个项。虽然它能够工作，但与原始代码一样糟糕，因此不会点踩。 - spender

我认为OP是在解决对象未实现IEquitable的问题。 - DanielV

Answer 9

如果只需要联合结果，这个也可以工作：

var set1 = new HashSet<T>(list1);
var set2 = new HashSet<T>(list2);
var areEqual = set1.SetEquals(set2);

T代表列表元素的类型。

- Ali Khaleghi Karsalari

Answer 10

我使用了这个代码来比较两个拥有数百万条记录的列表。

这种方法不需要太多时间。

    //Method to compare two list of string
    private List<string> Contains(List<string> list1, List<string> list2)
    {
        List<string> result = new List<string>();

        result.AddRange(list1.Except(list2, StringComparer.OrdinalIgnoreCase));
        result.AddRange(list2.Except(list1, StringComparer.OrdinalIgnoreCase));

        return result;
    }

- Sathish