Quante copie sono necessarie per ingrandire un array?

Question

Quante copie sono necessarie per ingrandire un array?

#1 da (5 voti)
#2 da (2 voti)
#3 da (0 voti)

8

Sto leggendo un'analisi su array dinamici (dal manuale dell'algoritmo di Skiena).
Cioè quando abbiamo una struttura di array e ogni volta che siamo fuori dallo spazio assegniamo una nuova matrice di dimensioni doppie rispetto all'originale.

Descrive gli sprechi che si verificano quando l'array deve essere ridimensionato.
Dice che (n / 2) da +1 a n verrà spostato al massimo una volta o non lo sarà affatto. Questo è chiaro.
Quindi descrivendo che metà degli elementi si muove una volta, un quarto degli elementi due volte e così via, il il numero totale di movimenti M è dato da:

Questo mi sembra che aggiunga più copie di quanto realmente avvenga.

per es.

se abbiamo il seguente:

array of 1 element
+--+
|a |
+--+

double the array (2 elements)  
+--++--+  
|a ||b |  
+--++--+  

double the array (4 elements)  
+--++--++--++--+  
|a ||b ||c ||c |  
+--++--++--++--+  

double the array (8 elements)  
+--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x |  
+--++--++--++--++--++--++--++--+    

double the array (16 elements)  
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+    
|a ||b ||c ||c ||x ||x ||x ||x ||  ||  ||  ||  ||  ||  ||  ||  |   
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+

Abbiamo l'elemento x copiato 4 volte, l'elemento c copiato 4 volte, l'elemento b copiato 4 volte e un elemento copiato 5 volte quindi il totale è 4 + 4 + 4 + 5 = 17 copie / movimenti.

Ma secondo la formula dovremmo avere 1 * (16/2) + 2 * (16/4) + 3 * (16/8) + 4 * (16/16) = 8 + 8 + 6 + 4 = 26 copie di elementi per l'ingrandimento dell'array a 16 elementi.

Questo è un errore o lo scopo della formula è fornire un'approssimazione approssimativa del limite superiore? O sono incomprensibile qualcosa qui?

algorithms complexity

posta user10326 11.11.2011 - 07:29

fonte

3 risposte

Leggi altre domande sui tag algorithms complexity

Quali sono le migliori pratiche per popolare e utilizzare un database di test? Quali sono alcuni buoni criteri per l'utilizzo di Tracer Bullets?

score 5 · Answer 1

In primo luogo, b viene spostato 3 volte e a viene spostato 4 volte, per un totale di 4 + 4 + 3 + 4 = 15 copie.

Penso che la formula dovrebbe essere compilata con n = 8: 1 * (8/2) (x è copiato una volta) + 2 * (8/4) (c è copiato due volte) + 3 * (8/8 ) (b viene copiato tre volte) = 11. In altre parole, la formula sembra mancare un termine "+ log ₂ n + 1" oltre alla somma stessa.

Quello che mi sembra un modo molto più naturale per contare il numero di mosse è contare il numero di elementi spostati per copia:

sum da i = 1 a i = ceiling (log ₂ n): 2 ^i-1

Nel tuo caso, n = 16, quindi ceiling (log ₂ 16) = 4 e la somma sopra è: 2 ⁰ +2 ¹ +2 ² +2 ³ = 1 + 2 + 4 + 8 = 15.

Vedrò se riesco a trovare il manuale dell'algoritmo di Skiena per vedere se ho capito bene.

Aggiornamento: ho trovato la parte nel manuale dell'algoritmo di Skiena. Sembra che ci sia un termine mancante nella somma che usa lì. Tuttavia, la conclusione è corretta:

M = somma da i = 1 a i = soffitto (log ₂ n): 2 ^i-1 = somma da i = 0 a i = soffitto (log ₂ n) - 1: 2 ⁱ = 2 ^{ceiling (log ₂ n) - 1 + 1} < = (2 ^{log ₂ n + 1 - 1 + 1}) = 2 * n

(Vorrei poter formattare queste formule in un modo più carino per te)

Il punto principale di questo paragrafo sembra essere quello di dare un esempio dell'analisi ammortizzata . Metodi come il potenziale metodo farebbero un argomento migliore (meno ad hoc) perché gli array dinamici funzionano molto bene, ma questo metodo è un po 'avanzato.

Se sei convinto che ci sia un errore in questo libro, potresti prendere in considerazione di contattare l'autore a riguardo (in modo costruttivo, ovviamente - il libro ha un sacco di pagine, ed è difficile ottenere ogni cosa corretta, e c'è sempre una possibilità che il libro sia giusto e che entrambi abbiamo sbagliato). Non ho trovato questo particolare sull'errata.

score 2 · Answer 2

Ai livelli di conteggio dei blocchi inferiori, è improbabile che si verifichi effettivamente un'allocazione di memoria. I gestori di memoria trattano blocchi di memoria e allocano di routine blocchi di memoria più grandi rispetto alla richiesta di allocazione richiesta in modo accidentale.

Allo stesso modo, l'implementazione di una classe array è probabile che arrotonda le allocazioni per consentire alcuni elementi aggiuntivi.

EDIT:

In caso di ulteriore riflessione, è improbabile che le copie effettive si presentino quando le descrivi. I processori di solito hanno un comando di copia di blocco e userebbero una singola istruzione di assrambler per copiare i dati dell'array come un singolo blocco di memoria nel nuovo indirizzo.

score 0 · Answer 3

Credo che la formula indicata nel libro sia semplicemente errata. Il moltiplicatore i deve essere eliminato dalla formula per risolverlo.

Prendiamo l'esempio del richiedente e chiamiamo l'array di 1 elemento array-1, l'array di 2 elementi - array-2 , l'array di 4 elementi - array-4 , e così via.

Quindi, di conseguenza al libro, per questo particolare esempio il numero di copie è governato dalla seguente formula:


M = 1⋅8 + 2⋅4 + 3⋅2 + 4⋅1

Il primo termine della somma 1⋅8 è per copiare array-8's elementi in array-16 .

Copiamo due volte array-4's items (a, b, c, c) . Da array-4 a array-8 . E poi quando copi array-8's elementi in array-16 copiamo (a, b, c, c) elementi per la seconda volta. Di conseguenza al libro, da qui il secondo termine: 2⋅4 .

Ma ora noti che il termine 1⋅8 tiene già conto della copia di (a, b, c, c) elementi da array-8 a array-16 . Di conseguenza, il termine 2⋅4 non deve includere il moltiplicatore 2 .

La stessa logica si applica a tutti gli altri termini. E quindi moltiplicare per i è un errore.