C#如何快速处理大量数据列表

Question

我尝试查找一些与我的问题相关或对我的应用程序有意义的文章，但没有找到任何相关的内容。这是我的问题：

我有两个列表，每个列表中都有超过20,000个项目。

我需要检查每个列表中的每个项目是否与另一个列表中的每个项目匹配。

类似以下实现的代码：

    foreach(var item1 in List1)
    {
         foreach(var item2 in List2)
         {
              // Check item 1 against item 2. 
              // Check item 2 against item 1.
         }
    }

由于检查工作的原因，处理这些大型项目列表变得非常缓慢且无法使用。

是否有更有效的方法来处理这些需要此类检查的大型项目列表？

如果有更多信息可以提供，请告诉我。感谢任何帮助/建议。

我正在使用C＃.NET 3.5

编辑：让我简要解释一下检查。

item1和item2是路径系统的一部分。 item1和item2由N个其他项目连接。 我正在检查item1是否连接（有效路径）到item2，并且item2连接到item1。 不能假定如果item1 -> item2，则item2 -> item1。 因此，两个检查都是必要的。

数据库包含有关item1 -> item2以及item2 -> item1的信息以及如何进行操作。

在检查中，存在对服务的命名管道调用以执行检查。 服务执行所有路径检查并返回item1 -> item2等。

- therealjohn

---

如果有大量的数据和数据库混合在一起，您能否在迭代所有数据之前在数据库中执行一些预先过滤操作？ - 48klocs

请提供有关列表的更多信息。这些值是否唯一？如果是，您应该使用哈希集；框架哈希集实现具有高效的集合比较操作。 - Jamie Treworgy

从逻辑上讲，您正在执行某种“连接”操作，因此应该使用内置于您的数据库中的机制（和优化）来实现它... - Paul Michalik

Answer 1

这是一个O(N * M)的检查。

如果您只是在某个关键字上进行相等比较，那么假设哈希码合理且关键字分布良好，您可以通过O(N + M)次迭代来完成。在.NET中最简单的方法是使用LINQ join：

var pairs = from x in List1
            join y in List2 on x.Key1 equals y.Key2
            select new { x, y}; // Or whatever

foreach (var pair in pairs)
{
    // Process each match
}

当然，如果你不需要检查相等性，这并没有什么帮助……但是如果没有更多的上下文信息，就很难给出具体的帮助。

- Jon Skeet

Answer 2

长时间的循环加上数据库查询会导致性能极差。

你应该尝试先运行一些查询，获取所需数据，然后对该数据进行 N x M 次检查。

当然，并不是所有情况都可以这样做；这真的取决于你要进行的检查类型。

- Roman Starkov

---

我不确定在我的条件下是否可能。每个item1都必须进入检查调用的服务以验证路线。 - therealjohn

Answer 3

我建议将双方都转换为哈希表（每个表的O(n)），遍历每个列表并在另一个表中进行O(1)查找以检查是否包含当前项（总体上是o(n)）。这样可以得到总体的O(n)时间复杂度。

我曾经处理过大约100万个元素的列表，记得通常可以在1秒左右完成。

- Andrew Long

Answer 4

尽量避免每次迭代都向数据库发送请求的情况。如果可能，尝试在循环外部进行一次查询，或者在循环外部获取所需数据，然后对这些数据进行检查。

所有操作都取决于检查操作。因此，请描述它们。但无论如何，如果您的迭代是独立的，您也可以使用PLINQ和Task Parallel Library并行化您的循环。

数据并行性（任务并行库）

如何编写简单的Parallel.ForEach循环

- Regfor

---

谢谢提供的链接，看起来很有用，但是它只支持.NET 4.0，而我们被限制在3.5。 - therealjohn

我没有注意到你正在使用.NET 3.5。对于.NET 3.5，TPL是不可能使用的。但是可以并行化循环迭代。当单个迭代需要很长时间且彼此独立时，应该使用ThreadPool.QueueUserWorkItem和Wait句柄来等待所有迭代结束。因此，这与TPL中的数据并行性相同，但是需要手动实现。 - Regfor

Answer 5

Lambda表达式和Linq

我会节省时间并避免使用循环。我相信你想要实现的任何目标都可以通过LINQ查询来完成。

例如，在另一个集合中查找一个值，或者在另一个集合中查找一组项目。

以下是一个示例，说明如何按照名称对包含在另一个集合中的项目进行排序，并获取这些项目的集合：

var result = from x in List1
         where (from c in List2
                select c.Id).Contains(x.Id)
                select x).OrderByDescending(x => x.Name);

- InspiredBy