Почему '.Select(...). Last()' оптимизирован, а ".Select(...). Last (...)" нет?
Рассмотрим следующий перечислитель:
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, я обнаружил, что:
С другой стороны:
Это объясняет, как случай обратного вызова не оптимизирован. Но это не объясняет почему.
Концептуально, если хотя бы один элемент удовлетворяет предикату (что вероятно на практике), то итерация в обратном направлении может позволить досрочно выйти из цикла.
Это также не кажется сложным для реализации: из того, что я видел, все, что требуется, это дополнительный метод в IPartition<T>.
Отсутствие оптимизации также может быть удивительным. Поскольку эти перегрузки имеют одно и то же имя, можно предположить, что они также оптимизированы аналогичным образом. (По крайней мере, так я и думал.)
Учитывая эти причины для оптимизации этого случая, почему авторы LINQ решили не делать этого?
Ответы
Ответ 1
Last() всегда может быть оптимизирована для коллекций, которые обеспечивают доступ к последнему элементу коллекции в постоянное время (O(1)). Для этих коллекций вместо итерации всей коллекции и возврата последнего элемента вы можете просто получить доступ к последнему элементу напрямую.
Концептуально, если хотя бы один элемент удовлетворяет предикату (что вероятно на практике), то итерация в обратном направлении может позволить досрочно выйти из цикла.
Это предположение слишком далеко для общей реализации Last(Func<T,bool>). Вы не можете предположить, что последний элемент, который удовлетворяет предикату, ближе к концу коллекции в целом. Эта оптимизация хорошо работает для вашего примера (Last(x=>true)), но для каждого такого примера может быть противоположный пример, где эта оптимизация работает хуже (Last(x=>false)).
