Timeline for Why is it most efficient to resize a dynamic array to 2 * array.length()?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2017 at 22:08 | comment | added | Yuval Filmus | 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. | |
| Apr 22, 2017 at 18:14 | comment | added | gnasher729 | 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. | |
| Apr 22, 2017 at 14:08 | comment | added | Yuval Filmus | 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$. | |
| Apr 22, 2017 at 14:03 | comment | added | user172818 | 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. | |
| Apr 22, 2017 at 6:59 | history | answered | Yuval Filmus | CC BY-SA 3.0 |