Qual è la performance del metodo di estensione Last () per List ?

Mi piace veramente Last() e userei tutto il tempo per List s. Ma poiché sembra essere definito per IEnumerable , immagino che enumeri prima l’enumerazione – questo dovrebbe essere O (n) in opposizione a O (1) per l’indicizzazione diretta dell’ultimo elemento di una List .

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

Lo STL in C ++ ne è consapevole in virtù di un intero “albero di ereditarietà” per gli iteratori e quant’altro.

Ho appena usato la Reference Source per esaminare il codice per Last e controlla se è un IList prima ed esegue la chiamata O (1) appropriata:

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

Quindi hai il leggero overhead di un cast, ma non l’enorme overhead dell’enumerazione.

Puoi semplicemente usare Ultimo con List senza preoccuparti 🙂

Enumerable.Last tenta di downcast l’istanza IEnumerable in IList . Se ciò è ansible, utilizza l’indicizzatore e la proprietà Count.

Qui fa parte dell’implementazione visto da Reflector :

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

Contiene un’ottimizzazione per tutto ciò che implementa IList nel qual caso cerca solo l’object alla lunghezza -1.

Tieni presente che la maggior parte delle cose che invierai implementeranno IList

 List int[] 

e così via … tutti implementano IList

Per coloro che non possono guardare il codice per confermare, puoi confermarlo usando l’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(); } } } 

Produzione:

 Prestazioni non elaborate Tempo trascorso 1 ms
 Con l'ultima volta è trascorso 31 ms

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

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

Risposta breve :

O (1).

Spiegazione :

È evidente che Last () per List utilizza il metodo di estensione Count () .

Count () controlla il tipo di raccolta in runtime e utilizza la proprietà Count se è disponibile.

La proprietà Count per la lista ha la complessità O (1), quindi è il metodo di estensione Last () .