5

我试图找到一些关于我的问题的文章，但没有找到任何相关的或对我的应用程序有意义的东西。这是我的问题：

我有两个（> 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 和 if/how item2 -> item1。在检查内部，有一个对服务的命名管道调用来进行检查。该服务会执行所有路径检查，并在 item1 -> item2 等情况下返回。

4

5 回答 5

4

那是一张O(N * M)支票。

如果您只是比较某个键或其他键的相等性，那么假设合理的哈希码和良好的键分布，您可以摆脱 O(N + M) 次迭代。在 .NET 中执行此操作的最简单方法是使用 LINQ 连接：

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
}

当然，如果您不检查是否相等，这将无济于事……但是如果没有更多上下文，几乎不可能提供任何具体帮助。

于 2012-06-20T17:22:58.113 回答
2

长循环 + 数据库查询 = 糟糕的性能。

您应该尝试做的是首先运行一些查询，获取您需要的数据，然后针对该数据进行 N x M 检查。

当然，这不一定是可能的。真的取决于你正在做的检查类型。

于 2012-06-20T17:21:39.100 回答
1

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

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

数据并行（任务并行库）

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

于 2012-06-20T17:22:42.500 回答
1

我建议将每个表的两边都转换为哈希表 (O(n)) 并扫描每个列表并在另一个表中进行 O(1) 查找以检查它是否包含当前项目 (o(n) 整体）。这导致总体上为 O(n)。

我用 ~1,000,000 的列表做了类似的事情，它通常在我记得的 ~1 秒范围内完成。

于 2014-09-17T21:26:18.053 回答
-1

Lambda 表达式和 Linq

我会节省时间并远离循环。我确信您想要实现的任何目标都可以通过 LINQ 查询来完成。

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

这是一个示例，如何按 ID 获取包含在另一个集合中的项目集合，例如按名称排序：

var result = from x in List1
         where (from c in List2
                select c.Id).Contains(x.Id)
                select x).OrderByDescending(x => x.Name);
于 2012-06-20T17:24:51.080 回答