我非常喜欢使用 Last()
方法,并且通常在处理 List<T>
时会用到它。但是,由于该方法似乎是为 IEnumerable<T>
定义的,所以我猜测它首先枚举了枚举 - 这应该是 O(n),而直接索引 List<T>
的最后一个元素则为 O(1)。
标准(Linq)扩展方法是否知道这一点?
C++ STL 通过迭代器和其他内容的完整“继承树”意识到了这一点。
我非常喜欢使用 Last()
方法,并且通常在处理 List<T>
时会用到它。但是,由于该方法似乎是为 IEnumerable<T>
定义的,所以我猜测它首先枚举了枚举 - 这应该是 O(n),而直接索引 List<T>
的最后一个元素则为 O(1)。
标准(Linq)扩展方法是否知道这一点?
C++ STL 通过迭代器和其他内容的完整“继承树”意识到了这一点。
我刚才使用了参考源代码查看了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();
}
你需要进行一次轻微的强制类型转换,但不需要承受枚举的巨大开销。你可以放心使用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];
}
}
如果实现了 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倍,并且在您拥有的任何长度列表中都保持了这种性能特征,在大局观中并不算什么。
HashSet<T>
没有实现IList<T>
。 - LukeH对于 List<T>
来说,时间复杂度为 O(1),但对于其他的可枚举对象来说,它可能是 O(N)。
简短回答:
O(1)。
解释:
显然,List 的 Last() 使用了 Count() 扩展方法。
Count() 在运行时检查集合的类型,并使用 Count 属性(如果可用)。
列表的 Count 属性具有 O(1) 复杂度,因此 Last() 扩展方法也是如此。
Last
方法并不使用Count
扩展方法,但你说得对,在某些情况下这两种方法都可以是O(1)的:Last
检查集合是否实现了IList<T>
接口,如果是,则通过索引获取最后一个元素而不是枚举;Count
方法检查集合是否实现了ICollection<T>
接口,如果是,则只需获取Count
属性而不是枚举。 - LukeHLast
方法,那么它必须对集合进行O(n)的枚举,以确定哪些项与谓词匹配。 - LukeHIList<T>
直到找到与给定条件匹配的第一个(即最后一个)元素吗?这会比当前框架中更改善最佳情况的性能表现。 - LukeH
vector
上的end()
与list
上的不同实现,任何想要使用它们的迭代器的东西都必须在Iterator
类型参数上进行模板化。 - Pavel Minaev