Saltar al contenido ForoHackers

Why does a dynamic array double its size? (amortized cost)

AlgoritmosEstructuras de datosIngeniería de rendimiento
#1005 · off_by_two · · Denunciar

push_back is "O(1)". But sometimes it is O(n), because the array is full and has to be copied into a bigger one. So which is it?

Take a dynamic array that doubles when full. Start at capacity 1 and push n items. The copies happen at sizes 1, 2, 4, 8, ... up to n, copying that many items each time:

1 + 2 + 4 + ... + n/2  <  n

Total copy work is below n, plus n writes for the pushes themselves: under 2n operations for n pushes. So the amortized cost per push is O(1): expensive steps are rare enough that the average stays constant.

Why double and not "add 10"? With a fixed increment k, copies happen every k pushes and cost grows linearly each time, total about n²/(2k). Quadratic. The geometric growth is what makes it work, and any factor above 1 does the job. Many implementations use 1.5 to leave room to reuse freed memory.

Puzzle: what is the worst-case cost of a single push, and when does it happen? (Answer: O(n), right after the array fills, and that is the "hiccup" some latency-sensitive code cannot afford.)

#1404 · mutex_mike · · Denunciar

That hiccup is why real-time code preallocates. In a low-latency path I want worst-case, not amortized. An average that includes a 40 ms pause is not an average anyone wants to experience.

#1405 · tabs_over_spaces_42 · · Denunciar

And in review, the cheapest improvement is often reserve(n) when you know the size up front. One allocation instead of fifteen. I have written that comment more times than I can count.

#1406 · hexdump_hermit · · Denunciar

Related: hash tables resize the same way, with the extra cost of rehashing every key. Same geometric argument, bigger constant.

#1407 · lambda_llama · · Denunciar

If you do not want any hiccup, there are persistent (immutable) structures like balanced trees, where an append costs O(log n) and never copies the whole thing. Slower on average, flatter in the worst case.

Inicia sesión o únete para responder.