8
$\begingroup$

By dynamic array, I mean an array that when it becomes full we replace it with a new array having greater capacity than the previous array.

I read in a textbook that doubling the size of the array is the most efficient resizing. I want to know if this is in fact demonstrably true and not just a matter of personal preference.

We will want to minimize the amount of resizing events, because each such event requires O(n) time where n is the number of elements in the list.

We also should be careful not to make the list too big because it might be a waste of memory.

Why does the author of my textbook say that 2 * array.length() is the magic number?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You should credit the textbook. $\endgroup$
    – Yuval Filmus
    Commented Apr 22, 2017 at 15:08

2 Answers 2

Reset to default
4
$\begingroup$

Consider a model in which elements are only added, one at a time, and once an array is full, it is increased in size by a factor of $C$. Suppose also that resizing an array of size $x$ costs $Cx$. Adding $N = C^n$ elements (the worst case in terms of resizing cost per element) has cost $C(1+C+C^2+\cdots+C^n) \approx \frac{C^2}{C-1} N$. The amortized cost of adding an element is thus $f(C) = \frac{C^2}{C-1}$. The derivative of this function is $$ f'(C) = \frac{2C(C-1)-C^2}{(C-1)^2} = \frac{C(2-C)}{(C-1)^2}, $$ which vanishes at $C=2$. It is not hard to check that this is a minimum of $f(C)$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This is interesting, but I don't think it is the right answer. Why resizing an array of size $x$ costs $Cx$? It is more like $x$ if you have to copy over; or $1$ if you have enough space without copying. Of course, in a more realistic setting, there is also cost to find the right memory block and to return the old block, which differs greatly between implementations. How to assign cost directly determines the derivative. You just chose a cost such that 2 happens to be the minima. $\endgroup$
    – user172818
    Commented Apr 22, 2017 at 14:03
  • 1
    $\begingroup$ You are barking at the wrong tree. People often assume that whatever is written in textbooks must be the objective truth. In fact, this is not always the case. It may be that if you change the cost function, the optimal value of $C$ changes. We don't know what cost function the textbook used, since they don't bother to tell us. My cost function is just a guess, and with respect to this guess, $C=2$ is optimal. If you use the cost function $x$, then it is best to take $C$ as large as possible. The cost function $x + \rho C x$ for $\rho \in (0,1)$ will have an optimum $C$ depending on $\rho$. $\endgroup$
    – Yuval Filmus
    Commented Apr 22, 2017 at 14:08
  • $\begingroup$ I think that analysis might be a bit dodgy, because you assume that the array will be exactly filled. I think N = $C^N + 1$ would be a worse case. $\endgroup$
    – gnasher729
    Commented Apr 22, 2017 at 18:14
  • $\begingroup$ The worst case is just after the array is extended, which is also when it is exactly filled. My semantics are different than yours – I extend the array once it gets filled, whereas you extend it only when you are adding an element to a full array. $\endgroup$
    – Yuval Filmus
    Commented Apr 22, 2017 at 22:08
3
$\begingroup$

Let $C$ be the growth factor. In practice, we don't use small $C$ because reallocation would be too frequent; we don't use large $C$ because we would waste $(C−1)/C$ of space in the worse case or $(C−1)/(2C)$ in average. I don't think there is an accurate model to compute $C$ because it is hard to precisely weight speed vs space waste. $C=2$ is something we feel comfortable most of time. It is also fast to compute (a bit shift) and may align well with typical page size which is almost always power-of-2.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In other words, in your view it is arbitrary rather than "the most efficient resizing". $\endgroup$
    – Yuval Filmus
    Commented Apr 22, 2017 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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