在C#中优化列表性能

Question

我正在处理一个项目(.NET 3.5)，读取两个文件，比较它们并找到缺失的对象。

基于这些数据，我需要进一步解析并定位对象位置。我将尝试进一步解释：

我有两个列表： 1个列表是服务器上所有文件的长列表，以及它们在服务器上的物理地址或其他服务器上，此文件略大于10亿行，并持续增长(有些荒谬，我知道)。文件大小目前约为160MB。 另一个列表是报告列表，显示服务器上丢失的文件，与列表1相比微不足道，通常不到1MB的大小。

我必须将列表2与列表1相交，并确定缺失对象的位置。列表中的项看起来像这样（不幸的是它是以空格分隔而不是CSV文档）： filename.extension rev rev# source server:harddriveLocation\|filenameOnServer.extension origin

使用流，我将两个文件读入不同的字符串列表中。然后我采用正则表达式并将列表2中的项目解析到第三个列表中，其中包含filename.extension、rev和rev#。所有这些都工作得很好，问题在于性能太差。

我希望有一种更有效的方法来完成我正在做的事情。

foreach (String item in slMissingObjectReport)
{
    if (item.Contains(".ext1") || item.Contains(".ext2") || item.Contains(".ext3"))
    {
        if (!item.Contains("|"))
        {                                     
            slMissingObjects.Add(item + "," + slMissingObjectReport[i + 1] + "," + slMissingObjectReport[i + 2]); //object, rev, version
        }
    }

    i++;
}

int j = 1; //debug only

foreach (String item in slMissingObjects)
{
    IEnumerable<String> found = Enumerable.Empty<String>();
    Stopwatch matchTime = new Stopwatch(); //used for debugging
    matchTime.Start(); //start the stop watch

    foreach (String items in slAllObjects.Where(s => s.Contains(item.Remove(item.IndexOf(',')))))
    {
        slFoundInAllObjects.Add(item);
    }

matchTime.Stop();

tsStatus.Text = "Missing Object Count: " + slMissingObjects.Count + " | " + "All Objects count: " + slAllObjects.Count + " | Time elapsed: " + (taskTime.ElapsedMilliseconds) * 0.001 + "s | Items left: " + (slMissingObjects.Count - j).ToString();

j++;
}

taskTime.Stop();
lstStatus.Items.Add(("Time to complete all tasks: " + (taskTime.ElapsedMilliseconds) * 0.001) + "s");

这种方法是有效的，但由于目前我的缺失对象列表中有1300个缺失项，所以平均需要8到12分钟才能完成。其中耗时最长的部分是

foreach (String items in slAllObjects.Where(s => s.Contains(item.Remove(item.IndexOf(',')))))
{
    slFoundInAllObjects.Add(item);
}

我只需要正确方向的指引，以及如何改进我正在努力完成的代码的帮助。LINQ并不是看起来很困难的部分，似乎是将其添加到列表中会影响性能。

- BinaryAssault

---

为什么不使用数据库？ - Hamid Pourjam

列表插入的时间复杂度是O(n)，因此使用列表作为数据结构，插入操作永远不会有最佳优化。那么堆栈或哈希表呢？此外，您是否已经进行了分析，确保已经找到代码的缓慢部分？ - David L

如果列表是预分配的，插入操作可以达到O(1)，你能预分配吗？ 至少给出一个合理的期望值？ - Yosef O

不要使用List，而是使用HashSet。 - Robert McKee

slFoundInAllObjects.AddRange(slObjects.Where.....); 为什么不使用 AddRange？试一下，看看问题是否可能出在其他地方。 - Jagannath

这整个问题可能更适合于http://codereview.stackexchange.com/。 - mclark1129

Answer 1

Hashsets是专门设计用来处理此类任务的，您拥有唯一值并且需要进行比较。

列表则不是。它们只是任意收集的东西。

我首选使用 HashSet<> 和相应的交集方法，因为它可以方便地实现。

- Moo-Juice

---

这里是关于List和HashSet性能的一些统计数据：https://dev59.com/0XVC5IYBdhLWcg3w51hv - Robert McKee

