Arrays y arrays dinámicos

Qué cubre este capítulo

El array es la estructura sobre la que se construye todo lo demás. Es un bloque de memoria con los elementos acomodados uno tras otro, y ese acomodo tan simple te compra el único superpoder que el resto del libro se la pasa intentando recuperar: llegar a cualquier elemento por índice en tiempo constante. El detalle es que un array crudo tiene tamaño fijo, y los programas reales no saben su tamaño de antemano. Este capítulo construye la solución — un array dinámico que crece bajo demanda — y muestra por qué hacerlo crecer al doble abarata el append aunque el crecimiento en sí sea caro. También es tu primer encuentro con el análisis amortizado, el truco contable que permite que una operación cara de vez en cuando siga contando como barata.

Un poco de historia

El array es tan viejo como las computadoras de programa almacenado. En cuanto la memoria fue direccionable, lo natural fue acomodar los valores de forma contigua y calcular la dirección del elemento i con pura aritmética — base más i por el tamaño del elemento. Esa fórmula es toda la razón por la que el acceso aleatorio es O(1), y no ha cambiado desde los años cuarenta.

El array dinámico, el que puede crecer, es más joven, y también lo es el análisis que lo justifica. La estrategia de duplicar al llenarse se volvió la implementación estándar detrás de los arrays redimensionables de todos los lenguajes importantes — el vector de C++, el ArrayList de Java, el list de Python, los slices de Go. Lo que lo hizo respetable en lugar de un simple hack fue el artículo de Robert Tarjan de 1985 que introdujo la complejidad computacional amortizada, y que nos dio el vocabulario para decir que una operación que cuesta O(n) cada tanto puede seguir siendo O(1) en promedio, y para demostrarlo en vez de nomás afirmarlo. Esa demostración es la sección de matemáticas de este capítulo.

La intuición

Imagina un bloque fijo de casillas — el almacén de respaldo — con un contador de cuántas están ocupadas. Hacer append es fácil mientras haya espacio: escribes en la siguiente casilla y subes el contador. El problema llega en el momento en que el bloque se llena. Un array fijo no puede crecer en su lugar; la memoria que sigue justo después le pertenece a alguien más. Así que asignas un bloque nuevo más grande, copias todos los elementos existentes y te cambias al nuevo. Esa copia es O(n), y no hay forma de evitarla.

La pregunta es qué tanto más grande hacer el bloque nuevo. Súmale una cantidad constante — digamos una casilla — y vas a redimensionar en cada append, copiando todo cada vez; eso es O(n) por append, un desastre. Duplica el tamaño en cambio, y los redimensionamientos se vuelven raros: después de duplicar en tamaño n, obtienes n appends más gratis antes del siguiente. Las copias caras quedan cada vez más separadas, tan rápido que su costo total, repartido entre todos los appends baratos, sale en una constante por append. Duplicar convierte una operación O(n) que haces ocasionalmente en una operación O(1) con la que puedes contar.

Complejidad: cómo escala

El acceso aleatorio es la parte fácil. El elemento i vive en un offset conocido, así que leerlo o escribirlo es $O(1)$ sin importar el tamaño — esto es lo que hace __getitem__.

El append es el interesante. La mayoría de los appends son una sola escritura, $O(1)$. Los que disparan un redimensionamiento cuestan $O(n)$. Para sacar el promedio, suma todo el copiado hecho a lo largo de n appends. Empezando con capacidad 1 y duplicando, los redimensionamientos ocurren en los tamaños 1, 2, 4, 8, y así, y cada uno copia esa cantidad de elementos:

Ese es el copiado total de los n appends juntos. Divídelo entre los n appends y el costo amortizado por append es:

El trace confirma la aritmética exactamente: 64 appends sobre un array nuevo hicieron 63 copias de elementos en total, o sea 0.984 copias por append — prácticamente una. La gráfica de abajo muestra dónde ocurre ese copiado. Cada barra es la cantidad de elementos copiados en ese append en particular; los picos son los redimensionamientos, en 1, 2, 4, 8, 16, 32, y se separan al doble cada vez aun cuando se hacen más altos. Ese hueco que se ensancha es la duplicación pagándose sola:

Insertar al inicio es la operación que hay que evitar. No hay espacio en el índice 0, así que cada elemento existente se recorre primero una casilla a la derecha — $O(n)$ cada vez, y ninguna estrategia de crecimiento ingeniosa lo arregla, porque el costo está en el recorrido, no en la asignación. Cuando necesitas inserción barata en ambos extremos, esa es otra estructura, y son los siguientes dos capítulos.

En qué es bueno y en qué no

Los arrays dinámicos son el default correcto para una secuencia a la que sobre todo le haces append e indexas. La memoria contigua no solo es cuestión de la fórmula de índice O(1); también es el acomodo más amigable posible para el hardware. El CPU trae memoria en cache lines, así que recorrer un array en orden significa que los siguientes elementos casi siempre ya están en cache. Por eso un array a menudo le gana a una estructura "más rápida" con mejor big-O sobre datos reales — la constante escondida en un cache miss es enorme, y los arrays la esquivan.

