如何比较和更新包含大量项目的 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&nbsp;join d in DestinationList on&nbsp;&nbsp;s.FilePath.ToLower().TrimEnd() equals d.FilePath.ToLower().TrimEnd()&nbsp;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 = checksumvar newList = DestinationList.select(d => $"{d.thing1},{d.thingN}" + SourceDictionary[d.filename.tolower()])应该快得多