Come for the quick hacks, stay for the epiphanies. | |
PerlMonks |
Re: Re: Re: Re: Re: Re: Slowness when inserting into pre-extended arrayby tilly (Archbishop) |
on Jul 20, 2003 at 16:54 UTC ( [id://276061]=note: print w/replies, xml ) | Need Help?? |
You're right, I just glanced at av.c and it isn't a power of 2. It is 20%. Perhaps I hadn't read it carefully enough originally? (In which case someone might look at my unshift speedup since that does go by powers of 2.) Or perhaps I am mixing it up with the fact that many things I have looked at (hash resizing, some malloc arrangements) like working with powers of 2? However 20% per time is still a geometric arrangement and therefore is a constant amortized cost per new element added. It is just a higher amortized cost. Let's calculate it in theory. Suppose that we have been adding one element at a time with push, and we have just had to recopy the array. Suppose that our size is now N. How many recopyings have we needed (ignoring the rounding because we only move an integer number)? Well N elements got moved this time. When we moved we wind up with 6/5'ths as much space, so 5/6'ths of our elements got moved on the previous time we had to move. And 5/6'ths of 5/6'ths of them got moved the round before that. etc. This is just a geometric series with r=5/6. The well-known trick for calculating those is to multiply and divide by 1-r: In our case r is 5/6, so 1-r is 1/6 and 1/(1-r) is 6. Therefore, worst case, the amount of recopying that we would have to do averages out to 6 times per element in the array. Best case, just before we have to recopy is 5 times. So growing an array incrementally we have to recopy each element 5-6 times. Now how do theory and practice work out? Well consider the following silly program to calculate the exact number of resizes after building up an array to any size, taking into account rounding etc: and the output from this is: So you see, as long as Perl can continue allocating more and more space as it wants, the amount of recopying work needed scales linearly with the size of the array.
In Section
Seekers of Perl Wisdom
|
|