.net - Queue<T> vs List<T>




performance difference (3)

Attualmente sto usando una List<T> come una coda (usa lst[0] poi lst.removeAt(0) ) per contenere oggetti. Ci sono circa 20 articoli max in un dato momento. Mi sono reso conto che esisteva una classe di Queue<T> . Mi chiedo se c'è qualche vantaggio (prestazioni, memoria, ecc.) Nell'usare una Queue<T> su un List<T> agisce come una coda?


Le prestazioni possono essere profilate. Anche se in questo caso di così pochi elementi, potrebbe essere necessario eseguire il codice milioni di volte per ottenere effettivamente delle differenze.

Dirò questo: la Queue<T> esporrà le tue intenzioni in modo più esplicito, le persone sanno come funziona una coda.

Un elenco utilizzato come una coda non è chiaro, specialmente se si dispone di un sacco di indicizzazione inutile e codice RemoveAt(magicNumber) . Dequeue è molto più consumabile dal punto di vista della manutenzione del codice.

Se ciò ti dà problemi di prestazioni misurabili, puoi risolverli. Non affrontare in anticipo ogni potenziale problema di prestazioni.


Oltre al fatto che la classe Queue<T> implementa una coda e la classe List<T> implementa una lista, c'è una differenza di prestazioni.

Ogni volta che rimuovi il primo elemento da List<T> vengono copiati tutti gli elementi della coda. Con solo 20 elementi in coda potrebbe non essere evidente. Tuttavia, quando si rimuove il prossimo elemento dalla Queue<T> non avviene alcuna copia di questo tipo e sarà sempre più veloce. Se la coda è lunga, la differenza può essere significativa.


Risposta breve:
Queue<T> è più veloce di List<T> quando viene usata come una coda. List<T> è più veloce della Queue<T> se utilizzato come un elenco.

Risposta lunga:
Una Queue<T> è più veloce per l'operazione di rimozione, che è un'operazione O (1). L'intero blocco degli elementi successivi dell'array non viene spostato verso l'alto. Questo è possibile perché una Queue<T> non deve facilitare la rimozione da posizioni casuali, ma solo dall'alto. Quindi mantiene una testa (da cui viene estratto l'elemento su Dequeue ) e la posizione della coda (a cui l'oggetto viene aggiunto su Enqueue ). D'altra parte rimuovendo dalla cima di una List<T> richiede di spostare le posizioni di ogni articolo successivo su. Questo è O (n) - il caso peggiore se si sta rimuovendo dall'alto, che è ciò che un'operazione di dequeue è. Il vantaggio in termini di velocità può essere notevole se si interrompe il ciclo.

Una List<T> è più performante se hai bisogno di accesso indicizzato, recupero casuale, ecc. Una Queue<T> dovrà enumerare completamente per trovare la posizione di indice appropriata (non espone IList<T> ).

Detto questo, uno Stack<T> vs List<T> è molto più vicino, non c'è differenza di prestazioni nelle operazioni push e popping. Entrambi spingono fino alla fine e rimuovono dalla fine delle strutture dell'array (entrambi sono O (1)).

Ovviamente dovresti usare la struttura corretta che rivela l'intento. Nella maggior parte dei casi si esibiranno meglio anche perché sono fatti su misura per lo scopo. Credo che se non ci fosse stata alcuna differenza di prestazioni, Microsoft non avrebbe incluso Queue<T> e Stack<T> nel framework per semantica semplicemente diversa. Sarebbe stato semplicemente facilmente estensibile se fosse così. Pensa a SortedDictionary<K, V> e SortedList<K, V> , entrambi i quali fanno esattamente la stessa cosa ma sono differenziati solo dalle caratteristiche delle prestazioni; trovano un posto in BCL.







difference