Perché SortedList e List usano array e perché LinkList non è molto usato?

Question

Nella mia mente, lo List viene sostanzialmente implementato utilizzando LinkedList, mentre un normale Array viene implementato come blocchi contigui. Ho sempre usato List perché è nello spazio dei nomi Generic e perché pensavo che fosse utilizzato l'allocazione della memoria dinamica - ma mi sbagliavo.

Ieri ho visto l'implementazione di List utilizzando Reflector e trovato che è in realtà una matrice di T (T[]). Ci sono un sacco di Array.Copy in giro mentre si manipola ciascun elemento nello List. Ad esempio, quando si utilizza Insert, verrà creata una nuova memoria e verranno copiati tutti gli elementi prima/dopo gli elementi inseriti. Quindi mi sembra che l'uso di List sia molto costoso.

Ho visto anche lo SortedList. Non sono sicuro del perché un SortedList implementa anche un array al suo interno. Non pensi che SortedList sarebbe orribile utilizzare un array in quanto è necessario ordinare l'elenco ogni volta che si verifica una piccola manipolazione dello List?

Mi chiedo anche perché lo List sia così popolare come la maggior parte delle persone lo usa piuttosto che andare per LinkedList. È solo a causa della flessibilità dell'indicizzatore?

Answer 1

Sì, SortedList è O (n) per gli inserti. Usare con attenzione.

Il motivo principale è la progettazione di computer moderni. La cache della CPU è molto importante perché la RAM è così lenta. Il design del bus di memoria non riusciva a stare al passo con i rapidi progressi della velocità di clock della CPU. Fare un segnale digitale ad alta frequenza viaggiare più di un pollice è molto difficile.

Un array ha prestazioni cache imbattibili, è molto probabile che l'elemento successivo sia già nella cache quando lo si itera. Un elenco collegato dà probabilità molto piccole che questo è il caso, l'elemento successivo è essenzialmente a un indirizzo casuale. È costoso, blocca il processore, in attesa che la RAM raggiunga il livello. Possono essere centinaia di cicli.

Answer 2

Poiché la maggior parte delle raccolte non ha bisogno di inserimenti nel mezzo spesso. Ma hanno bisogno di accedere direttamente tramite un indicizzatore.

Answer 3

Nella vita reale Lista non chiama Array.Copy spesso, di solito basta accodare elementi da array, non inserire. È uno scopo di Elenco, a differenza di un elenco collegato. Dovresti solo scegliere una classe di raccolta appropriata.

Se si inseriscono elementi, utilizzare spesso l'elenco collegato. Se per la maggior parte aggiungete articoli e avete bisogno di iterarli efficacemente, usate List.

Answer 4

Se si desidera una raccolta in memoria di un unico tipo per il quale:

1. La raccolta deve essere growable.
2. L'operazione di mutazione più comune è che aggiunge un elemento alla fine della raccolta.
3. Il recupero rapido tramite indice è essenziale.

quindi List<T> è probabilmente la scelta migliore. LinkedList<T> potrebbe essere una scelta migliore quando (2) e (3) non si applicano.