¿Cuál es el rendimiento del método de extensión Last () para List ?

Realmente me gusta Last() y lo usaría todo el tiempo para List s. Pero dado que parece estar definido para IEnumerable , supongo que enumera primero la enumeración, esto debería ser O (n) en oposición a O (1) para indexar directamente el último elemento de una List .

¿Los métodos de extensión estándar (Linq) son conscientes de esto?

El STL en C ++ es consciente de esto en virtud de un “árbol de herencia” completo para iteradores y otras cosas.

Acabo de utilizar la fuente de referencia para ver el código de Last y comprueba si es un IList primero y realiza la llamada O (1) apropiada:

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

Así que tienes la ligera sobrecarga de un yeso, pero no la gran sobrecarga de enumerar.

Puedes usar Last with List sin preocuparte 🙂

Enumerable.Last intenta IEnumerable la IEnumerable a IList . Si esto es posible, usa el indexador y la propiedad Count.

Aquí hay parte de la implementación, como Reflector lo ve:

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

Contiene una optimización para cualquier cosa que implemente IList en cuyo caso solo busca el elemento a la longitud -1.

Tenga en cuenta que la gran mayoría de las cosas que enviará implementarán IList

 List int[] 

y así sucesivamente … todos implementan IList

Para aquellos que no pueden ver el código para confirmarlo, puedes confirmarlo usando la observación:

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

Salida:

 Rendimiento sin procesar Tiempo transcurrido 1 ms
 Con el último tiempo transcurrido 31 ms

Por lo tanto, es solo 30 veces más lento y mantiene ese perfil de rendimiento con cualquier lista de longitud que tenga, lo cual no es nada en el gran esquema de cosas.

Para List es O (1), pero para otros enumerables puede ser O (N).

Respuesta corta :

O (1).

Explicación

Es evidente que Last () for List usa el método de extensión Count () .

Count () verifica el tipo de la colección en tiempo de ejecución y usa la propiedad Count si está disponible.

La propiedad Count para la lista tiene una complejidad O (1), por lo que es el método de extensión Last () .