c# - 为什么 `.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>) forwards to TryGetLast(IEnumerable<T>, out bool) ;
• TryGetLast(IEnumerable<T>, out bool) has a fast path for IPartition<T> ;
• 自 ArraySelectIterator<T> implements IPartition<T> ，这条快速路径被触发，一切都很好。

另一方面:

• Last(IEnumerable<T>, Func<T, bool>) forwards to TryGetLast(IEnumerable<T>, Func<T, bool>, out bool)
• 这有 OrderedEnumerator and IList<T> , but not ArraySelectIterator<T> 的快速路径.
• 因此它采用慢速路径并从头开始迭代。

这解释了如何未优化回调案例。但它没有解释原因。

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

实现起来似乎也不难:据我所见，只需要在 IPartition<T> 上添加一个方法即可.

缺乏优化也可能令人惊讶。由于这些重载共享相同的名称，人们可能会认为它们也以类似的方式进行了优化。 (至少我是这么想的。)

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

Answer 1

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

Conceptually, if at least one element satisfies the predicate (which is likely in practice), then iterating backward may allow for exiting the loop early.

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