Donde duelen es en cualquier edición que no sea al final. Inserta o borra en medio o al inicio y todo lo que sigue después del corte tiene que moverse, lo cual es O(n). Un redimensionamiento además necesita brevemente el bloque viejo y el nuevo en memoria al mismo tiempo, así que el uso pico es mayor que los datos, y la capacidad extra por sobreasignación es memoria real ahí sentada sin usarse. Nada de eso pesa más que la velocidad de acceso para la mayoría de las cargas de trabajo, que es exactamente por lo que el array redimensionable es el tipo de lista integrado en casi todos los lenguajes. Busca otra cosa solo cuando tu patrón de acceso realmente gire en torno al inicio o al medio.

Los datos, o las entradas

La entrada es nomás un flujo de valores a los que hacerles append — el contenido da igual, lo que importa es la cantidad, porque este capítulo trata de cómo se comporta el costo conforme el array crece. Lo único que vale la pena observar directamente es el almacén de respaldo en sí: cómo se llena, y qué pasa en el instante en que está lleno.

Constrúyelo, una función a la vez

El append es el corazón del asunto. Revisa si el almacén está lleno; si lo está, hazlo crecer; luego escribe y sube el contador:

def append(self, value):
    """Amortized O(1): usually a single write; occasionally a resize.

    When the store is full we grow it before writing. Because we DOUBLE the
    capacity, resizes get rarer as the array grows — a resize at size n buys
    room for another n appends before the next one.
    """
    if self._n == self._cap:
        self._resize(2 * self._cap)
    self._store[self._n] = value
    self._n += 1

El paso de crecimiento es el caro que estamos tratando de volver raro — asignar un almacén más grande y copiar cada elemento vivo exactamente una vez. El contador self.copies está ahí solo para que el capítulo pueda demostrar la cota amortizada:

def _resize(self, new_cap):
    """O(n): the expensive step. Allocate a bigger store and copy every
    existing element across exactly once."""
    bigger = [None] * new_cap
    for i in range(self._n):
        bigger[i] = self._store[i]
        self.copies += 1
    self._store = bigger
    self._cap = new_cap

El acceso aleatorio es la recompensa y la razón misma de usar un array — un índice directo al almacén de respaldo, en tiempo constante:

def __getitem__(self, i):
    """O(1): a direct index into the backing store. This — random access in
    constant time — is the reason arrays exist."""
    if not 0 <= i < self._n:
        raise IndexError(i)
    return self._store[i]

def __setitem__(self, i, value):
    if not 0 <= i < self._n:
        raise IndexError(i)
    self._store[i] = value

Y la inserción al inicio es el antipatrón, incluido para que sientas el O(n) en carne propia: para hacer espacio en el índice 0, todo se recorre a la derecha:

def insert_front(self, value):
    """O(n): the array's weak spot. To open a slot at index 0 every existing
    element must shift one place to the right."""
    if self._n == self._cap:
        self._resize(2 * self._cap)
    for i in range(self._n, 0, -1):
        self._store[i] = self._store[i - 1]
    self._store[0] = value
    self._n += 1

Míralo funcionar

Aquí está el almacén de respaldo mientras se le hace append a dieciséis valores uno por uno. Las celdas en gris pizarra están ocupadas, las oscuras son capacidad vacía, y la naranja es el valor recién escrito. Cuando el almacén se llena, míralo duplicar su ancho y destellar en azul los elementos copiados — ese estallido azul es el redimensionamiento O(n). Ve paso a paso y cuenta los appends entre redimensionamientos: se duplican cada vez, 1, 2, 4, 8, que es precisamente por lo que el costo promedio se mantiene plano. Dieciséis appends caben en un almacén que se duplicó 1 → 2 → 4 → 8 → 16 y copió 15 elementos en total en el camino.

El código completo

El array dinámico entero contra el que reimplementa — cámbiate entre ellos. La pestaña desde cero es nuestro almacén de respaldo, el append que duplica, el acceso O(1) y la inserción al inicio O(n). La pestaña de librería es el list de Python: misma estructura, pero crece con una curva más suave que nuestra duplicación estricta (su factor ronda 1.125) y corre el loop de append y copia en C. Misma forma — append O(1) amortizado, inserción al inicio O(n).

"""A dynamic array built from scratch on top of a fixed-size backing store.

The backing store is a Python list used the way a real language uses a raw
array: allocated at a fixed capacity, never grown in place. When it fills, we
allocate a bigger one and copy everything across. Doubling the capacity on each
resize is what makes append cheap on average — that's the whole idea of the
chapter, and `self.copies` counts the copying so we can prove it.
"""


