Trade-offs

El precio de duplicar

Duplicar ahorra copias, pero reserva memoria que todavía no usas. Justo después de crecer de 512 a 1024, la mitad del bloque está vacía. Algunas bibliotecas usan factor 1,5: un poco más de copias, menos memoria sin usar.

Hay un segundo precio: la latencia. Una inserción entre muchas tarda mucho más que las demás.

Un sistema de audio agrega muestras a un array dinámico y no tolera que una sola inserción tarde mucho, aunque la media sea buena. ¿Qué haces?Dejar la regla de duplicar: el O(1) amortizado garantiza que cada inserción es rápida siempreReservar de antemano la capacidad necesaria, para que nunca crezca durante la reproducciónCambiar el factor de 2 a 1,5, lo que acorta a la mitad la pausa de cada crecimiento que ocurraCrecer de uno en uno, para que cada crecimiento copie pocos valores y ninguna pausa dure mucho