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

Question

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

322

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

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

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

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

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

- Frank

1

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

18个回答

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

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

- Kim Homann · Answer 1

Jon Skeet和miguelmpn的回答都很好。它取决于列表元素的顺序是否重要：

// take order into account
bool areEqual1 = Enumerable.SequenceEqual(list1, list2);

// ignore order
bool areEqual2 = !list1.Except(list2).Any() && !list2.Except(list1).Any();

- Ahmad · Answer 2

我比较了三种不同的方法来比较不同的数据集。下面的测试创建一个字符串集合，包含从0到length - 1的所有数字，然后创建另一个相同范围的集合，但只包含偶数。然后我从第一个集合中挑选出奇数。

使用 Linq Except

public void TestExcept()
{
    WriteLine($"Except {DateTime.Now}");
    int length = 20000000;
    var dateTime = DateTime.Now;
    var array = new string[length];
    for (int i = 0; i < length; i++)
    {
        array[i] = i.ToString();
    }
    Write("Populate set processing time: ");
    WriteLine(DateTime.Now - dateTime);
    var newArray = new string[length/2];
    int j = 0;
    for (int i = 0; i < length; i+=2)
    {
        newArray[j++] = i.ToString();
    }
    dateTime = DateTime.Now;
    Write("Count of items: ");
    WriteLine(array.Except(newArray).Count());
    Write("Count processing time: ");
    WriteLine(DateTime.Now - dateTime);
}

输出

Except 2021-08-14 11:43:03 AM
Populate set processing time: 00:00:03.7230479
2021-08-14 11:43:09 AM
Count of items: 10000000
Count processing time: 00:00:02.9720879

使用 HashSet.Add

public void TestHashSet()
{
    WriteLine($"HashSet {DateTime.Now}");
    int length = 20000000;
    var dateTime = DateTime.Now;
    var hashSet = new HashSet<string>();
    for (int i = 0; i < length; i++)
    {
        hashSet.Add(i.ToString());
    }
    Write("Populate set processing time: ");
    WriteLine(DateTime.Now - dateTime);
    var newHashSet = new HashSet<string>();
    for (int i = 0; i < length; i+=2)
    {
        newHashSet.Add(i.ToString());
    }
    dateTime = DateTime.Now;
    Write("Count of items: ");
    // HashSet Add returns true if item is added successfully (not previously existing)
    WriteLine(hashSet.Where(s => newHashSet.Add(s)).Count());
    Write("Count processing time: ");
    WriteLine(DateTime.Now - dateTime);
}

输出

HashSet 2021-08-14 11:42:43 AM
Populate set processing time: 00:00:05.6000625
Count of items: 10000000
Count processing time: 00:00:01.7703057

特殊的HashSet测试：

public void TestLoadingHashSet()
{
    int length = 20000000;
    var array = new string[length];
    for (int i = 0; i < length; i++)
    {
       array[i] = i.ToString();
    }
    var dateTime = DateTime.Now;
    var hashSet = new HashSet<string>(array);
    Write("Time to load hashset: ");
    WriteLine(DateTime.Now - dateTime);
}
> TestLoadingHashSet()
Time to load hashset: 00:00:01.1918160

使用 .Contains

public void TestContains()
{
    WriteLine($"Contains {DateTime.Now}");
    int length = 20000000;
    var dateTime = DateTime.Now;
    var array = new string[length];
    for (int i = 0; i < length; i++)
    {
        array[i] = i.ToString();
    }
    Write("Populate set processing time: ");
    WriteLine(DateTime.Now - dateTime);
    var newArray = new string[length/2];
    int j = 0;
    for (int i = 0; i < length; i+=2)
    {
        newArray[j++] = i.ToString();
    }
    dateTime = DateTime.Now;
    WriteLine(dateTime);
    Write("Count of items: ");
    WriteLine(array.Where(a => !newArray.Contains(a)).Count());
    Write("Count processing time: ");
    WriteLine(DateTime.Now - dateTime);
}

输出

Contains 2021-08-14 11:19:44 AM
Populate set processing time: 00:00:03.1046998
2021-08-14 11:19:49 AM
Count of items: Hosting process exited with exit code 1.
(Didnt complete. Killed it after 14 minutes)

结论：

Linq的Except在我的设备上比使用HashSets（n=20,000,000）慢了大约1秒。
使用Where和Contains需要很长时间。

有关HashSets的结论：

唯一数据
确保为类类型正确地重写GetHashCode
如果您复制数据集，则可能需要多达2倍的内存，具体取决于实现方式
HashSet针对使用IEnumerable构造函数克隆其他HashSets进行了优化，但是将其他集合转换为HashSets速度较慢（请参见上面的特殊测试）

- user3415602 · Answer 3

第一种方法：

