LINQ的OrderBy如何与MoveNext合作？

Question

这个帖子说LINQ OrderBy使用Quicksort.我正在努力解决这个问题,因为它OrderBy返回了一个IEnumerable.

我们以下面的代码为例.

int[] arr = new int[] { 1, -1, 0, 60, -1032, 9, 1 }; 
var ordered = arr.OrderBy(i => i); 
foreach(int i in ordered)
    Console.WriteLine(i); 

循环相当于

var mover = ordered.GetEnumerator();
while(mover.MoveNext())
    Console.WriteLine(mover.Current);

在MoveNext()返回下一个最小元素.该LINQ工作,除非你通过使用查询的"套现"的方式ToList()或类似的,还有不应该产生的任何中间的列表,所以每次你打电话MoveNext()的IEnumerator找到下一个最小元素.这没有意义,因为在Quicksort的执行过程中,没有当前最小和下一个最小元素的概念.

我在这里思考的缺陷在哪里？

Answer 1

LINQ的工作方式,除非你通过使用ToList()或类似方法"兑现"查询,否则不应该创建任何中间列表

这句话是错误的.你的想法中的缺陷是你相信一个错误的陈述.

LINQ to Objects实现在可能的情况下以合理的成本推迟工作.正如您所记录的那样,在排序的情况下是不可能的. OrderBy生成一个对象,当MoveNext被调用时,它枚举整个源序列,在内存中生成已排序的列表,然后枚举已排序的列表.

类似地,连接和分组也必须在枚举第一个元素之前枚举整个序列.(从逻辑上讲,连接只是一个带有过滤器的交叉产品,并且工作可以分散在每个MoveNext()上,但效率很低;为了实用,建立了一个查找表.对于渐近空间的研究是有教育意义的.与时间权衡;试一试.)

源代码可用; 如果您对实施有疑问,我建议您阅读.或者查看Jon的"edulinq"系列.