问题描述 #

我正在开发一个.NET Core 3.1应用程序，需要使用LINQ对SearchResult列表进行过滤，当前代码可正常运行，但我对其性能表现存在疑问，希望能得到优化建议。

需求目标 #

• 对SearchResult结果集进行过滤，最终结果中每个Id必须唯一；
• 若存在多个相同Id的项：
  • 优先保留带有ContactId的项，移除无ContactId的项；
  • 若所有相同Id的项均无ContactId，则保留第一个出现的项；
• 最终结果需按Id升序、ContactId升序排序。

相关类定义 #

public class SearchResult 
{ 
    public int? Id {get; set;} 
    public int? ContactId {get; set;} 
}

当前实现代码 #

public class Program 
{ 
    public static void Main() 
    { 
        var searchResults = new List<SearchResult> { 
            new SearchResult { Id = 1 }, 
            new SearchResult { Id = 2 }, // yes 
            new SearchResult { Id = 3 }, // yes 
            new SearchResult { Id = 4 }, // yes 
            new SearchResult { Id = 5 }, 
            new SearchResult { Id = 1, ContactId = 1 }, // yes 
            new SearchResult { Id = 5, ContactId = 3 }, // yes 
            new SearchResult { Id = 1, ContactId = 1 }, 
            new SearchResult { Id = 8, ContactId = 4 }, // yes 
            new SearchResult { Id = 1 }, 
            new SearchResult { Id = 2 }, 
            new SearchResult { Id = 10 }, // yes 
            new SearchResult { Id = 11 }, // yes 
            new SearchResult { Id = 12 }, // yes 
        }; 

        // group1 without contactId 
        var group1 = searchResults 
            .Where(sr => sr.ContactId == null) 
            .GroupBy(sr => sr.Id) 
            .Select(grp => grp.First()); 

        // group2 WITH contactId 
        var group2 = searchResults 
            .Where(sr => sr.ContactId != null) 
            .GroupBy(sr => sr.Id) 
            .Select(grp => grp.First()); 

        // joined = group1.Id - group2.Id 
        var joined = group1.Where(g1 => !group2.Any(g2 => g2.Id == g1.Id)); 

        // result = group2 + joined 
        var merged = new List<SearchResult>(); 
        merged.AddRange(group2); 
        merged.AddRange(joined); 

        // result ordered by id then by contactId 
        var result = merged 
            .OrderBy(x => x.Id) 
            .ThenBy(x => x.ContactId); 

        foreach(var sr in result){ 
            Console.WriteLine(sr.Id + " " + sr.ContactId); 
        } 
    } 
}

目前代码可满足需求，但希望了解是否有更优的实现方案以提升性能。

回答 #

嘿，你的实现思路是对的，但当数据量变大时，原代码里的一些操作会成为性能瓶颈——尤其是group1.Where(g1 => !group2.Any(g2 => g2.Id == g1.Id))这一步，每一个group1的元素都要遍历整个group2来判断是否存在，时间复杂度是O(m*k)，数据量大的时候会拖慢速度。下面给你两个更高效的优化方案：

方案1：GroupBy+组内排序（简洁且高效） #

我们可以直接按Id分组，然后在每个组内先排序（优先选有ContactId的，无ContactId的则保留第一个出现的），最后取每组的第一个元素，再统一排序。这样只需要遍历原列表一次，分组一次，性能比原实现好很多：

var result = searchResults
    // 给每个元素标记原始索引，方便后续保留第一个出现的无ContactId项
    .Select((sr, index) => new { SearchResult = sr, OriginalIndex = index })
    .GroupBy(x => x.SearchResult.Id)
    .Select(grp => 
        grp.OrderByDescending(x => x.SearchResult.ContactId.HasValue) // 有ContactId的排前面
           .ThenBy(x => x.SearchResult.ContactId) // 按ContactId升序
           .ThenBy(x => x.OriginalIndex) // 无ContactId时，保留第一个出现的项
           .First().SearchResult)
    .OrderBy(sr => sr.Id)
    .ThenBy(sr => sr.ContactId);

这个方案的时间复杂度是O(n log n)，主要来自排序操作，比原实现的O(n + m*k)高效很多，而且代码简洁易读。

方案2：使用哈希表（Dictionary）遍历一次完成筛选（极致性能） #

哈希表的查找和插入都是O(1)操作，我们可以遍历原列表一次，用字典记录每个Id对应的最优项，这是性能最优的方案，时间复杂度为O(n)：

var idToBestResult = new Dictionary<int?, SearchResult>();

foreach (var sr in searchResults)
{
    // 跳过Id为null的项（如果你的需求需要保留这类项，可以调整逻辑）
    if (sr.Id == null) continue;

    if (idToBestResult.TryGetValue(sr.Id, out var existingResult))
    {
        // 判断当前项是否比已有项更优
        bool shouldReplace = false;

        // 已有项无ContactId，当前项有 → 替换
        if (!existingResult.ContactId.HasValue && sr.ContactId.HasValue)
        {
            shouldReplace = true;
        }
        // 两者都无ContactId → 保留第一个出现的，不替换
        // 两者都有ContactId → 原逻辑是取第一个出现的，所以不替换；如果需要取更小的ContactId，可以改成 sr.ContactId < existingResult.ContactId
        else if (existingResult.ContactId.HasValue && sr.ContactId.HasValue)
        {
            shouldReplace = sr.ContactId < existingResult.ContactId;
        }

        if (shouldReplace)
        {
            idToBestResult[sr.Id] = sr;
        }
    }
    else
    {
        // 该Id首次出现，直接加入字典
        idToBestResult.Add(sr.Id, sr);
    }
}

// 转换为列表并按要求排序
var result = idToBestResult.Values
    .OrderBy(sr => sr.Id)
    .ThenBy(sr => sr.ContactId);

这个方案适合数据量非常大的场景，因为只需要遍历原列表一次，没有额外的分组或多次遍历操作，性能优势非常明显。

原实现的性能瓶颈总结 #

原实现需要多次遍历原列表（group1和group2各一次），而且group1.Where(...)中的Any操作是嵌套循环，当group1和group2的元素数量较多时，这一步会消耗大量时间。优化后的方案要么减少遍历次数，要么用哈希表避免嵌套循环，都能有效提升性能。

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