¿Por qué la retroceso en los vectores de C ++ se amortiza constantemente?

Estoy aprendiendo C ++ y noté que el tiempo de ejecución de la función push_back para vectores es constante "amortizado". La documentación señala además que "si ocurre una reasignación, la reasignación es en sí misma lineal en todo el tamaño".

¿No debería esto significar que la función push_back es , donde es la longitud del vector? Después de todo, estamos interesados ​​en el análisis del peor de los casos, ¿verdad?$O(n)$$n$

Creo que, crucialmente, no entiendo cómo el adjetivo "amortizado" cambia el tiempo de ejecución.

La palabra importante aquí es "amortizado". El análisis amortizado es una técnica de análisis que examina una secuencia de operaciones. Si toda la secuencia se ejecuta en tiempo , entonces cada operación en la secuencia se ejecuta en . La idea es que si bien algunas operaciones en la secuencia pueden ser costosas, no pueden suceder con la frecuencia suficiente para pesar el programa. Es importante tener en cuenta que esto es diferente del análisis de casos promedio sobre alguna distribución de entrada o análisis aleatorio. El análisis amortizado estableció el peor de los casos para el rendimiento de un algoritmo independientemente de las entradas. Se usa más comúnmente para analizar estructuras de datos, que tienen un estado persistente en todo el programa.T ( n ) T ( n ) /$n$$T(n)$$T(n)/n$

Uno de los ejemplos más comunes dados es el análisis de una pila con operaciones multipunto que muestran elementos. Un análisis ingenuo de multipop diría que, en el peor de los casos, multipop debe tomar tiempo, ya que podría tener que extraer todos los elementos de la pila. Sin embargo, si observa una secuencia de operaciones, notará que la cantidad de pops no puede exceder la cantidad de empujes. Por lo tanto, en cualquier secuencia de operaciones, el número de pops no puede exceder de , por lo que el multipunto se ejecuta en tiempo amortizado , aunque ocasionalmente una sola llamada puede tomar más tiempo.O ( n ) n O ( n ) O ( 1 $k$$O(n)$$n$$O(n)$$O(1)$

Ahora, ¿cómo se relaciona esto con los vectores C ++? Los vectores se implementan con matrices, por lo que para aumentar el tamaño de un vector debe reasignar la memoria y copiar toda la matriz. Obviamente no quisiéramos hacer esto muy a menudo. Entonces, si realiza una operación push_back y el vector necesita asignar más espacio, aumentará el tamaño en un factor . Ahora, esto requiere más memoria, que no puede usar en su totalidad, pero las siguientes operaciones push_back se ejecutan en tiempo constante.$m$

Ahora, si hacemos el análisis amortizado de la operación push_back (que encontré aquí ), encontraremos que se ejecuta en tiempo amortizado constante. Suponga que tiene elementos y su factor de multiplicación es . Entonces el número de reubicaciones es aproximadamente . La reasignación ésima costará proporcionalmente a , aproximadamente el tamaño de la matriz actual. Por lo tanto, el tiempo total para retroceder es , ya que es una serie geométrica. Divida esto entre operaciones y obtenemos que cada operación tomam log m ( n ) i m i n ∑ log m ( n ) i = 1 m i ≈ n $n$$m$$\log_m(n)$$i$$m^i$$n$ n$\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$$n$ m1m$\frac{m}{m-1}$, una constante. Por último, debes tener cuidado al elegir tu factor . Si está demasiado cerca de entonces esta constante se vuelve demasiado grande para aplicaciones prácticas, pero si es demasiado grande, digamos 2, entonces comienza a desperdiciar mucha memoria. La tasa de crecimiento ideal varía según la aplicación, pero creo que algunas implementaciones usan .$m$$1$$m$$1.5$

Aunque @Marc ha realizado (lo que creo que es) un excelente análisis, algunas personas podrían preferir considerar las cosas desde un ángulo ligeramente diferente.

Una es considerar una forma ligeramente diferente de hacer una reasignación. En lugar de copiar todos los elementos del almacenamiento anterior al nuevo almacenamiento de inmediato, considere copiar solo un elemento a la vez, es decir, cada vez que realiza un push_back, agrega el nuevo elemento al nuevo espacio y copia exactamente uno existente elemento del antiguo espacio al nuevo espacio. Suponiendo un factor de crecimiento de 2, es bastante obvio que cuando el nuevo espacio está lleno, habríamos terminado de copiar todos los elementos del espacio anterior al nuevo espacio, y cada push_back ha sido exactamente un tiempo constante. En ese punto, descartaríamos el espacio anterior, asignaríamos un nuevo bloque de memoria que era el doble de ganancia y repetiríamos el proceso.

Claramente, podemos continuar esto indefinidamente (o siempre que haya memoria disponible) y cada push_back implicaría agregar un nuevo elemento y copiar un elemento antiguo.

Una implementación típica todavía tiene exactamente el mismo número de copias, pero en lugar de hacer las copias de una en una, copia todos los elementos existentes a la vez. Por un lado, tiene razón: eso significa que si observa las invocaciones individuales de push_back, algunas de ellas serán sustancialmente más lentas que otras. Sin embargo, si observamos un promedio a largo plazo, la cantidad de copia realizada por invocación de push_back permanece constante, independientemente del tamaño del vector.

Aunque es irrelevante para la complejidad computacional, creo que vale la pena señalar por qué es ventajoso hacer las cosas como lo hacen, en lugar de copiar un elemento por push_back, por lo que el tiempo por push_back permanece constante. Hay al menos tres razones para considerar.

El primero es simplemente la disponibilidad de memoria. La memoria anterior se puede liberar para otros usos solo después de que finalice la copia. Si solo copiara un elemento a la vez, el antiguo bloque de memoria permanecería asignado mucho más tiempo. De hecho, tendrías un bloque antiguo y un bloque nuevo asignados esencialmente todo el tiempo. Si opta por un factor de crecimiento menor que dos (que generalmente desea) necesitaría aún más memoria asignada todo el tiempo.

En segundo lugar, si solo copió un elemento antiguo a la vez, la indexación en la matriz sería un poco más complicada: cada operación de indexación necesitaría averiguar si el elemento en el índice dado estaba actualmente en el bloque de memoria anterior o uno nuevo. Eso no es terriblemente complejo de ninguna manera, pero para una operación elemental como indexar en una matriz, casi cualquier desaceleración podría ser significativa.

Tercero, al copiar todo de una vez, aprovecha mucho mejor el almacenamiento en caché. Al copiar todo de una vez, puede esperar que tanto el origen como el destino estén en la memoria caché en la mayoría de los casos, por lo que el costo de una pérdida de memoria caché se amortiza sobre el número de elementos que caben en una línea de memoria caché. Si copia un elemento a la vez, es posible que pierda memoria caché fácilmente por cada elemento que copie. Eso solo cambia el factor constante, no la complejidad, pero aún puede ser bastante significativo: para una máquina típica, puede esperar fácilmente un factor de 10 a 20.

Probablemente también valga la pena considerar la otra dirección por un momento: si estaba diseñando un sistema con requisitos en tiempo real, podría tener sentido copiar solo un elemento a la vez en lugar de todos a la vez. Aunque la velocidad general podría (o no) ser menor, aún tendría un límite superior duro en el tiempo necesario para una sola ejecución de push_back, suponiendo que tuviera un asignador en tiempo real (aunque, por supuesto, muchos en tiempo real los sistemas simplemente prohíben la asignación dinámica de memoria, al menos en porciones con requisitos en tiempo real).