我在使用Hashsets时遇到了问题，具体问题是在使用'Hashset.ContainsKey'时需要找到哈希集中单个键的部分匹配项。因此，我需要将哈希集键拆分为多个字符串（例如文件名/版本/位置等），然后进行搜索（如果可能的话）。这样做对吗？另外，很抱歉我在SO上发布评论时经常修改，因为我是新手。 - BinaryAssault

好的，我已经将所有内容转换为哈希表，并按建议使用了交集。唯一的问题是包含所有对象的文件有我需要的某些信息。因此，当我读取每行时，我对其应用了正则表达式以剥离出我需要的内容（并匹配文件2的输入）。这将帮助我克服第一个障碍，稍后我需要进一步完善我的正则表达式以收集所需的所有信息。感谢大家的帮助，我能够在不到一分钟的时间内匹配所有1300个项目。 - BinaryAssault

Answer 2

您可以进行的一项改进是使用 AddRange 而不是 Add。 AddRange 将允许内部列表为添加预分配所需的内存，而不是在 foreach 循环过程中多次分配。

IEnumerable<string> items = slAllObjects.Where(s => s.Contains(item.Remove(item.IndexOf(','));
slFoundInAllObjects.AddRange(items);

其次，在您的Where lambda中，您应该避免使用item.Remove(item.IndexOf(',')，因为这会导致它针对列表中的每个项目执行一次。该值是静态的，您可以提前执行一次。

var itemWithoutComma = item.Remove(item.IndexOf(','));
IEnumerable<string> items = slAllObjects.Where(s => s.Contains(itemWithoutComma));
slFoundInAllObjects.AddRange(items);

- mclark1129

---

我不认为选项1会奏效；slAllObjects.Where(s => s.Contains(item.Remove(item.IndexOf(','));将返回一个IEnumerable<String>。 - BinaryAssault

是的，那是我的语法错误。我会修复它。不过 AddRange 的重点在于一次添加整个集合，所以 IEnumerable<string> 恰好是你想要的。 - mclark1129

它仍然相当慢。没有addrange（或者说没有add），它是非常快的。我在我的OP中定义了一个IEnumerable<String>。我测量时间的方式是在自己的线程中运行任务，并计算处理项目的速度。平均而言，似乎每秒钟处理1个项目。当你有1300个项目时，速度相当慢。我将转换为哈希集并查看结果如何。感谢您的帮助和快速响应。 - BinaryAssault

Answer 3

有几个瓶颈被指出来了。

如果我理解正确，你正在做以下事情：

1. 读取两个文件到2个列表中。O(K)
2. 遍历一个列表（O(n)），并在另一个列表中搜索匹配项（O(m)）。
3. 创建一个包含这些匹配项的新列表。（O(n)）

因此，你有一个大概是： O(K + m * n * n) 的东西。 瓶颈发生在步骤2和3（代码中的内部循环）。

解决方案：

1. 你正在搜索的集合（我想是slAllObjects）应该是可以快速搜索的，所以要么使用哈希集，要么对其进行排序一次，然后使用二进制搜索在此集合中查找项目。
2. 预分配你要创建的列表。你提前知道大小，所以将容量设置为相同。

如果你使用哈希集，则此解决方案应将O(n^2) * O(m) 减少到 O(n) * O(k)，如果你对列表进行排序，则减少到O(n) * log(m)。

- Yosef O

Answer 4

首先，不要使用List。使用HashSet进行更快的插入和比较。

接下来，确定列表是否按预排序顺序排列。如果是，则可以同时快速读取两个文件，并且只需对每个文件进行一次遍历，而无需在内存中保留它们。

如果其他方法都失败了，请考虑使用LINQ的Intersects方法，这可能比您自己编写的版本表现更好。

- Robert McKee

Answer 5

除了已经提出的建议，我认为可以考虑使用树。如果我理解正确，文件名中存在某种层次结构（例如：服务器、文件路径、文件名等），对吧？通过使用树，您可以在每个步骤中大大减少搜索空间。

此外，如果您在每个节点中使用Dictionary<String, Node>，则可以减少搜索时间，这将成为O(1)，考虑到层次级别的常数数量。

另外，如果您决定使用数组或数组列表，请避免使用foreach，而应该使用for，因为它应该更快（不使用迭代器，因此至少对于数组列表来说，应该更快）。

如果有任何不清楚的地方，请告诉我。

- Gentian Kasa