为什么`.Select(...).Last()`优化,但是`.Select(...).Last(...)`不？

Question

考虑以下枚举器:

var items = (new int[] { 1, 2, 3, 4, 5 }).Select(x =>
{
    Console.WriteLine($"inspect {x}");
    return x;
});

这会产生元素[1, 2, 3, 4, 5],在消耗时打印它们.

当我Last在这个枚举器上调用该方法时,它会触发一个只访问单个元素的快速路径:

items.Last();

inspect 5

但是当我将回调传递给Last它时,它从头开始遍历整个列表:

items.Last(x => true);

inspect 1
inspect 2
inspect 3
inspect 4
inspect 5

浏览.NET Core源代码,我发现:

• Last(IEnumerable<T>)转发TryGetLast(IEnumerable<T>, out bool) ;
• TryGetLast(IEnumerable<T>, out bool)有一条快速的道路IPartition<T> ;
• 而且由于ArraySelectIterator<T>工具IPartition<T>,这个快速路径被触发,一切都很顺利.

另一方面:

• Last(IEnumerable<T>, Func<T, bool>) 转发到 TryGetLast(IEnumerable<T>, Func<T, bool>, out bool)
• 这对快速路OrderedEnumerator和IList<T>,但不会ArraySelectIterator<T>.
• 因此,它采用慢速路径并从头开始迭代.

这解释了如何不优化回调情况.但它没有解释原因.

从概念上讲,如果至少有一个元素满足谓词(可能在实践中),则向后迭代可以允许提前退出循环.

它似乎也难以实现:从我所看到的,所需要的只是一个额外的方法IPartition<T>.

缺乏优化也可能令人惊讶.由于这些重载具有相同的名称,因此可以假设它们也以类似的方式进行优化.(至少那是我的想法.)

鉴于优化此案例的这些原因,为什么LINQ的作者选择不这样做呢？

Answer 1

Last()始终可以针对允许在恒定时间 ( ) 内访问集合的最后一个元素的集合进行优化O(1)。对于这些集合，您可以直接访问最后一个元素，而不是迭代所有集合并返回最后一个元素。

从概念上讲，如果至少一个元素满足谓词（这在实践中很可能），则向后迭代可能允许提前退出循环。

对于 的通用实现来说，这个假设太牵强了Last(Func<T,bool>)。一般来说，您不能假设满足谓词的最后一个元素更接近集合的末尾。该优化对于您的示例效果很好 ( Last(x=>true))，但对于每个这样的示例，都可能存在一个相反的示例，其中该优化性能较差 ( Last(x=>false))。