Wie viele Kopien werden benötigt, um ein Array zu vergrößern?

Ich lese eine Analyse zu dynamischen Arrays (aus dem Skiena-Algorithmushandbuch).
Das heißt, wenn wir eine Array-Struktur haben und jedes Mal, wenn wir keinen Platz mehr haben, ein neues Array zuweisen, das doppelt so groß ist wie das Original.

Es beschreibt die Verschwendung, die auftritt, wenn die Größe des Arrays geändert werden muss.
Es heißt, dass (n / 2) +1 bis n höchstens einmal oder gar nicht verschoben werden. Das ist klar.
Wenn man dann beschreibt, dass sich die Hälfte der Elemente einmal, ein Viertel der Elemente zweimal usw. bewegt, ergibt sich die Gesamtzahl der Bewegungen M aus:

Dies scheint mir, dass es mehr Kopien hinzufügt, als tatsächlich passieren.

Z.B

wenn wir folgendes haben:

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 ||  ||  ||  ||  ||  ||  ||  ||  |   
+--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+   

Wir haben das x-Element 4-mal kopiert, das c-Element 4-mal kopiert, das b-Element 4-mal kopiert und ein Element 5-mal kopiert, sodass insgesamt 4 + 4 + 4 + 5 = 17 Kopien / Bewegungen sind.

Aber gemäß der Formel sollten wir 1 * (16/2) + 2 * (16/4) + 3 * (16/8) + 4 * (16/16) = 8 + 8 + 6 + 4 = 26 Kopien von haben Elemente zur Vergrößerung des Arrays auf 16 Elemente.

Ist dies ein Fehler oder besteht das Ziel der Formel darin, eine grobe Annäherung an die Obergrenze bereitzustellen? Oder verstehe ich hier etwas falsch?

Zunächst wird b dreimal und a viermal verschoben, was insgesamt 4 + 4 + 3 + 4 = 15 Kopien ergibt.

Ich denke, die Formel sollte mit n = 8: 1 * (8/2) (x wird einmal kopiert) + 2 * (8/4) (c wird zweimal kopiert) + 3 * (8/8) (b) ausgefüllt werden wird dreimal kopiert) = 11. Mit anderen Worten, der Formel scheint zusätzlich zur Summe selbst ein Term "+ log ₂ n + 1" zu fehlen .

Was mir viel natürlicher erscheint, um die Anzahl der Züge zu zählen, ist die Zählung der Anzahl der verschobenen Elemente pro Kopie:

Summe von i = 1 bis i = Decke (log ₂ n): 2 ^i-1

In Ihrem Fall n = 16, so Obergrenze (log ₂ 16) = 4 ist und die Summe oben ist: 2 ⁰ 2 ¹ 2 ² +2 ³ = 1 + 2 + 4 + 8 = 15.

Ich werde sehen, ob ich das Handbuch dieses Skiena-Algorithmus finden kann, um zu sehen, ob ich es richtig verstanden habe.

Update: Ich habe den Teil in Skienas Algorithmus-Handbuch gefunden. Es scheint, als ob in der Summe, die er dort verwendet, ein Begriff fehlt. Die Schlussfolgerung ist jedoch richtig:

M = Summe von i = 1 bis i = Decke (log ₂ n): 2 ^i-1 = Summe von i = 0 bis i = Decke (log ₂ n) - 1: 2 ⁱ = 2 ^{Decke (log ₂ n) - 1 + 1} <= (2 ^{log ₂ n + 1 - 1 + 1} ) = 2 * n

(Ich wünschte, ich könnte diese Formeln für Sie besser formatieren.)

Der Hauptpunkt dieses Absatzes scheint darin zu bestehen, ein Beispiel für eine amortisierte Analyse zu geben . Methoden wie die potenzielle Methode würden ein besseres (weniger ad hoc) Argument dafür liefern, warum dynamische Arrays sehr gut funktionieren, aber diese Methode ist etwas fortgeschritten.

Wenn Sie davon überzeugt sind, dass dieses Buch einen Fehler enthält, können Sie sich an den Autor wenden (natürlich auf konstruktive Weise - das Buch hat viele Seiten, und es ist schwierig, alles richtig zu machen, und es gibt immer einen Chance, dass das Buch richtig ist und wir beide es falsch verstanden haben). Ich habe diesen speziellen nicht in den Errata gefunden.

Bei den niedrigeren Blockanzahlstufen ist es unwahrscheinlich, dass tatsächlich eine Speicherzuordnung erfolgt. Speichermanager arbeiten mit Speicherblöcken und weisen routinemäßig größere Speicherblöcke zu, als die tatsächlich angeforderte Zuordnungsanforderung.

Ebenso wird die Implementierung einer Array-Klasse wahrscheinlich die Zuordnungen aufrunden, um einige zusätzliche Elemente zu ermöglichen.

BEARBEITEN:

Bei weiterer Überlegung ist es unwahrscheinlich, dass die tatsächlichen Kopien so auftreten, wie Sie sie beschreiben. Prozessoren haben normalerweise einen Blockkopierbefehl und verwenden einen einzelnen Assmbler-Befehl, um die Array-Daten als einzelnen Speicherblock an die neue Adresse zu kopieren.

Ich glaube, die im Buch angegebene Formel ist einfach falsch. Der iMultiplikator muss aus der Formel entfernt werden, um ihn zu beheben.

Nehmen wir das Beispiel des Fragestellers und rufen das Array von 1 Element Array-1, das Array von 2 Elementen - array-2, das Array von 4 Elementen - array-4usw. auf.

Entsprechend dem Buch wird für dieses spezielle Beispiel die Anzahl der Kopien durch die folgende Formel bestimmt:

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

Der erste Term der Summe 1⋅8dient zum Kopieren von array-8'sElementen in array-16.

Wir kopieren die array-4'sArtikel (a, b, c, c)zweimal. Einmal von der array-4bis array-8. Und dann kopieren wir beim Kopieren von array-8'sElementen zum zweiten Mal Elemente. Entsprechend dem Buch daher der zweite Begriff : .array-16(a, b, c, c)2⋅4

Beachten Sie jedoch, dass der 1⋅8Begriff bereits das Kopieren von (a, b, c, c)Elementen von array-8nach berücksichtigt array-16. Folglich 2⋅4darf der Begriff den 2Multiplikator nicht enthalten .

Die gleiche Logik gilt für alle anderen Begriffe. Das Multiplizieren mit iist also ein Fehler.