Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am reading an analysis on dynamic arrays (from the Skiena's algorithm manual).
I.e. when we have an array structure and each time we are out of space we allocate a new array of double the size of the original.

It describes the waste that occurs when the array has to be resized.
It says that (n/2)+1 through n will be moved at most once or not at all. This is clear.
Then by describing that half the elements move once, a quarter of the elements twice, and so on, the total number of movements M is given by:

enter image description here

This seems to me that it adds more copies than actually happen.

E.g.

if we have the following:

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

We have the x element copied 4 times, c element copied 4 times, b element copied 4 times and a element copied 5 times so total is 4+4+4+5 = 17 copies/movements.

But according to formula we should have 1*(16/2)+2*(16/4)+3*(16/8)+4*(16/16)= 8+8+6+4=26 copies of elements for the enlargement of the array to 16 elements.

Is this some mistake or the aim of the formula is to provide a rough upper limit approximation? Or am I missunderstanding something here?

share|improve this question
    
Another factor: in the real-world, the empty allocated elements would be zeroed out (in a high-level language like Java or C#). This entails a write (but not a read), that seems to cost half as much as a copy. –  dbkk Nov 11 '11 at 7:50
1  
Your sums aren't correct; b is copied 3 times, each c twice, and each x once. 15 copies. –  Donal Fellows Nov 11 '11 at 10:32

3 Answers 3

Firstly, b is moved 3 times and a is moved 4 times, which gives a total of 4 + 4 + 3 + 4 = 15 copies.

I think the formula should be filled in with n=8: 1*(8/2) (x is copied once) + 2*(8/4) (c is copied twice) + 3*(8/8) (b is copied thrice) = 11. In other words, the formula seems to be missing a "+ log2 n + 1" term in addition to the sum itself.

What would seem to me to be a much more natural way to count the number of moves is to count the number of moved elements per copy:

sum from i = 1 to i = ceiling(log2 n): 2i-1

In your case, n = 16, so ceiling(log2 16) = 4 and the sum above is: 20+21+22+23 = 1 + 2 + 4 + 8 = 15.

I'll see if I can find this Skiena's algorithm manual to see if I got it correct.

Update: I found the part in Skiena's algorithm manual. It does seem like there there is a term missing in the sum he uses there. However, the conclusion is correct:

M = sum from i = 1 to i = ceiling(log2 n): 2i-1 = sum from i = 0 to i = ceiling(log2 n) - 1: 2i = 2ceiling(log2 n) - 1 + 1 <= (2log2 n + 1 - 1 + 1) = 2 * n

(I wish I could format these formulas in a nicer way for you)

The main point of this paragraph seems to be to give an example of amortized analysis. Methods such as the potential method would make a better (less ad hoc) argument why dynamic arrays perform very well, but this method is somewhat advanced.

If you are convinced there is an error in this book, you could consider contacting the author about this (in a constructive way of course - the book has a lot of pages, and it's hard to get every last thing correct, and there's always a chance that the book is right and we both got it wrong). I haven't found this particular one on the errata.

share|improve this answer
    
I formatted the formulas a bit :-) –  Péter Török Nov 11 '11 at 11:28
    
Thank you, it looks much nicer now - I'm used to LaTeX formatting, and I don't think that's possible on Programmers.SE. –  Alex ten Brink Nov 11 '11 at 11:39
    
@Alex:+1 thank you for this.I was wondering why do you think that in the OP the n should be 8 and not 16.I didn't get that. –  user10326 Nov 11 '11 at 14:54
    
Because then the i*n/2^i terms make sense: if i = 1, then you talk about 1 * n/2, which would correspond to half the input being copied once. In his example, there are four x positions that get copied once, and 8/2=4, so n=8 would make more sense. If n=16, then 16/2=8 elements would supposedly be copied once, which simply doesn't match the example. –  Alex ten Brink Nov 11 '11 at 16:26

At the lower block count levels, its unlikely that a memory allocation actually occurs. Memory managers deal in blocks of memory and routinely allocate larger blocks of memory than the allocation request acutually asked for.

Likewise, the implementation of an array class is likely to round up allocations to allow for a few additional elements.

EDIT:

On further reflection, the actual copies are unlikely to occur as you describe them either. Processors usually have a block copy command and would use a single assmbler instruction to copy the array data as a single block of memory to the new address.

share|improve this answer
1  
Sorry, how is this related to my question? –  user10326 Nov 11 '11 at 8:38
    
Well if an allocation does not need to occur, then there is no need to copy the array elements to the new memory space. –  Ptolemy Nov 11 '11 at 8:40
1  
But I am asking about the formula. –  user10326 Nov 11 '11 at 8:59
    
Fair enough, its a mathematical question and I am giving programming answers on a programming site... ;) –  Ptolemy Nov 11 '11 at 9:17

I believe the formula given in the book is simply incorrect. The i multiplier has to be dropped from the formula to fix it.

Let's take the asker's example and call the array of 1 element array-1, the array of 2 elements -- array-2, the array of 4 elements -- array-4, and so on.

So, accordingly to the book, for this particular example the number of copyings is governed by the following formula:


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

The first term of the sum 1⋅8 is for copying array-8's items into array-16.

We copy the array-4's items (a, b, c, c) twice. Once from the array-4 to array-8. And then when copying array-8's items to array-16 we copy (a, b, c, c) items for the second time. Accordingly to the book, hence the second term: 2⋅4.

But now notice that the 1⋅8 term already takes into account copying of (a, b, c, c) items from array-8 to array-16. Consequently the 2⋅4 term must not include the 2 multiplier.

The same logic applies to all the other terms. And so multiplying by i is a mistake.

share|improve this answer
    
would you mind explaining more on what it does and why do you recommend it as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange –  gnat Jun 4 at 9:22
    
Sure. I will copy my answer from cs.stackexchange. The problem is though that programmers.stackexchange doesn't allow proper math formulas formatting. –  Nik Jun 4 at 9:24
    
per my reading, the formulas in your answer at CS can be reasonably approximated using code formatting with backticks: M=1⋅8+2⋅4+3⋅2+4⋅1 etc –  gnat Jun 4 at 9:26
1  
Thanks, followed your suggesting. –  Nik Jun 4 at 9:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.