如何优化嵌套遍历逻辑 提升C#代码执行效率？

我有如下代码，希望提升其运行速度：

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创建查找表，再为每个TradeDate对应的列表创建Fingerprint查找表是否可行？

解答： #

这个方案完全可行，而且是解决这类性能问题的典型思路。

原代码的核心问题是每次循环都要遍历整个relatedWorkflows列表做条件判断，时间复杂度为O(N*M)（N为closedWorkflows长度，M为relatedWorkflows长度），数据量较大时会导致运行极慢。

按TradeDate分组并为每组维护Fingerprint的哈希集合，能将时间复杂度降至O(N + M)，具体逻辑如下：

1. 先预处理relatedWorkflows，用字典存储：键为TradeDate，值为对应分组下所有Fingerprint的哈希集合
2. 遍历closedWorkflows时，直接通过字典快速定位对应TradeDate的Fingerprint集合，只需判断该集合中是否存在与当前workflow.Fingerprint不同的元素，即可决定是否添加

优化后的代码示例（假设TradeDate为DateTime类型，Fingerprint为string类型）：

// 预处理构建查找表
var tradeDateFingerprints = new Dictionary<DateTime, HashSet<string>>();
foreach (var r in relatedWorkflows)
{
    if (!tradeDateFingerprints.TryGetValue(r.TradeDate, out var fingerprints))
    {
        fingerprints = new HashSet<string>();
        tradeDateFingerprints[r.TradeDate] = fingerprints;
    }
    fingerprints.Add(r.Fingerprint);
}

// 遍历处理closedWorkflows
foreach (var workflow in closedWorkflows)
{
    if (tradeDateFingerprints.TryGetValue(workflow.TradeDate, out var fingerprints))
    {
        // 只要同TradeDate分组下存在至少一个不同的Fingerprint，就添加当前workflow
        if (fingerprints.Any(f => f != workflow.Fingerprint))
        {
            relatedWorkflows.Add(workflow);
            // 同步更新查找表，避免后续循环判断出错
            fingerprints.Add(workflow.Fingerprint);
        }
    }
}

更新： #

非常感谢@Dmitry Bychenko。我的测试结果显示耗时从41486毫秒降至26毫秒！

内容的提问来源于stack exchange，提问作者Anand