c++ - vectors - Análisis amortizado de std:: inserción de vectores

vector stl c++ reference

Question

¿Cómo hacemos el análisis de inserción en la parte posterior (push_back) en un std :: vector? Su tiempo amortizado es O (1) por inserción. En particular, en un video en el canal 9 de Stephan T Lavavej y en este (17:42 en adelante) dice que para un rendimiento óptimo, la implementación de este método por parte de Microsoft aumenta la capacidad del vector en alrededor de 1.5.

¿Cómo se determina esta constante?

Answer 1

Puedes hacer los cálculos para tratar de averiguar cómo funciona este tipo de cosas.

Un método popular para trabajar con análisis asintótico es el método de los banqueros. Lo que hace es marcar todas sus operaciones con un costo adicional, "guardándolo" para luego pagar una operación costosa.

Hagamos algunas suposiciones de volcado para simplificar las matemáticas:

• Escribir en una matriz cuesta 1 . (Lo mismo para insertar y mover entre matrices)
• La asignación de una matriz más grande es gratuita.

Y nuestro algoritmo se ve como:

function insert(x){
    if n_elements >= maximum array size:
         move all elements to a new array that
         is K times larger than the current size
    add x to array
    n_elements += 1

Obviamente, el "peor caso" ocurre cuando tenemos que mover los elementos a la nueva matriz. Intentemos amortizar esto agregando un margen de ganancia constante de d al costo de inserción, lo que da un total de (1 + d) por operación.

Justo después de cambiar el tamaño de una matriz, hemos llenado (1 / K) y no hemos ahorrado dinero. Para cuando llenemos la matriz, podemos estar seguros de tener al menos d * (1 - 1/K) * N guardado. Dado que este dinero debe poder pagar por todos los elementos N que se mueven, podemos averiguar una relación entre K y d :

d*(1 - 1/K)*N = N
d*(K-1)/K = 1
d = K/(K-1)

Una mesa útil:

k    d     1+d(total insertion cost)
1.0  inf   inf
1.1  11.0  12.0
1.5  3.0   4.0
2.0  2.0   3.0
3.0  1.5   2.5
4.0  1.3   2.3
inf  1.0   2.0

De este modo, puede obtener una idea matemática aproximada de cómo funciona la compensación de tiempo / memoria para este problema. Hay algunas advertencias, por supuesto: no fui más allá de la reducción de la matriz cuando tiene menos elementos, esto solo cubre el peor de los casos en que nunca se eliminaron los elementos y no se tuvieron en cuenta los costos de tiempo de asignación de memoria adicional.

Lo más probable es que hayan realizado un montón de pruebas experimentales para resolver esto, aunque al final la mayoría de lo que escribí es irrelevante.

Answer 2

Suponiendo que te refieres a push_back y no a la inserción, creo que la parte importante es la multiplicación por alguna constante (en lugar de agarrar N más elementos cada vez) y mientras lo hagas, obtendrás tiempo constante amortizado. Cambiar el factor cambia el caso promedio y el desempeño del peor caso.

Concretamente: si su factor constante es demasiado grande, tendrá un buen rendimiento promedio de las carcasas, pero el peor será el peor de las mayúsculas, especialmente a medida que las matrices aumentan de tamaño. Por ejemplo, imagina duplicar (2x) un vector de tamaño 10000 solo porque tienes el elemento 10001th empujado. EDITAR: Como Michael Burr señaló de manera indirecta, el costo real aquí es probablemente que crecerá su memoria mucho más grande de lo que necesita. Me gustaría agregar a esto que hay problemas de caché que afectan la velocidad si su factor es demasiado grande. Basta con decir que hay costos reales (memoria y cómputo) si creces mucho más de lo que necesitas.

Sin embargo, si su factor constante es demasiado pequeño, diga (1.1x) entonces tendrá un buen desempeño en el peor de los casos, pero un mal desempeño promedio, porque tendrá que incurrir en el costo de la reasignación demasiadas veces.

También, vea la respuesta de Jon Skeet a una pregunta similar anteriormente. (Gracias @Bo Persson)

Un poco más sobre el análisis: Digamos que tienes n elementos que estás rechazando y un factor de multiplicación de M Luego, el número de reasignaciones será aproximadamente la base de registro M de n ( log_M(n) ). Y la i reasignación tendrá un costo proporcional a M^i ( M a la i th potencia). Entonces, el tiempo total de todos los rechazos será M^1 + M^2 + ... M^(log_M(n)) . El número de rechazos es n , y así obtiene esta serie (que es una serie geométrica y se reduce a aproximadamente (nM)/(M-1) en el límite) dividida por n . Esto es aproximadamente una constante, M/(M-1) .

Para valores grandes de M , se excederá mucho y asignará mucho más de lo que necesita razonablemente (lo que mencioné anteriormente). Para valores pequeños de M (cerca de 1) esta constante M/(M-1) hace grande. Este factor afecta directamente el tiempo promedio.

Answer 3

Uhm, el análisis es realmente simple cuando estás familiarizado con los sistemas numéricos, como nuestro decimal habitual.

Por simplicidad, entonces, suponga que cada vez que se alcanza la capacidad actual, se asigna un nuevo 10x como búfer grande.

Si el búfer original tiene tamaño 1, entonces la primera reasignación copia 1 elemento, el segundo (donde ahora el búfer tiene tamaño 10) copia 10 elementos, y así sucesivamente. Entonces, con cinco reasignaciones, digamos, tiene 1 + 10 + 100 + 1000 + 10000 = 11111 copias de elementos realizadas. Multiplica eso por 9, y obtienes 99999; ahora agrega 1 y tienes 100000 = 10 ^ 5. O, en otras palabras, haciendo eso al revés, el número de copias de elementos realizadas para respaldar esas 5 reasignaciones ha sido (10 ^ 5-1) / 9.

Y el tamaño del búfer después de 5 reasignaciones, 5 multiplicaciones por 10, es 10 ^ 5. Que es aproximadamente un factor de 9 más grande que el número de operaciones de copia de elementos. Lo que significa que el tiempo dedicado a la copia es aproximadamente lineal en el tamaño del búfer resultante.

Con la base 2 en lugar de 10 obtienes (2 ^ 5-1) / 1 = 2 ^ 5-1.

Y así sucesivamente para otras bases (o factores para aumentar el tamaño del búfer).

Saludos y hth.