Perché lo stack <T> e la coda <T> sono implementati con un array?

Question

Sto leggendo C# 4.0 in a Nutshell dai fratelli Albahari e mi sono imbattuto in questo:

Le pile sono implementate internamente con una matrice che ha ridimensionato come richiesto, come con coda e lista. (pg 288, paragrafo 4)

Non posso fare a meno di chiedermi perché. LinkedList fornisce O (1) inserimenti e cancellazioni di testa e coda (che dovrebbero funzionare bene per uno stack o una coda). Un array ridimensionabile ha O (1) inserto ammortizzato (se ricordo bene), ma O (n) caso peggiore (non sono sicuro dell'eliminazione). E probabilmente usa più spazio della lista collegata (per grandi stack/code).

C'è dell'altro? Qual è l'aspetto negativo di un'implementazione di una lista doppiamente collegata?

Answer 1

ma O (n) nel caso peggiore

Il ammortizzato caso peggiore è ancora O (1). I tempi di inserimento lunghi e brevi si aggirano mediamente - questo è l'intero punto dell'analisi ammortizzata (e lo stesso per la cancellazione).

Un array utilizza anche in meno dello spazio rispetto a un elenco collegato (che dopo tutto deve memorizzare un puntatore aggiuntivo per ciascun elemento).

Inoltre, il sovraccarico è molto meno che con un elenco collegato. Tutto sommato, un'implementazione basata su array è (molto) più efficiente per quasi tutti i casi d'uso, anche se di tanto in tanto un accesso richiederà un po 'più di tempo (infatti, una coda può essere implementata in modo leggermente più efficiente prendendo vantaggio delle pagine che sono gestite da sole in un elenco collegato - vedere l'implementazione std::deque di C++).

Answer 2

Ecco un calcolo ipotetico di massima delle risorse di memoria utilizzato per una pila di 100 System.Int32 s:

Un'implementazione serie richiederebbe il seguente:

type designator       4 bytes 
object lock        4 
pointer to the array      4 (or 8) 
array type designator     4 
array lock        4 
int array        400 
stack head index       4 
             --- 
Total         424 bytes (in 2 managed heap objects) 

Un'implementazione lista collegata richiederebbe il seguente:

type designator       4 bytes 
object lock        4 
pointer to the last node     4 (or 8) 
node type designator   4 * 100 = 400 
node lock     4 * 100 = 400 
int value     4 * 100 = 400 
pointer to next node 4 (or 8) * 100 = 400 (or 800) 
            ----- 
Total        1,612 bytes (in 101 managed heap objects) 

Il downside principale dell'implementazione dell'array sarebbe l'atto di copiare l'array quando è necessario Xpanded. Ignorando tutti gli altri fattori, questa operazione sarebbe O (n) dove n è il numero di elementi nello stack. Sembra una cosa piuttosto brutta se non per due fattori: non accade quasi mai, poiché l'espansione è raddoppiata ad ogni incremento e l'operazione di copia dell'array è altamente ottimizzata ed è incredibilmente veloce. Pertanto, l'espansione è, in pratica, facilmente sommersa da altre operazioni di stack.

Analogamente per la coda.

Answer 3

Questo perché .NET è stato progettato per funzionare su processori moderni. Che sono molto, molto più veloci del bus di memoria. Il processore funziona a circa 2 gigahertz. La RAM della tua macchina ha un clock tipicamente di un paio di centinaia di megahertz. La lettura di un byte dalla RAM richiede oltre cento cicli di clock.

Il che rende le cache della CPU molto importanti per i processori moderni, una grande quantità di chip in loco viene masterizzata per rendere le cache più grandi possibile. Tipico oggi è 64 KB per la cache L1, la memoria più veloce e fisicamente situata molto vicino al core del processore, 256 KB per la cache L2, più lento e più lontano dal core, circa 8 MB per la cache L3, più lento e più lontano via, condiviso da tutti i core del chip.

Per rendere effettive le cache, è molto importante accedere alla memoria in modo sequenziale. La lettura del primo byte può essere molto costosa se è necessario un accesso alla memoria L3 o RAM, i successivi 63 byte sono molto economici. La dimensione della "linea della cache", l'unità di trasferimento dei dati per il bus di memoria.

Questo rende una matrice di gran lunga la più efficace struttura di dati, i suoi elementi sono memorizzati in modo sequenziale in memoria. E una lista collegata di gran lunga la peggiore struttura dati possibile, i suoi elementi sono naturalmente dispersi nella memoria, potenzialmente incorrendo nella carenza di cache molto costosa per ogni elemento.

Di conseguenza, tutte le raccolte .NET, ad eccezione di LinkedList <, vengono implementate come array internamente. Si noti che uno Stack <> è già naturalmente implementato come array poiché è possibile solo premere e inserire un elemento dalla fine dell'array. Un'operazione O (1). Il ridimensionamento dell'array viene ammortizzato O (logN).