Perché la matrice vettoriale è raddoppiata?

Question

Perché l'implementazione classica di Vector (ArrayList per persone Java) raddoppia la dimensione dell'array interno su ogni espansione invece di triplicarla o quadruplicarla?

Answer 1

Quando si calcola il tempo medio di inserimento in un vettore, è necessario consentire gli inserti non crescenti e gli inserti crescenti.

Chiama il numero totale di operazioni per inserire n elementi o _totale e la media o _media .

Se inserisci n e cresci di un fattore A come richiesto, allora ci sono o _totale = n + & # 931; A ⁱ [0 < i < 1 + ln _A n] operazioni. Nel peggiore dei casi si utilizza 1 / A della memoria allocata.

Intuitivamente, A = 2 significa nel peggiore dei casi che hai o _totale = 2n , quindi o _media è O (1) e nel caso peggiore si utilizza il 50% della memoria allocata.

Per una A più grande, hai un o_totale più basso, ma più spazio sprecato.

Per una A più piccola, o_totale è più grande, ma non si spreca così tanto spazio. Finché cresce geometricamente, è ancora O (1) tempo di inserimento ammortizzato, ma la costante aumenterà.

Per i fattori di crescita 1,25 (rosso), 1,5 (ciano), 2 (nero), 3 (blu) e 4 (verde), questi grafici mostrano l'efficienza del punto e della dimensione media (rapporto tra dimensione / spazio allocato; più è meglio ) a sinistra e efficienza temporale (rapporto di inserzioni / operazioni; di più è meglio) a destra per l'inserimento di 400.000 articoli. L'efficienza spaziale del 100% viene raggiunta per tutti i fattori di crescita appena prima del ridimensionamento; il caso di A = 2 mostra un'efficienza temporale compresa tra il 25% e il 50% e un'efficienza spaziale di circa il 50%, il che è positivo per la maggior parte dei casi:

Per i runtime come Java, gli array vengono riempiti con zero, quindi il numero di operazioni da allocare è proporzionale alla dimensione dell'array. Tenerne conto riduce la differenza tra le stime di efficienza temporale:

Answer 2

Il raddoppio esponenziale delle dimensioni dell'array (o della stringa) è un buon compromesso tra avere abbastanza celle nell'array e sprecare troppa memoria.

Supponiamo che iniziamo con 10 elementi:

1 - 10
2 - 20
3 - 40
4 - 80
5 - 160

Quando triplichiamo le dimensioni, cresciamo troppo velocemente

1 - 10
2 - 30
3 - 90
4 - 270
5 - 810

In pratica cresceresti forse 10 o 12 volte. Se triplichi, lo faresti forse 7 o 8 volte: il colpo di runtime per la riallocazione è che poche volte è sufficientemente piccolo di cui preoccuparti, ma è più probabile che superi completamente la dimensione richiesta.

Answer 3

Se dovessi allocare un blocco di memoria di dimensioni insolite, allora quando quel blocco viene deallocato (o perché lo stai ridimensionando o ottiene GC'd) ci sarebbe un buco di memoria di dimensioni insolite che potrebbe causare mal di testa per il gestore della memoria. Quindi di solito si preferisce allocare memoria in potenze di due. In alcuni casi il gestore della memoria sottostante ti fornirà solo blocchi di determinate dimensioni e, se richiedi una dimensione strana, arrotonderà alla dimensione successiva successiva. Quindi, piuttosto che chiedere 470 unità, ottenere comunque 512 e poi ridimensionare una volta che hai usato tutti i 470 che hai richiesto, potresti anche chiedere 512 per cominciare.

Answer 4

Qualsiasi multiplo è un compromesso. Rendilo troppo grande e sprechi troppa memoria. Rendilo troppo piccolo e perdi molto tempo per riallocazioni e copie. Immagino che il raddoppio sia lì perché funziona ed è molto facile da implementare. Ho anche visto una libreria proprietaria simile a STL che usa 1,5 come moltiplicatore per lo stesso - immagino che i suoi sviluppatori abbiano considerato il raddoppio sprecando troppa memoria.

Answer 5

Se stai chiedendo l'implementazione specifica di Java di Vector e ArrayList , quindi non è necessariamente raddoppiato su ogni espansione.

Da Javadoc per Vector:

  

Ogni vettore tenta di ottimizzare la gestione dell'archiviazione mantenendo un capacity e un capacityIncrement. La capacità è sempre almeno pari alla dimensione del vettore; di solito è più grande perché quando i componenti vengono aggiunti al vettore, la memoria del vettore aumenta in blocchi di dimensioni ensureCapacity(int minCapacity). Un'applicazione può aumentare la capacità di un vettore prima di inserire un gran numero di componenti; ciò riduce la quantità di riallocazione incrementale.

Uno dei costruttori per Vector consente di specificare le dimensioni iniziali e l'incremento di capacità per Vector. La classe Vector fornisce anche setSize(int newSize) e ArrayList, per le regolazioni manuali della dimensione minima del vettore e per ridimensionare il vettore da soli.

La classe ArrayList è molto simile:

  

Ogni <=> istanza ha una capacità. La capacità è la dimensione dell'array utilizzato per memorizzare gli elementi nell'elenco. È sempre almeno grande quanto la dimensione dell'elenco. Man mano che gli elementi vengono aggiunti a una ArrayList, la sua capacità aumenta automaticamente. I dettagli della politica di crescita non sono specificati oltre al fatto che l'aggiunta di un elemento ha un costo temporale ammortizzato costante.

     

Un'applicazione può aumentare la capacità di un'istanza <=> prima di aggiungere un gran numero di elementi utilizzando l'operazione sureCapacity. Ciò può ridurre la quantità di riallocazione incrementale.

Se stai chiedendo l'implementazione generale di un vettore, piuttosto che la scelta di aumentare le dimensioni e di quanto è un compromesso. In genere, i vettori sono supportati da array. Le matrici hanno dimensioni fisse. Ridimensionare un vettore perché è pieno significa che devi copiare tutti gli elementi di un array in un nuovo array più grande. Se si rende il nuovo array troppo grande, è stata allocata memoria che non verrà mai utilizzata. Se è troppo piccolo, potrebbe essere necessario troppo tempo per copiare gli elementi dal vecchio array nel nuovo, più grande array, un'operazione che non si desidera eseguire molto spesso.

Answer 6

Personalmente, penso che sia una scelta arbitraria. Potremmo usare la base e anziché la base 2 (invece di raddoppiare la dimensione multipla di (1 + e).)

Se stai per aggiungere grandi quantità di variabili al vettore, allora sarebbe vantaggioso avere una base alta (per ridurre la quantità di copia che farai.) D'altro canto, se devi archiviare solo pochi membri su avg, quindi una base bassa andrà bene e ridurrà la quantità di spese generali, accelerando così le cose.

Base 2 è un compromesso.

Answer 7

Non vi è alcun motivo di prestazioni per il raddoppio rispetto al triplo o al quadruplo poiché tutti hanno gli stessi grandi profili di prestazioni O. Tuttavia, in termini assoluti, il raddoppio tenderà ad essere più efficiente nello spazio nello scenario normale.