List <T>的Last()扩展方法的性能如何？

Question

我非常喜欢Last()并且会一直使用它List<T>.但是因为它似乎被定义了IEnumerable<T>,我想它首先枚举枚举 - 这应该是O(n)而不是O(1)直接索引a的最后一个元素List<T>.

标准(Linq)扩展方法是否意识到这一点？

C++中的STL通过迭代器和诸如此类的整个"继承树"来意识到这一点.

Answer 1

我只是使用引用源查看Last的代码,它检查它是否是IList<T>第一个并执行适当的O(1)调用:

public static TSource Last < TSource > (this IEnumerable < TSource > source) {
    if (source == null) throw Error.ArgumentNull("source");
    IList < TSource > list = source as IList < TSource > ;
    if (list != null) {
        int count = list.Count;
        if (count > 0) return list[count - 1];
    }
    else {
        using(IEnumerator < TSource > e = source.GetEnumerator()) {
            if (e.MoveNext()) {
                TSource result;
                do {
                    result = e.Current;
                } while ( e . MoveNext ());
                return result;
            }
        }
    }
    throw Error.NoElements();
}

所以你有一个演员的轻微开销,但不是枚举的巨大开销.

Answer 2

你可以使用Last而List<T>不用担心:)

Enumerable.Last尝试将IEnumerable<T>实例向下转换为IList<T>.如果可以,则使用索引器和Count属性.

以下是Reflector看到的实现的一部分:

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

Answer 3

它包含对实现的任何内容的优化,IList<T>在这种情况下它只是查找项目的长度-1.

请记住,您将发送的绝大多数内容都将实现 IList<T>

List<int> 
int[] 

等等...全部实施 IList<T>

对于那些无法查看代码进行确认的人,可以使用观察来确认:

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();
        }


    }
}

输出:

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

因此它只有30倍的速度,并且保持了你所拥有的任何长度列表的性能配置文件,这在大型方案中没有任何意义.