Alberi: elenchi collegati vs matrici (efficienza)

Question

Questa è una domanda di assegnazione a cui sto riscontrando problemi nella formulazione di una risposta.

"Supponiamo che un albero può avere fino a k bambini per nodo. Sia v il numero medio di figli per nodo. Per quel valore (s) di y è più efficace (in termini di spazio utilizzato) per memorizzare il nodi figlio in un elenco collegato rispetto allo spazio di archiviazione in un array? Perché? "

Credo di poter rispondere al "perché?" più o meno in inglese semplice - sarà più efficiente usare l'elenco collegato perché piuttosto che avere un sacco di nodi vuoti (cioè indici vuoti nell'array se la tua media è inferiore al massimo) occupando la memoria si assegna solo spazio per un nodo in un elenco collegato quando in realtà stai compilando un valore.

Quindi se hai una media di 6 bambini quando il tuo massimo è 200, l'array creerà lo spazio per tutti i 200 figli di ogni nodo quando viene creato l'albero, ma l'elenco collegato assegnerà solo lo spazio per il nodi come necessario Quindi, con la lista collegata, lo spazio utilizzato sarà approssimativamente (?) Nella media; con l'array, spaziati usati saranno il massimo.

... Non vedo quando sarebbe più efficiente utilizzare l'array. È una domanda trabocchetto? Devo tenere conto del fatto che l'array deve avere un limite sul numero totale di nodi quando viene creato?

Answer 1

Per molte lingue comunemente utilizzate, la matrice richiederà l'allocazione di memoria k indirizzi di memoria (dei dati). Una lista collegata singolarmente richiede 2 indirizzi per nodo (dati & avanti). Una lista doppiamente collegata richiederebbe 3 indirizzi per nodo.

Let n tramite il numero effettivo di figli di un nodo particolare A:

• La matrice utilizza Indirizzi k memoria
• La lista semplicemente collegata utilizza 2 n indirizzi
• L'elenco doppiamente collegato utilizza 3 n indirizzi

Il valore k consente di determinare se 2 n o 3 n indirizzi saranno in media un guadagno o perdita rispetto al semplice memorizzare gli indirizzi in un array.

Answer 2

... Non vedo quando sarebbe più efficiente utilizzare l'array. È una domanda trabocchetto?

Non è una domanda trabocchetto. Pensa alla memoria in testa che una lista collegata ha. Come viene implementata una lista collegata (rispetto ad una matrice)?

Inoltre (sebbene ciò esuli dallo scopo della domanda!), Il consumo di spazio non è l'unico fattore decisivo nella pratica. Il caching svolge un ruolo importante nelle moderne CPU e l'archiviazione dei singoli nodi figli in una matrice anziché in una lista collegata può migliorare drasticamente la localizzazione della cache (e di conseguenza le prestazioni dell'albero).

Answer 3

Posso immaginare che potrebbe essere un'ottima idea e molto efficiente in molti scenari utilizzare uno LinkedList se l'elemento dati che si utilizza ha comunque una logica intrinseca per un articolo precedente e successivo, ad esempio uno TimeTableItem o qualcosa che è in qualche modo tempo-correlate. Questi dovrebbero implementare un'interfaccia, quindi l'implementazione di LinkedList può sfruttarla e non deve avvolgere gli oggetti nei propri oggetti nodo. L'inserimento e la rimozione sarebbero molto più efficienti qui rispetto all'utilizzo di un'implementazione List che internamente manipola gli array.

Answer 4

Le matrici devono pre-allocare lo spazio ma possiamo utilizzarle per accedere molto velocemente a qualsiasi voce.
Gli elenchi allocano memoria ogni volta che creano un nuovo nodo e ciò non è ideale perché i costi di allocazione di memoria
in tempo CPU.

Suggerimento: è possibile allocare l'intero array in una sola volta, se si vuole, ma di solito ci destinare,
consente di dire, 4 voci e noi ridimensionarlo raddoppiando la dimensione quando abbiamo bisogno di più spazio.

Answer 5

Si presume che l'array non possa essere ridistribuito dinamicamente. Se possibile, l'array vince, perché non deve essere più grande di k item (più un overhead costante), e perché non ha bisogno di storage per item per i puntatori.