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
add comment

2 Answers

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
add comment

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
add comment

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.