Was is the performance of the Last() extension method for List<T>?

Question

I really like Last() and would use it all the time for List<T>s. But since it seems to be defined for IEnumerable<T>, I guess it enumerates the enumeration first - this should be O(n) as opposed to O(1) for directly indexing the last element of a List<T>.

Are the standard (Linq) extension methods aware of this?

The STL in C++ is aware of this by virtue of a whole "inheritance tree" for iterators and whatnot.

Answer 1

It contains an optimisation for anything that implements IList<T> in which case it just looks up the item at length -1.

Keep in mind that the vast majority of stuff you will send in will implement IList<T>

List<int> 
int[]

and so on ... all implement IList<T>

For those who can not look at the code to confirm, you can confirm it using observation:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ConsoleApplication4 {
    class Program {

        static void Profile(string description, int iterations, Action func) {

            // clean up
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();

            // warm up 
            func();

            var watch = Stopwatch.StartNew();
            for (int i = 0; i < iterations; i++) {
                func();
            }
            watch.Stop();
            Console.Write(description);
            Console.WriteLine(" Time Elapsed {0} ms", watch.ElapsedMilliseconds);
        }

        static void Main(string[] args) {
            int[] nums = Enumerable.Range(1, 1000000).ToArray();

            int a;

            Profile("Raw performance", 100000, () => { a = nums[nums.Length - 1];  });
            Profile("With Last", 100000, () => { a = nums.Last(); }); 

            Console.ReadKey();
        }


    }
}

Output:

Raw performance Time Elapsed 1 ms
With Last Time Elapsed 31 ms

So it's only 30 times slower and maintains that performance profile with whatever length list you have, which is nothing in the big scheme of things.

Answer 2

I just used reflector to look into the code for Last and it checks to see if it is a IList<T> first and performs the appropriate O(1) call:

---

EDIT:

On the advice of my lawyer I have removed the code snippet from reflector. If you want to see the code for yourself I suggest you either get Reflector and do it yourself (which everyone should have already) or more simply look in the revision history of this post (since there is nothing I can do about that)

(Or indeed look at Mark's answer who clearly doesn't have the same crack legal team protecting him)

---

So you have the slight overhead of a cast, but not the huge overhead of enumerating.

Answer 3

For List<T> it is O(1), but for other enumerables it may be O(N).

Answer 4

You can just use Last with List<T> without worrying :)

Enumerable.Last attempts to downcast the IEnumerable<T> instance to IList<T> . If this is possible, it uses the indexer and Count property.

Here is part of the implementation as Reflector sees it:

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

Answer 5

Short answer:

O(1).

Explanation:

It's evident that Last() for List uses Count() extension method.

Count() checks type of the collection in runtime and uses Count property if it's available.

Count property for list has O(1) complexity so is the Last() extension method.