使用其他列表中的详细信息填充大型对象列表

Question

我有一个大型数据库查询，它将100k记录返回到内存列表中。我需要将相关员工的列表链接到每条记录（也围绕100k记录），但我很难获得可用的性能。

foreach (var detail in reportData.Details)
{
    detail.Employees = employees
      .Where(x => x.AccountingDocumentItemId == detail.AccountingDocumentItemId)
      .Select(x => x.Employee)
      .ToList();

    detail.Employee = String.Join(", ", detail.Employees);
}

上面的代码需要8分钟才能完成。我已经将速度问题缩小到for loop的第一线，在那里它找到了相关的员工。如果我遗漏ToList()它超级快，但接下来的行立即导致String.Join导致Where执行的问题。

我显然是从错误的角度接近这个，但我已经筋疲力尽了我认为可行的选择。

Answer 1

您当前的代码具有O(n ** 2)时间复杂度（嵌套循环），因此您需要执行1e5 * 1e5 ~ 1e10（10亿）操作，这需要8分钟才能完成。

让我们提取一个字典，以便拥有O(n)时间复杂度（仅限~1e5操作）：

var dict = reportData
  .Details
  .GroupBy(item => item.AccountingDocumentItemId,
           item => item.Employee)
  .ToDictionary(chunk => chunk.Key, 
                chunk => chunk.ToList());

foreach (var detail in reportData.Details) {
  detail.Employees = dict.TryGetValue(detail.AccountingDocumentItemId, out var list) 
    ? list.ToList()        // copy of the list 
    : new List<MyClass>(); // put the right type instead of MyType

  detail.Employee = String.Join(", ", detail.Employees);
}