I was wondering how does one decide the resizing factor by which dynamic array resizes ? On wikipedia and else where I have always seen the number of elements being increased by a factor of 2? Why 2? Why not 3? how does one decide this factor ? IF it is language dependent I would like to know this for Java.
A:
Actually in Java's ArrayList the formula to calculate the new capacity after a resize is:
newCapacity = (oldCapacity * 3)/2 + 1;
This means roughtly a 1.5 factor.
About the reason for this number I don't know but I hope someone has done a statistical analisys and found this is a good compromise between space and computational overhead.
Andrea Polci
2010-03-30 14:06:49
@Andrea: there are some nice graphs even on SO: http://stackoverflow.com/questions/1424826/why-is-vector-array-doubled/1426065#1426065
andras
2010-04-01 20:50:23
+2
A:
Quoting from Wikipedia:
As n elements are inserted, the capacities form a geometric progression. Expanding the array by any constant proportion ensures that inserting n elements takes O(n) time overall, meaning that each insertion takes amortized constant time. The value of this proportion a leads to a time-space tradeoff: the average time per insertion operation is about a/(a−1), while the number of wasted cells is bounded above by (a−1)n. The choice of a depends on the library or application: a=3/21 and a=2[citation needed] is commonly-used.
Apparently it seems that it is a good compromise between CPU time and memory wasting. I guess the "best" value depends on what your application does.
ereOn
2010-03-30 14:07:50
The point on amortized time is key. Google "amortized analysis" and find things like http://www.cs.cornell.edu/Courses/cs312/2008sp/lectures/lec20.html
Matt
2010-04-01 21:05:42
A:
Would you waste more space than you actually use?
If not, the factor should be less than or equal to 2.
If you want it to be an integer so it is simple to work with, there is only one choice.
andras
2010-04-01 20:48:58