Qual è la prestazione del metodo di estensione Last() per l'elenco <T>?

Question

Mi piace molto Last() e lo userei sempre per List<T> s. Ma poiché sembra essere definito per IEnumerable<T>, suppongo che enumeri prima l'enumerazione - questo dovrebbe essere O (n) in opposizione a O (1) per l'indicizzazione diretta dell'ultimo elemento di uno List<T>.

I metodi di estensione standard (Linq) sono a conoscenza di questo?

L'STL in C++ ne è a conoscenza in virtù di un intero "albero di ereditarietà" per gli iteratori e quant'altro.

Answer 1

ho appena usato riflettore di esaminare il codice per ultimo e controlla per vedere se si tratta di un IList<T> primo ed esegue la O appropriata (1) chiamata:

---

EDIT:

Su consiglio del mio avvocato ho rimosso lo snippet di codice dal riflettore. Se vuoi vedere il codice da solo ti suggerisco di prendere Reflector e farlo da solo (che tutti dovrebbero già avere) o semplicemente di guardare nella cronologia delle revisioni di questo post (poiché non c'è nulla che io possa fare al riguardo)

(o addirittura guardare la risposta di Marco che chiaramente non ha la stessa squadra legale crepa proteggendolo)

---

in modo da avere il leggero sovraccarico di un cast, ma non l'enorme sovraccarico di enumerazione.

Answer 2

Contiene un'ottimizzazione per tutto ciò che implementa IList<T> nel qual caso cerca solo l'articolo alla lunghezza -1.

Tenete a mente che la stragrande maggioranza delle cose che manderà nel implementerà IList<T>

List<int> 
int[] 

e così via ... tutto implementare IList<T>

Per coloro che non possono guardare il codice di conferma, è possibile confermare utilizzando osservazione:

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


    } 
} 

uscita:

0.123.

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

Quindi è solo 30 volte più lento e mantiene quel profilo di prestazioni con qualsiasi lista di lunghezza, che non è nulla nel grande schema di cose.

Answer 3

Per List<T> è O (1), ma per altri enumerabili può essere O (N).

Answer 4

Si può semplicemente utilizzare Ultimo con List<T> senza preoccuparsi :)

Enumerable.Last tenta di downcast l'istanza IEnumerable<T>-IList<T>. Se ciò è possibile, utilizza l'indicizzatore e la proprietà Count.

Ecco parte della realizzazione come Reflector lo vede:

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

Answer 5

Risposta breve:

O (1).

Spiegazione:

E 'evidente che Ultima() per Lista utilizza Count() metodo di estensione.

Count() controlli tipo di raccolta in fase di esecuzione e usa Conte proprietà se è disponibile.

Count proprietà per la lista ha O (1) la complessità così è il Last) metodo di estensione (.