class DynamicArray:
    def __init__(self):
        self._cap = 1                 # capacity of the backing store
        self._n = 0                   # number of elements actually stored
        self._store = [None] * self._cap
        self.copies = 0               # total element copies caused by resizing

    # region: append
    def append(self, value):
        """Amortized O(1): usually a single write; occasionally a resize.

        When the store is full we grow it before writing. Because we DOUBLE the
        capacity, resizes get rarer as the array grows — a resize at size n buys
        room for another n appends before the next one.
        """
        if self._n == self._cap:
            self._resize(2 * self._cap)
        self._store[self._n] = value
        self._n += 1
    # endregion

    # region: resize
    def _resize(self, new_cap):
        """O(n): the expensive step. Allocate a bigger store and copy every
        existing element across exactly once."""
        bigger = [None] * new_cap
        for i in range(self._n):
            bigger[i] = self._store[i]
            self.copies += 1
        self._store = bigger
        self._cap = new_cap
    # endregion

    # region: access
    def __getitem__(self, i):
        """O(1): a direct index into the backing store. This — random access in
        constant time — is the reason arrays exist."""
        if not 0 <= i < self._n:
            raise IndexError(i)
        return self._store[i]

    def __setitem__(self, i, value):
        if not 0 <= i < self._n:
            raise IndexError(i)
        self._store[i] = value
    # endregion

    # region: insert_front
    def insert_front(self, value):
        """O(n): the array's weak spot. To open a slot at index 0 every existing
        element must shift one place to the right."""
        if self._n == self._cap:
            self._resize(2 * self._cap)
        for i in range(self._n, 0, -1):
            self._store[i] = self._store[i - 1]
        self._store[0] = value
        self._n += 1
    # endregion

    def __len__(self):
        return self._n

    @property
    def capacity(self):
        return self._cap

    def to_list(self):
        return [self._store[i] for i in range(self._n)]

"""Python's built-in list IS a dynamic array — the exact structure this chapter
builds. So the face-off is our DynamicArray against the list it reimplements.

CPython's list over-allocates on a gentler curve than our doubling (its growth
factor is roughly 1.125), and the append + copy loop runs in C. Same amortized
O(1) append, same O(n) resize cost spread thin — just a smaller constant.
"""


# region: python_list
def build_with_list(values):
    """Append every value into a built-in list. Amortized O(1) per append,
    because the list over-allocates and only copies on the occasional resize."""
    out = []
    for value in values:
        out.append(value)
    return out
# endregion


# region: list_insert_front
def insert_front_with_list(values):
    """The built-in's front insert is list.insert(0, x) — still O(n) per call,
    same as ours, because the underlying array still has to shift."""
    out = []
    for value in values:
        out.insert(0, value)
    return out
# endregion

Desde cero vs librería

Misma estructura, mismo big-O, así que el duelo se trata puramente de la constante — y la constante es grande, porque el nuestro es un loop de Python y el list es C. Hacer append a 160000 elementos tomó unos 20.1 ms con nuestro DynamicArray contra 1.54 ms con el integrado, como trece veces más lento. La gráfica muestra ambas operaciones; fíjate que las líneas de append son rectas en los dos casos (trabajo total lineal, o sea constante amortizado por elemento) mientras que las de inserción al inicio se curvan hacia arriba — eso es el $O(n^2)$ de hacer un recorrido O(n) n veces, y se dobla igual para nuestro código y para el de la librería, porque la estructura lo obliga:

Trece veces es una brecha real, y es el precio de escribir tu propio contenedor en un lenguaje de alto nivel. También es irrelevante: nunca mandarías esto a producción. La razón de construirlo es saber exactamente qué hace list.append debajo de ti, para que cuando un profiler muestre un loop lleno de appends dominando, sepas que son los redimensionamientos raros y no las escrituras, y para que cuando veas list.insert(0, x) en una ruta caliente reconozcas la trampa O(n) al instante.

Dónde te lo vas a encontrar de verdad

Te topas con el array dinámico cada vez que escribes [] y empiezas a hacer append — es el tipo de lista por defecto en Python, JavaScript, Java, C++, Go y Rust, bajo los nombres list, Array, ArrayList, vector, slice y Vec. Su perfil de rendimiento le da forma a consejos cotidianos que probablemente ya absorbiste sin saber por qué: construye una lista haciendo append, no insertando al inicio; predimensiónala cuando conozcas el largo para saltarte los redimensionamientos por completo; prefiérela sobre una lista ligada para iterar porque al cache le encanta la memoria contigua. Cada uno de esos tips es consecuencia directa de la mecánica de este capítulo.

Puntos clave

Un array dinámico es un array fijo más una estrategia de crecimiento, y la estrategia de crecimiento es todo el truco: duplica la capacidad cuando se llena, para que las copias caras O(n) se vuelvan exponencialmente más raras y su costo se amortice a O(1) por append. Obtienes gratis acceso aleatorio en tiempo constante e iteración amigable con el cache, y lo pagas al inicio y en medio, donde cada inserción o borrado es O(n).

Ese trato — barato al final y por índice, caro en medio — es el array en una línea, y es la línea base contra la que se definen las siguientes estructuras. Las listas ligadas renuncian al índice O(1) para ganar inserción O(1) en cualquier punto donde ya estés parado. Los stacks y las colas son arrays con las operaciones restringidas a propósito a los extremos baratos. Ten presente la imagen de este capítulo, la del almacén de respaldo que se duplica; casi todo lo que sigue es una reacción a ella.