Does List.Insert ha una penalizzazione delle prestazioni?

Question

dato un elenco:

List<object> SomeList = new List<object>(); 

Vuol fare:

SomeList.Insert(i, val); 

vs.

SomeList.Add(val); 

Ha qualche penalità per le prestazioni? In caso affermativo, come si dipende da:
- indice di inserimento
- - iSomeList.Count - La dimensione della lista

Answer 1

La classe List è l'equivalente generico della classe ArrayList. Implementa l'interfaccia generica IList utilizzando un array le cui dimensioni vengono aumentate dinamicamente secondo necessità.

(source)

significa che i dati interni vengono memorizzati come un array, e così è probabile che per eseguire il insert è necessario spostare tutti gli elementi per fare spazio, così la sua complessità è O (N), mentre add è un'operazione O (1) a tempo costante (ammortizzata), quindi sì.

Sommario - Sì, sarà quasi sempre più lento, e otterrà più lento è il più grande la vostra lista ottiene.

Answer 2

In caso di dubbio, eseguire un esperimento empirico:

List<object> SomeList = new List<object>(); 

     Stopwatch sw = new Stopwatch(); 
     sw.Start(); 
     for (var i = 0; i < 100000; i++) 
      SomeList.Insert(0, String.Empty); 
     sw.Stop(); 
     Console.WriteLine(sw.Elapsed.TotalMilliseconds); 
     sw.Reset(); 

     SomeList = new List<object>(); 
     sw.Start(); 
     for (var i = 0; i < 100000; i++) 
      SomeList.Add(String.Empty); 
     sw.Stop(); 
     Console.WriteLine(sw.Elapsed.TotalMilliseconds); 

L'inserimento avviene 2800ms sulla mia macchina; l'aggiunta richiede 0.8ms. Quindi sì, Insert è molto meno performante.

Answer 3

Certo che lo è.

Poiché List<T> è supportato da un array, qualsiasi operazione da inserire all'inizio dell'elenco deve spostare (o copiare) tutti gli altri elementi dell'array. Un'operazione che si aggiunge alla fine dell'elenco avverrà in un tempo costante, indipendentemente dal numero di elementi nell'elenco.

Answer 4

Il mio primo pensiero è stato "Sì, c'è una penalità di prestazioni perché Insert deve spostare tutti gli elementi nella lista di uno slot per fare spazio al nuovo oggetto" - ma poi ho letto la domanda con più attenzione. Quindi:

In generale, Insert prende (forse molto) più tempo perché ha bisogno di spostare tutti gli elementi già in lista per fare spazio per il nuovo elemento, quindi è un (n) O sul lunghezza dell'elenco (se l'elenco è pieno di capacità, sarà necessario ridimensionarlo, ma è ancora un'operazione O (n)). D'altra parte Add aggiunge semplicemente il nuovo oggetto senza dover spostare nulla, quindi è più veloce - un'operazione O (1) (a meno che l'elenco non debba ridimensionare, come sopra).

In questo esempio specifico, in cui l'elenco è vuoto per iniziare, non ci sarà alcuna differenza di prestazioni.

Ovviamente tutto questo è un po 'discutibile perché è necessario scegliere i metodi in base a ciò che è l'intento a meno che non si disponga di un problema di prestazioni documentato.

Answer 5

Per un elenco vuoto, non è diverso.

Ma per qualsiasi altra cosa deve essere più lento * perché per inserire nella parte anteriore, l'intero array di supporto deve essere spostato uno a destra.

* Tranne il caso in cui lo Add causa l'aumento di Capacity.

Answer 6

Mi rendo conto che questo è già stato esaurientemente risposto, ma vorrei sottolineare che queste informazioni sono prontamente disponibili nella documentazione MSDN.

The documentation for List<T>.Insert() stati:

Questo metodo è un'operazione O (n), dove n è Count.

The documentation for List<T>.Add() stati:

Se Count è inferiore Capacità, questo metodo è un'operazione O (1) funzionamento. Se la capacità deve essere aumentata per accogliere il nuovo elemento, questo metodo diventa un'operazione O (n), dove n è Count.

Se vi capita di essere questa domanda perché si ha una situazione in cui si desidera eseguire frequenti aggiunge al fronte e retro di una lista, quindi la struttura di dati appropriato da utilizzare è un Deque.

Stephen Cleary ha fornito una buona implementazione Deque qui: http://nitodeque.codeplex.com/