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>)转发给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 的作者选择不这样做呢？

标签： c#.netlinq

Answer 1

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

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

对于Last(Func<T,bool>). 您不能假设满足谓词的最后一个元素通常更接近集合的末尾。该优化适用于您的Last(x=>true)示例（Last(x=>false)