C# Linq中Where&All比Select&Except性能更优的原因探究

我在测试两种集合差集实现方式的性能时，发现用Where结合All的写法比Select搭配Except的写法性能更优，同时也了解到一种LINQ查询写法性能表现更好，但核心疑问是前者更快的原因。

我的测试代码如下：

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

[Serializable]
public class ADSASDCollection
{
    public GameObject gameO;
}

public class test : MonoBehaviour
{
    public List<ADSASDCollection> list;
    public List<GameObject> gameList;

    void Start()
    {
        var time = DateTime.Now;
        var count = 100000;

        for (int i = 0; i < count; i++)
        {
            foreach (var o in list.Where(item => gameList.All(item2 => item2 != item.gameO)))
            {
            }
        }

        Debug.Log($"Time - {time - DateTime.Now}");
        time = DateTime.Now;
        
        var select = list.Select(item2 => item2.gameO).ToArray();

        for (int i = 0; i < count; i++)
        {
            foreach (var o in gameList.Except(select))
            {
            }
        }

        Debug.Log($"Time - {time - DateTime.Now}");
    }
}

另外还有一种性能更优的LINQ写法：

var query = (from a in gameList
             from b in list
             where a != b.gameO
             select a);

为什么.Where+All比.Except更快？ #

核心原因在于两者的执行逻辑和重复开销的差异：

• Where+All的执行逻辑
  这种写法是遍历list中的每个元素，对每个元素调用gameList.All(...)——而All方法是短路求值：只要找到第一个与当前item.gameO匹配的元素，就会立即停止遍历gameList并返回false，不会遍历整个集合。10万次循环中，每次内部的遍历都可能提前终止，整体开销被控制住。

• Select+Except的执行逻辑
  首先Select+ToArray是一次性提取所有gameO元素，这部分开销不大，但问题出在10万次循环里的gameList.Except(select)：Except方法内部会每次都创建一个新的HashSet，把select中的元素全部加入进去，然后再遍历gameList检查元素是否不在这个HashSet中。HashSet的创建和元素插入是有固定开销的，这个开销被10万次循环放大后，整体性能就被拖垮了。

更高效的差集实现方案 #

想要真正优化性能，应该把HashSet的创建移到循环外面，避免重复初始化：

var time = DateTime.Now;
var count = 100000;

// 只初始化一次HashSet，复用整个循环
var gameOSet = new HashSet<GameObject>(list.Select(item => item.gameO));

for (int i = 0; i < count; i++)
{
    foreach (var o in gameList.Where(item => !gameOSet.Contains(item)))
    {
    }
}

Debug.Log($"Optimized Time - {DateTime.Now - time}");

HashSet的Contains操作是O(1)的时间复杂度，加上只做一次初始化，这个方案的性能会远高于之前的两种写法。

另外需要注意：你提到的LINQ双重查询写法，虽然性能可能优于前两者，但它会返回重复元素（同一个gameList元素会被多次选中，只要在list中有多个不匹配的项），逻辑上和前两种方式（返回无重复的差集）不完全一致，使用时需要注意这一点。

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