Saltar al contenido principal

Realocando un Arreglo

Supongamos que vamos leyendo números de un stream y almacenándolos en un arreglo. Como no sabemos cuántos números leeremos, no podemos alocar la memoria definitiva que el arreglo necesitará. Debemos, en cambio, ir realocando áreas de memoria cada vez mayores para el arreglo cada vez que éste se va llenando. Al realocar un arreglo que contiene nn elementos, debemos copiar sus nn elementos al área nueva de memoria. Consideremos como costo el número total de escrituras a memoria que se requiere a lo largo del proceso.

Si cada vez que se nos llena el arreglo de tamaño nn lo realocamos a tamaño n+1n+1, usaremos el mínimo posible de memoria, pero el costo total será Θ(n2)\Theta(n^2). Lo que se usa es partir con un arreglo de tamaño pequeño (digamos de 1 elemento, para simplificar) y duplicar su tamaño cada vez que se llena. Esto garantiza que en total usamos a lo sumo el doble de la memoria necesaria. Lo que no está claro es cuánto es el costo de insertar un nuevo elemento en el arreglo si realocamos de esta manera.

En términos de peor caso, esta política parece tan mala como la cuadrática: como hay inserciones que nos requieren realocar el arreglo, el costo de peor caso de una inserción son n+1n+1 escrituras, donde nn es el número de inserciones anteriores (o el tamaño del arreglo). Necesitamos un análisis amortizado para reflejar el hecho de que, con esta segunda política, estas inserciones tan costosas ocurren muy pocas veces e impactan poco en el costo total.

Análisis global​

Podemos notar que los valores de nn en los que, al insertar un nuevo elemento, debemos expandir el arreglo (es decir, duplicarlo en tamaño) son las potencias de 2: 1, 2, 4, …\ldots, 2k2^k. El peor caso es que n=2k+1n=2^k+1, de modo que no tengamos operaciones baratas después de la última expansión. Además de las nn escrituras realizadas para insertar los elementos en el arreglo, hemos copiado 1+2+4+…+2k=2k+1−11+2+4+\ldots+2^k = 2^{k+1}-1 elementos a lo largo de todas las expansiones. El costo total es entonces 3⋅2k<3n3\cdot 2^k < 3n, y por ende el costo amortizado de una inserción es a lo más de 33 escrituras.

Contabilidad de costos​

En vez de cobrar el costo de expandir el arreglo a la operación de inserción, se lo cobraremos a los elementos que se copian, de modo que la operación misma pagará solamente 1 escritura. Cobrarle la operación a los elementos, sin embargo, también nos da un problema, porque a lo largo de todas las expansiones los primeros elementos insertados en el arreglo se copian más veces que los últimos insertados.

Haremos entonces lo siguiente: sólo les cobraremos a los elementos que se copian por primera vez. Cuando se copien n=2kn=2^k elementos, entonces, sólo los n/2n/2 de la segunda mitad pagarán la copia, pues estos elementos se están copiando por primera vez. Como alguien tiene que pagar la copia de los n/2n/2 de la primera mitad, les cobraremos doble a los de la segunda mitad. Es decir, cada elemento "nuevo" paga por su copia y por la de un elemento "viejo". Luego de copiarse una primera vez, un elemento pasa a ser viejo y a residir en la primera mitad del nuevo arreglo, por lo que no paga nunca más. Esto facilita contabilizar los costos: cada uno de los nn elementos puede pagar hasta una vez, a costo 2. Además, cada una de las nn inserciones paga 1, por escribir el elemento en el arreglo. Sumando, tenemos un costo amortizado de a lo más 33 escrituras por inserción.

--> imagen

Función potencial​

Sea ss el tamaño actual del arreglo, que tiene escritos nn elementos, de modo que n≤s<2nn \le s < 2n (excepto al comienzo, en que n=0n=0 y supondremos que partimos con un arreglo de tamaño s=1s=1). Definiremos la función potencial como ϕ=2n−s\phi = 2n-s. Al comienzo vale ϕ0=−1\phi_0 = -1, pero luego de la primera inserción siempre vale ϕn>0\phi_n > 0. Partiremos la operación de inserción en dos sub-operaciones: la "inserción elemental" y la "expansión". La inserción elemental simplemente agrega el nuevo elemento al arreglo, y sólo puede invocarse cuando hay espacio. La expansión sólo duplica el arreglo y copia los elementos actuales, y se invoca cuando no hay espacio. Así, una inserción consiste de una inserción elemental, a veces precedida de una expansión.

La inserción elemental cuesta ci=1c_i=1. Como incrementa nn, ocurre que Δϕi=2\Delta\phi_i = 2. De modo que el costo amortizado de la inserción elemental es ci^=ci+Δϕi=3\hat{c_i} = c_i + \Delta\phi_i = 3. Por otro lado, la expansión teniendo nn elementos en el arreglo cuesta ci=nc_i = n. Se realiza cuando s=ns=n y hace que ss pase a ser 2s2s. Por lo tanto, ϕi−1=2n−s\phi_{i-1} = 2n-s y ϕi=2n−2s\phi_i = 2n-2s, con lo cual Δϕi=−s=−n\Delta\phi_i = -s = -n. Sumando, tenemos que el costo amortizado de la expansión es ci^=ci+Δϕi=0\hat{c_i} = c_i + \Delta\phi_i = 0. Por lo tanto, el costo amortizado de una inserción es a lo sumo 33.