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

Question

我非常喜欢使用 Last() 方法，并且通常在处理 List<T> 时会用到它。但是，由于该方法似乎是为 IEnumerable<T> 定义的，所以我猜测它首先枚举了枚举 - 这应该是 O(n)，而直接索引 List<T> 的最后一个元素则为 O(1)。

标准（Linq）扩展方法是否知道这一点？

C++ STL 通过迭代器和其他内容的完整“继承树”意识到了这一点。

- Daren Thomas

---

迭代器的继承树是什么？C++首先没有扩展方法，因此vector上的end()与list上的不同实现，任何想要使用它们的迭代器的东西都必须在Iterator类型参数上进行模板化。 - Pavel Minaev

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

你需要进行一次轻微的强制类型转换，但不需要承受枚举的巨大开销。

- Martin Harris

---

可能发布我轮椅的轮子照片也是违法的，因为有人邀请它。有时我认为人们在版权问题上变得有些疯狂。 - Stefan Steinegger

如果（this.m_handle == IntPtr.Zero） - mackenir

发布来自反编译软件 Reflector 的片段并无问题。 - user7116

好的一面是，代码仍然在编辑历史记录中:D打倒律师。 - Gusdor

现在您可以使用参考源代码来查看Last扩展的实现。 - Matthiee

Answer 2

你可以放心使用List<T>的Last方法 :)

Enumerable.Last尝试将IEnumerable<T>实例向下转换为IList<T>。如果可能，它会使用索引器和计数属性。

这是部分实现代码，如同Reflector所展示的：

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

- Mark Seemann

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


    }
}

输出:

原始性能 时间消耗 1 毫秒
带上一次时间消耗 31 毫秒

因此，它只慢了30倍，并且在您拥有的任何长度列表中都保持了这种性能特征，在大局观中并不算什么。

- Sam Saffron

---

只是一个小问题：HashSet<T>没有实现IList<T>。 - LukeH

Answer 4

对于 List<T> 来说，时间复杂度为 O(1)，但对于其他的可枚举对象来说，它可能是 O(N)。

- Brian Rasmussen

Answer 5

简短回答:

O(1)。

解释:

显然，List 的 Last() 使用了 Count() 扩展方法。

Count() 在运行时检查集合的类型，并使用 Count 属性（如果可用）。

列表的 Count 属性具有 O(1) 复杂度，因此 Last() 扩展方法也是如此。

- Konstantin Spirin

---

Last方法并不使用Count扩展方法，但你说得对，在某些情况下这两种方法都可以是O(1)的：Last检查集合是否实现了IList<T>接口，如果是，则通过索引获取最后一个元素而不是枚举；Count方法检查集合是否实现了ICollection<T>接口，如果是，则只需获取Count属性而不是枚举。 - LukeH

谢谢Luke，我并不是完全正确。Last方法对于IList使用Count属性，复杂度为O(1)。我刚刚查看了Last(this collection, predicate)的代码，它的复杂度是O(N)，这是一种懒惰的方式。 - Konstantin Spirin

@Konstantin：如果你将一个谓词传递给Last方法，那么它必须对集合进行O(n)的枚举，以确定哪些项与谓词匹配。 - LukeH

Luke，当前的实现“总是”遍历整个集合，而我提出的方案在最坏情况下给出O(n)，如果匹配元素的数量是O(n)，则为O(1)。 - Konstantin Spirin

@Konstantin：我不确定你具体在提议什么。你是指通过反向迭代IList<T>直到找到与给定条件匹配的第一个（即最后一个）元素吗？这会比当前框架中更改善最佳情况的性能表现。 - LukeH