Unoptimized IEnumerable<>.Last with predicate

user_809009 0
Viewed 114

The public static TSource Last<TSource>(this IEnumerable<TSource> source) extension method for IEnumerable<TSource> uses optimization for a source of the IList<TSource> type so that it does not iterate over the whole sequence when it can just step at the end using indexing.

IList<TSource> tSources = source as IList<TSource>;
if (tSources != null)
{
    int count = tSources.Count;
    if (count > 0)
    {
        return tSources[count - 1];
    }
}

I slightly altered the code so that it is mroe readable, but the functionality remains the same.

Why is not public static TSource Last<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) also optimized when it could clearly start iterating from the end of the sequence?

If there should be something that matches the predicate and it is near the start of the sequence then I still need to iterate to the very end. If there is something matching at the end I don't have to iterate more, because I started from the end.

I would expect something like this being a part of the method.

IList<TSource> tSources = source as IList<TSource>;
if (tSources != null)
{
    int count = tSources.Count;
    if (count > 0)
    {
        for (int i = count - 1; i >= 0; i--)
        {
            if (predicate(tSources[i]))
            {
                return tSources[i];
            }
        }
    }
}
ienumerable extension-methods linq .net c#
2 Answers

My guess, which is a shot in dark, as any answer you might get: optimizing in the predicate case would cause more side effects. Optimization generally causes a side-effect because the GetEnumerator() of IEnumarble is not called. But in the predicate case, you can observe from the outside that it's not called in order. One might write a predicate that expects the iteration to happen in order, and going backwards would break that.

user_5521390

Except when an implementation of IList<T> contains a very small number of items, optimizing the non-predicate Last to return theList[theList.Count()-1] is unlikely to be slower than simply enumerating from the start; it's unlikely that for any reasonable IList<T> implementation it will be much slower. Even though the time required for some implementations of IList<T> to find an item by index may be significantly longer than the average per-item time required to fetch data sequentially (perhaps by an order of magnitude, though probably not two), reading one item by index will generally take much less time than reading every item sequentially (random access generally won't be much slower than sequential access unless a collection is big; if in a 1,000,000-item collection the cost to read an item by index is 1,000 times the per-item time required for sequential access [an atypically-large penalty], that would still be 1,000 times as fast as reading every item).

When using Last with a predicate, there's no guarantee how many items will need to be examined. If random access takes longer than sequential access (common), and the last match happens to occur early in the list (highly plausible), then processing the list from the start will be faster than processing from the end. Given that it would not be unreasonable for an IList<T> implementation to take ten times as long to perform a random access as a sequential fetch, the "optimization" of reading from the back could end up making things an order of magnitude slower than "unoptimized" code that read sequentially.

If IList<T> provided more options for reading out data, and/or included properties which roughly described the relative costs of different operations, then a Last method could be optimized to examine list items in some other sequence, but absent such features it's better for the method to use a straightforward approach whose behavior is predictable if uninspiring, than one which tries to be clever but might sometimes perform much worse.

user_3637510
Related