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所以，是的， （以及）的 LINQ 实现Join正在使用最有效的通用查找数据结构之一 -哈希表。它可以在参考源中看到，并且在文档的“备注”部分中也提到（尽管不是直接）：

如果 Comparer 为 null，则使用默认相等比较器 Default 来散列和比较键。

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