if (list1 != null && list2 != null && list1.Select(x => list2.SingleOrDefault(y => y.propertyToCompare == x.propertyToCompare && y.anotherPropertyToCompare == x.anotherPropertyToCompare) != null).All(x => true))
   return true;

如果您可以接受重复值，第二种方法：

if (list1 != null && list2 != null && list1.Select(x => list2.Any(y => y.propertyToCompare == x.propertyToCompare && y.anotherPropertyToCompare == x.anotherPropertyToCompare)).All(x => true))
   return true;

- kame · Answer 4

一行代码：

var list1 = new List<int> { 1, 2, 3 };
var list2 = new List<int> { 1, 2, 3, 4 };
if (list1.Except(list2).Count() + list2.Except(list1).Count() == 0)
    Console.WriteLine("same sets");

- Ahmadreza TaleMasouleh · Answer 5

我写了一个通用函数来比较两个列表。

 public static class ListTools
{
    public enum RecordUpdateStatus
    {
        Added = 1,
        Updated = 2,
        Deleted = 3
    }


    public class UpdateStatu<T>
    {
        public T CurrentValue { get; set; }
        public RecordUpdateStatus UpdateStatus { get; set; }
    }

    public static List<UpdateStatu<T>> CompareList<T>(List<T> currentList, List<T> inList, string uniqPropertyName)
    {
        var res = new List<UpdateStatu<T>>();

        res.AddRange(inList.Where(a => !currentList.Any(x => x.GetType().GetProperty(uniqPropertyName).GetValue(x)?.ToString().ToLower() == a.GetType().GetProperty(uniqPropertyName).GetValue(a)?.ToString().ToLower()))
            .Select(a => new UpdateStatu<T>
            {
                CurrentValue = a,
                UpdateStatus = RecordUpdateStatus.Added,
            }));

        res.AddRange(currentList.Where(a => !inList.Any(x => x.GetType().GetProperty(uniqPropertyName).GetValue(x)?.ToString().ToLower() == a.GetType().GetProperty(uniqPropertyName).GetValue(a)?.ToString().ToLower()))
            .Select(a => new UpdateStatu<T>
            {
                CurrentValue = a,
                UpdateStatus = RecordUpdateStatus.Deleted,
            }));


        res.AddRange(currentList.Where(a => inList.Any(x => x.GetType().GetProperty(uniqPropertyName).GetValue(x)?.ToString().ToLower() == a.GetType().GetProperty(uniqPropertyName).GetValue(a)?.ToString().ToLower()))
         .Select(a => new UpdateStatu<T>
         {
             CurrentValue = a,
             UpdateStatus = RecordUpdateStatus.Updated,
         }));

        return res;
    }

}

- user10915707 · Answer 6

我认为这是一种简单易行的方法，逐个比较两个列表的元素

x=[1,2,3,5,4,8,7,11,12,45,96,25]
y=[2,4,5,6,8,7,88,9,6,55,44,23]

tmp = []


for i in range(len(x)) and range(len(y)):
    if x[i]>y[i]:
        tmp.append(1)
    else:
        tmp.append(0)
print(tmp)

- Fajoui El Mahdi · Answer 7

这是你能找到的最佳解决方案

var list3 = list1.Where(l => list2.ToList().Contains(l));

- Jibz · Answer 8

-3

也许有点好笑，但这对我很有效：

string.Join("",List1) != string.Join("", List2)

- Jibz

1

正如它在这里写的那样，即使是对于List<string>或List<int>，它也不能正常工作，例如列表11;2;3和1;12;3将是相同的，因为您没有使用某个唯一分隔符连接字符串，而该分隔符不是列表中可能的项。除此之外，对于具有许多项的列表进行字符串连接可能会降低性能。 - SwissCoder

@SwissCoder：你错了，这不会对字符串造成性能影响。如果你有两个包含50,000个字符串的列表（每个字符串长度为3），这个算法在我的机器上只需要3毫秒。而被接受的答案需要7毫秒。我认为Jibz的技巧在于只需要进行一次字符串比较。当然，他必须添加一个唯一的分隔符。 - user1027167

1

@user1027167：我不是在直接比较字符串（这也不是问题所在）。对于一个包含50,000个对象的列表，调用所有对象的.ToString()方法可能会创建一个巨大的字符串，具体取决于实现方式。我认为这不是正确的方法。此外，依赖于字符或字符串的“唯一性”也存在风险，这样的代码并不真正可重用。 - SwissCoder

好的，没错。提问者在没有给出列表数据类型的情况下询问最快的方法。也许这个答案是对提问者使用情况最快的方法。 - user1027167

1

更不用说两个对象的ToString结果相等并不意味着它们是相等的，而且这两个列表都应该被排序。 - Gert Arnold