代码之家 › 专栏 › 技术社区 › Daren Thomas

list的last()扩展方法的性能如何?

extension-methods linq .net c#

Daren Thomas · 技术社区 · 15 年前

我真的很喜欢 Last() 会一直用它 List<T> 但因为它似乎是为 IEnumerable<T> ,我想它首先枚举枚举-这应该是o(n),而不是o(1),用于直接索引 列表& T; .

标准(LINQ)扩展方法是否知道这一点?

C++中的STL通过一个完整的“继承树”来了解迭代器和WHATNOT。

5 回复 | 直到 15 年前

HarshWombat 6 年前

我刚用过 Reference Source 查找最后一个代码并检查它是否是 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();
}

所以你有一个演员的轻微开销,但没有枚举的巨大开销。

Mark Seemann 15 年前

你可以用最后一个 List<T> 不用担心:)

可枚举。上次尝试将 IEnumerable<T> 实例到 IList<T> . 如果可能,则使用indexer和count属性。

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

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

Sam Saffron James Allen 15 年前

它包含对任何实现 IList<T> 在这种情况下,它只查找长度为-1的项目。

请记住,您将发送的绝大多数内容都将实现 ILIST & T;T & GT;

List<int> 
int[]

等等…全部实施 ILIST & T;T & GT;

对于那些看不到要确认的代码的人,可以通过观察来确认:

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倍,并且用您拥有的任何长度的列表来维护性能配置文件,这在大计划中是没有意义的。

Brian Rasmussen 15 年前

为了 List<T> 它是O(1),但对于其他可枚举项,它可能是O(n)。

Konstantin Spirin 15 年前

简短回答 :

O(1)。

解释 :

很明显 最后() 对于表使用 计数() 扩展方法。

计数() 在运行时检查集合的类型并使用计数属性(如果可用)。

计数 List的属性具有O(1)复杂性,因此 最后() 扩展方法。