如何比较和更新包含大量项目的 2 个列表？

Question

注意：使用 LINQ 连接解决了这个问题。我需要比较源列表中的列表值是否存在于目标列表中，如果是，则将其保存到第三个列表。我编写的代码确实有效，但它花费了很多时间，因为我的源列表有 30k 个项目，并且它将每个项目值与 1500 万个目标列表进行比较，这需要很多时间。因为它每次都会遍历整个列表（30k *1500 万次）查看显然不是最佳但可以完成工作的代码。        // The below code will generate the lists from CSV file        The lists are below for sample        **Source List**        FileId  FilePath      FileChecksum        1       somepath A    check1        2       somepath AA   check2        3       somepath AAB  check3        4       somepath B    check4        5       somepath BB   check5        **Destination List**        StepId  StatusID  JobId ProjectId FileId     FilePath        5        6         4    2091      577206853  somepath A        5        6         4    2092      577206853  somepath AA        5        6         4    2093      577206853  somepath AAA        5        6         4    2094      577206853  somepath AB        5        6         4    2095      577206853  somepath A        5        6         4    2096      577206853  somepath B        5        6         4    2097      577206853  somepath BB        List<Source> SourceList = File.ReadAllLines(@"D:\source.csv").Skip(1).Select(v => Source.SourceFromCSv(v)).ToList();        List<Destination> DestinationList = File.ReadAllLines(@"D:\Destination.csv").Skip(1).Select(d => Destination.FromDestinationCSV(d)).ToList();        //This will compare and create a new list        var result1 =            from s in SourceList            from d in DestinationList            where (d.FilePath.ToLower() == s.FilePath.ToLower())             select (d.StepId + "," + d.StatusId + "," + d.JobId + "," +              d.ProjectId + "," + d.FileId + "," + d.FilePath + "," + 

Answer 1

您可以对两个列表进行排序，然后逐行进行比较。算法复杂度为 O(n log n+n)。

您将第一行数据 A 与第一行数据 B 进行比较，然后在“较大”行上增加指针的索引。如果数据 A 有 8 而数据 B 有 7 和 9，当你达到 9 时，你就会知道数据 B 中不存在 8。

您应该开始比较最大可能的索引。这样，如果列表确实是一个子列表，您可以快速终止。

Answer 2

你可以反过来做。您可以迭代 3000 万个条目，而不是从 30k 个源条目中选择一个。如果找到所有 30k 个条目，或者在最坏的情况下，找到 3000 万个条目，则可以停止。那还是比 30K*15M 好。

Answer 3

var query = from s in SourceList

 join d in DestinationList on 

 s.FilePath.ToLower().TrimEnd() equals d.FilePath.ToLower().TrimEnd()

 select (d.StepId + "," + d.StatusId + "," + d.JobId + "," +d.ProjectId + "," + d.FileId + "," + d.FilePath + "," + s.FileChecksum);

LINQ join 在不到 5 秒的时间内完成了同样的事情。

Answer 4

是的，如果您不需要列表的所有功能，将基本类型设置为 aHashSet<T>将显着改善查找。您的自定义类型可能需要实现适当的GetHashCode()功能以进一步提高查找速度。

看：

• HashSet<T>

• GetHashCode()

不要调用new HashSet(query.ToList())，而是在实例化列表时直接转换为哈希集，query.ToHashSet()可选地传入一个 Equality Comparer，见下文：

• ToHashSet(IEqualityComparer<T>)

除了自定义GetHashCode实现之外，您还可以实现自定义IEqualityComparer来处理特定情况，例如您的情况，其中特定字段构成了平等规则。现在的 Visual Studio 和 Resharper 提供了一个内置的重构来生成GetHashCodeEquals.

看：

• IEqualityComparer<T>

然后，您可以使用IntersectWith一次调用获取两组中的所有项目：

看：

• IntersectWith()

创建一个可以将Source和转换Destination为的特殊对象，或者为它们提供相同的基类将允许这样做。

您也可以使用 aIDictionary<Key, Value>并使密钥成为Item.FilePath.ToLower()，与上述相同的原则适用。这将允许运行时使用字符串检查该项目是否存在于其他列表中GetHashCode，默认情况下这是高度优化的。

Answer 5

原则上，您所做的只是将文件校验和附加到目标列表的末尾。

从源列表中创建一个散列或字典，然后你的新列表看起来像这样。

//create dictionary SourceDictionary<string,string> with key = filepath.tolower and value = checksum

var newList = DestinationList.select(d => $"{d.thing1},{d.thingN}" + SourceDictionary[d.filename.tolower()])

应该快得多