c# - Linq GroupJoin 与 Linq All in Select 的效率对比

Question

Linq 是否使用任何排序或其他机制来提高组连接的效率，这样它就不必为每个不匹配的项目遍历整个集合？

换句话说，这是:

var x = listA.GroupJoin(
listB, a => a.prop,
b => b.prop,
(a, b) => new { a, b })
.Where(!x.b.Any()).Select(x => x.a);

比这更有效:

var x = listA.Where(a => listB.All(b => b.prop != a.prop));

Answer 1

我想问题是关于 LINQ to Objects，即 Enumerable.GroupJoin .所以，是的，GroupJoin(以及Join)的 LINQ 实现使用最有效的通用查找数据结构之一 - hash table .在reference source中可以看到并且在文档中的 Remarks 部分中也提到了(虽然不是直接提到的):

If comparer is null, the default equality comparer, Default, is used to hash and compare keys.

由于哈希查找的时间复杂度为 O(1)，连接操作的复杂度为 O(N)，而在第二种情况下为 O(N * M)，因此连接操作的效率肯定高得多。