如何让嵌套的for循环更加高效？

Question

我有以下代码，我想加快速度：

foreach (var workflow in closedWorkflows)
{
    var w = relatedWorkflows.FirstOrDefault(r => r.Fingerprint != workflow.Fingerprint && r.TradeDate == workflow.TradeDate);
    if (w != null)
    {
        relatedWorkflows.Add(workflow);
    }
}

relatedWorkflows

和

closedWorkflows

是相同类型对象的列表。 我考虑过在

Fingerprint

和

TradeDate

上使用匿名类或元组创建查找或字典，但一项检查是为了相等，另一项检查是为了不平等。 在

TradeDate

上创建查找，然后为

Fingerprint

的每个查找列表在

TradeDate

上创建查找，这是一个好方法吗？

Answer 1

性能的主要问题在于

var w = relatedWorkflows.FirstOrDefault(...)

我们一次又一次地扫描

relatedWorkflows

，这就是为什么我们有

O(closedWorkflows.Count * relatedWorkflows.Count)

时间复杂度。 我们可以借助基于哈希的集合（字典和哈希集）来摆脱

relatedWorkflows.Count

，例如

var dict = workflow
  .GroupBy(item => item.TradeDate, item => item.FingerPrint)
  .ToDictionary(group => group.Key, group => group.ToHashSet());

foreach (var workflow in closedWorkflows) {
  // If we have a date, but NOT print we add it into relatedWorkflows
  if (dict.TryGetValue(workflow.TradeDate, out var prints) && 
      prints.Add(workflow.Fingerprint)) {
    relatedWorkflows.Add(workflow);
  }
}