比较两个List <>的最快方法

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();

但这并不像我想的那样好.因为我需要处理很多列表,所以想要更快,更少资源吗？

Answer 1

用途Except:

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

我怀疑有这实际上是略高于这个速度的方法,但即使这样会大大超过你的O(N*M)的方法要快.

如果要组合这些,可以使用上面的方法创建一个方法,然后使用return语句:

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

Answer 2

效率更高的将是Enumerable.Except:

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

此方法通过使用延迟执行来实现.这意味着你可以写例如:

var first10 = inListButNotInList2.Take(10);

它也很有效,因为它在内部使用a Set<T>来比较对象.它的工作原理是首先收集第二个序列中的所有不同值,然后流式传输第一个序列的结果,检查它们之前是否曾见过.

Answer 3

Enumerable.SequenceEqual方法

根据相等比较器确定两个序列是否相等。 微软文档

Enumerable.SequenceEqual(list1, list2);

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

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

IEqualityComparer接口

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

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

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 的以下结果：

方法	意思是	错误	标准差	比率	第0代	第一代	第2代	已分配
差异链接	115.19 毫秒	0.656 毫秒	0.582 毫秒	1.00	2800.0000	2800.0000	2800.0000	67110744乙
差异压缩	23.48 毫秒	0.018毫秒	0.015毫秒	0.20	-	-	-	720乙

对于 N = 100M：

方法	意思是	错误	标准差	比率	第0代	第一代	第2代	已分配
差异链接	12.146秒	0.0427秒	0.0379秒	1.00	13000.0000	13000.0000	13000.0000	8589937032乙
差异压缩	2.324秒	0.0019秒	0.0018秒	0.19	-	-	-	720乙

请注意，这个示例当然受益于列表已经排序并且可以非常有效地比较整数这一事实。但这正是重点：如果你确实有有利的环境，请确保你利用它们。

一些进一步的评论：比较函数的速度显然与整体性能相关，因此优化它可能是有益的。这样做的灵活性是压缩方法的一个好处。此外，并行化对我来说似乎更可行，尽管绝不容易，而且可能不值得付出努力和开销。尽管如此，一种将处理速度加快大约 2 倍的简单方法是将列表分别分成两半（如果可以有效地完成）并并行比较这些部分，一个从前到后处理，另一个从前到后处理。以相反的顺序。

Answer 6

不是为了这个问题,但是这里有一些代码来比较列表是否相等而不是!相同的对象:

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);
}

Answer 7

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它们产生相同的值。我们可以通过将哈希码委托给列表中的每个元素，并使用标准的按位异或将它们全部组合起来来实现这一点。XOR 与顺序无关，因此列表的排序方式是否不同并不重要。重要的是它们只包含同等的成员。

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