El arreglo dinámico por dentro en Java

Problema

El carrito que se vuelve lento

La tienda en línea muestra el carrito con el último producto añadido arriba. El código lo hace sin complicaciones: cada línea nueva entra en el índice 0.

String[] orderLines = {"Harina 25 kg", "Azúcar 10 kg", "Aceite 5 l", "Arroz 10 kg"};
List<String> cart = new ArrayList<>();
for (String line : orderLines) {
    cart.add(0, line);
}
System.out.println("El carrito: " + cart);

El carrito: [Arroz 10 kg, Aceite 5 l, Azúcar 10 kg, Harina 25 kg]

Con un cliente normal y 5 productos no se nota. Luego llega un cliente mayorista y sube un pedido desde un archivo: 50 000 líneas. La página se congela durante segundos.

La causa: cada inserción en el índice 0 mueve un espacio todos los productos ya añadidos. 50 000 líneas hacen 1 + 2 + … + 49 999 = 1 249 975 000 movimientos.

La idea

Un arreglo que se cuida solo

ArrayList es por dentro un arreglo dinámico: un arreglo normal con más espacios que elementos y un contador de cuántos están ocupados.

La capacidad es cuántos espacios tiene el arreglo.
El tamaño es cuántos de ellos están ocupados, de 0 al tamaño menos uno.

Cuando se acaban los espacios, crea un arreglo nuevo, el doble de grande, y copia todo. Por qué eso es O(1) de media se explica en la lección «Complejidad amortizada». Aquí miramos qué pasa dentro del arreglo: al leer, al insertar y al quitar por índice.

Los espacios del arreglo están uno junto a otro en la memoria y son del mismo tamaño. Si el arreglo empieza en la dirección 1000 y cada espacio ocupa 8 bytes, el espacio i está en la dirección 1000 + i × 8. Por eso leer por índice es una multiplicación y una suma: O(1), sin importar cuántos elementos haya.

Míralo

Tu propio arreglo dinámico

Aquí está lo mismo, escrito a mano. El arreglo empieza con 8 espacios:

class DynamicArray {
    private String[] items = new String[8];
    private int size = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
        }
        items = bigger;
    }
}

Mira qué pasa con los espacios al leer, insertar y quitar:

void insert(int index, String value) {
    Objects.checkIndex(index, size + 1);
    if (size == items.length) {
        grow();
    }
    for (int i = size; i > index; i--) {
        items[i] = items[i - 1];
    }
    items[index] = value;
    size++;
}

String removeAt(int index) {
    Objects.checkIndex(index, size);
    String removed = items[index];
    for (int i = index; i < size - 1; i++) {
        items[i] = items[i + 1];
    }
    size--;
    items[size] = null;
    return removed;
}

private String[] items = new String[8];
private int size = 0;

String get(int index) {
    Objects.checkIndex(index, size);
    return items[index];
}

void set(int index, String value) {
    Objects.checkIndex(index, size);
    items[index] = value;
}

private String[] items = new String[8];
private int size = 0;

void insert(int index, String value) {
    Objects.checkIndex(index, size + 1);
    if (size == items.length) {
        grow();
    }
    for (int i = size; i > index; i--) {
        items[i] = items[i - 1];
    }
    items[index] = value;
    size++;
}

private String[] items = new String[8];
private int size = 0;

String removeAt(int index) {
    Objects.checkIndex(index, size);
    String removed = items[index];
    for (int i = index; i < size - 1; i++) {
        items[i] = items[i + 1];
    }
    size--;
    items[size] = null;
    return removed;
}

Paso a paso, en palabras

El carrito es un único bloque de 8 espacios contiguos en la memoria. Hay 5 ocupados: ese es el tamaño. Los 8 son la capacidad.
get(3): la dirección es inicio + 3 × 8 = 1024. Un salto, sin pasar por los demás: O(1) con cualquier tamaño.
insert(0, …): el espacio 0 está ocupado. Cada producto se desplaza un espacio a la derecha, de atrás hacia delante, para no borrar nada: 5 desplazamientos.
Solo ahora «Queso» entra en el espacio 0, y el tamaño pasa a ser 6.
removeAt(2) saca «Leche». Los 3 siguientes se desplazan un espacio a la izquierda para cerrar el hueco: 3 desplazamientos.
El tamaño baja a 5, y el último espacio recibe null: la referencia antigua mantendría vivo el producto en la memoria.
get(5): el espacio 5 existe (la capacidad es 8), pero no está en el carrito. La comprobación compara con el tamaño y lanza IndexOutOfBoundsException.
Leer por índice es un salto. Insertar y quitar desplazan todo lo que hay después del índice: al principio son todos los n, O(n). Al final no se desplaza nada.

DynamicArray cart = new DynamicArray();
cart.add("Pan");
cart.add("Leche");
cart.add("Café");
cart.add("Mantequilla");
cart.add("Manzanas");
System.out.println(cart.get(3));
cart.insert(0, "Queso");
cart.removeAt(2);
for (int i = 0; i < cart.size(); i++) {
    System.out.println(i + ": " + cart.get(i));
}
System.out.println("Espacios: " + cart.capacity());
try {
    cart.get(5);
} catch (IndexOutOfBoundsException e) {
    System.out.println("Error: " + e.getMessage());
}

Mantequilla
0: Queso
1: Pan
2: Café
3: Mantequilla
4: Manzanas
Espacios: 8
Error: Index 5 out of bounds for length 5

Objects.checkIndex(index, size) lanza IndexOutOfBoundsException si el índice es negativo o no es menor que size. ArrayList comprueba igual.

Pruébalo

Predice la salida

Un arreglo con 8 espacios contiene 8 productos. Insertas uno más al principio:

class DynamicArray {
    private String[] items = new String[8];
    private int size = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
        }
        items = bigger;
    }
}

DynamicArray cart = new DynamicArray();
for (int i = 1; i <= 8; i++) {
    cart.add("P" + i);
}
cart.insert(0, "P0");
System.out.println("Productos: " + cart.size());
System.out.println("Espacios: " + cart.capacity());
System.out.println(cart.get(8));

Respuesta

Productos: 9
Espacios: 16
P8

Productos: 9
Espacios: 16
P0

Productos: 9
Espacios: 9
P8

La idea

Insertar y quitar cuestan O(n)

Insertar en el índice i mueve todo lo que hay desde i hasta el final un espacio a la derecha, de atrás hacia delante, para no borrar nada. Quitar mueve todo lo que hay después de i un espacio a la izquierda. Cuanto más cerca del principio, más:

Al final: no se mueve nada. O(1), y con el crecimiento O(1) amortizado.
Al principio: se mueve todo. O(n).
En el medio: de media, la mitad. Sigue siendo O(n).

Por eso n inserciones al principio son O(n²), y n adiciones al final, O(n). La solución para el carrito es añadir al final y mostrar de atrás hacia delante. Recorrer desde atrás es el mismo O(n):

String[] orderLines = {"Harina 25 kg", "Azúcar 10 kg", "Aceite 5 l", "Arroz 10 kg"};
List<String> cart = new ArrayList<>();
for (String line : orderLines) {
    cart.add(line);
}
List<String> newestFirst = cart.reversed();
System.out.println("El carrito: " + newestFirst);

El carrito: [Arroz 10 kg, Aceite 5 l, Azúcar 10 kg, Harina 25 kg]

Míralo

Mídelo: al final contra al principio

Ejecuta los dos caminos con los mismos productos. Contamos las escrituras de elementos en el arreglo: la del nuevo, cada movimiento y cada copia al crecer. Insertar al principio con 100 000 no se ejecuta de verdad: Bench lo estima a partir de la curva.

Agregar al final O(n)
Insertar al principio O(n²)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Agregar al final	18	2016	26.376	231.064
Insertar al principio	63	501.516	50.021.376	≈ 5.002.137.600

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

class DynamicArray {
    private String[] items = new String[8];
    private int size = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
        }
        items = bigger;
    }
}

Con 1000 productos, añadir al final hace 2016 escrituras: 1000 nuevas y las copias al crecer. Insertar al principio hace 501.516. Con 10 000 la diferencia es 26.376 contra 50.021.376.

Más precisamente, para curiosos

Los mismos números en tu lenguaje, con un contador de escrituras en la clase:

class DynamicArray {
    private String[] items = new String[8];
    private int size = 0;
    long writes = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
            writes++;
        }
        items[index] = value;
        writes++;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
            writes++;
        }
        items = bigger;
    }
}

for (int n : new int[] {10, 1000, 100000}) {
    DynamicArray cart = new DynamicArray();
    for (int i = 0; i < n; i++) {
        cart.add(String.valueOf(1001 + i));
    }
    System.out.println("al final, n = " + n + ": " + cart.writes + " escrituras");
}
for (int n : new int[] {10, 1000}) {
    DynamicArray cart = new DynamicArray();
    for (int i = 0; i < n; i++) {
        cart.insert(0, String.valueOf(1001 + i));
    }
    System.out.println("al principio, n = " + n + ": " + cart.writes + " escrituras");
}

al final, n = 10: 18 escrituras
al final, n = 1000: 2016 escrituras
al final, n = 100000: 231064 escrituras
al principio, n = 10: 63 escrituras
al principio, n = 1000: 501516 escrituras

Pruébalo

Encuentra el error

Un compañero ha reescrito insert. Tres productos, luego uno más al principio, y el carrito sale así:

DynamicArray cart = new DynamicArray();
cart.add("Pan");
cart.add("Leche");
cart.add("Café");
cart.insert(0, "Queso");
for (int i = 0; i < cart.size(); i++) {
    System.out.println(i + ": " + cart.get(i));
}

0: Queso
1: Pan
2: Pan
3: Pan

¿En qué línea está el error?

Elige la línea con el error.

Pruébalo

Completa

removeAt cierra el hueco moviendo cada elemento posterior un espacio a la izquierda. ¿De dónde viene el elemento del espacio i?

String removeAt(int index) {
    Objects.checkIndex(index, size);
    String removed = items[index];
    for (int i = index; i < size - 1; i++) {
        items[i] = items[];
    }
    size--;
    items[size] = null;
    return removed;
}

La idea

Reducir o no reducir

El carrito llegó a tener 10 000 productos, y luego el cliente quitó casi todos. El arreglo aún guarda 16 384 espacios. ¿Debería reducirse?

Si se reduce a la mitad en cuanto el tamaño cae por debajo de la mitad, hay una trampa. Un arreglo con 16 espacios y 9 elementos: un quitar, y pasa a 8 espacios, lleno. Un añadir, y vuelve a 16 espacios. Alterna los dos justo en ese límite, y cada operación copia todo: O(n).

Por eso la reducción espera más: a la mitad, cuando está lleno hasta un cuarto. Tras reducir, el arreglo está medio lleno, y hasta la siguiente copia hay al menos n/4 operaciones. El coste sigue siendo O(1) amortizado.

Las listas integradas deciden de otra forma:

Java ArrayList no se reduce nunca por sí solo. Lo reduces tú, con trimToSize().
C# List<T> no se reduce solo, tiene TrimExcess();
Python (CPython) se reduce solo por debajo de la mitad;
JavaScript (V8) a veces reduce, según sus propias reglas.

Reducir ahorra memoria, pero cuesta una copia. Si el arreglo va a volver a crecer pronto, es más barato no reducirlo.

La idea

Por qué el arreglo también es rápido en la práctica: el caché

El procesador no lee la memoria byte a byte. Toma una línea entera de 64 bytes y la guarda en el caché, una memoria pequeña y muy rápida a su lado. Leer del caché es decenas de veces más rápido que leer de la memoria principal.

El arreglo es un solo bloque. Cuando lees el espacio 0, sus vecinos vienen en la misma línea y las siguientes lecturas salen del caché. El procesador también nota que lees en orden, y trae las siguientes líneas por adelantado. Por eso recorrer un arreglo es rápido no solo sobre el papel, sino también en el reloj.

Importa qué hay en los espacios: - int[] guarda los propios números uno junto a otro. String[] y ArrayList<String> guardan referencias una junto a otra, y los objetos están en otro lugar de la memoria. Recorrer las referencias es rápido, pero cada lectura de un objeto puede ser un salto.

La siguiente lección, «Lista enlazada», es lo contrario: cada elemento es un objeto aparte en algún lugar de la memoria. Allí insertar al principio es O(1), pero el caché no ayuda.

Ejercicio

Un arreglo que se reduce

Resuélvelo en tu editor.

Reducir con un cuarto. Sustituye el crecimiento de la clase por un método resize(int places) que crea un arreglo con esa cantidad de espacios y copia los elementos. insert lo llama con el doble de espacios cuando el arreglo está lleno. removeAt lo llama con la mitad cuando el tamaño llega a un cuarto de los espacios, pero nunca por debajo de 8 espacios.

Añade 20 productos e imprime el tamaño y los espacios. Luego quita desde el final hasta que queden 2, e imprime el tamaño y los espacios en cada cambio de espacios:

20 / 32
8 / 16
4 / 8

Más ejercicios

indexOf y remove. Añade indexOf(String value), que devuelve el índice o -1, y remove(String value), que quita la primera aparición. ¿Cuánto cuesta cada uno?
Quitar del principio sin mover. Una cola de pedidos quita siempre el primero. Guarda un índice head del primer espacio ocupado en lugar de mover todos. ¿Qué pasa cuando head llega al final del arreglo? (Pista: continúa desde el principio.)
Llenar por partes. Importa 50 000 líneas de una vez: reúnelas al final y da la vuelta al arreglo una sola vez. ¿Cuántas escrituras son?

Test

Ponte a prueba

1. Un arreglo dinámico tiene 1000 elementos. ¿Cuántos elementos mueve una inserción en el índice 0? ¿Y en el índice 990?1000 y 10001 y 11000 y 10

2. ¿Por qué leer por índice es O(1) incluso con un millón de elementos?Porque el arreglo está ordenadoEl arreglo recuerda dónde está cada elemento en una tabla aparteLa dirección se calcula: inicio + índice × tamaño de un espacio

3. El arreglo tiene capacidad 8 y tamaño 5. ¿Qué pasa con get(6)?Devuelve un espacio vacíoUn error de índice fuera de los límites, aunque el espacio 6 existeEl arreglo crece hasta 16

4. ¿Por qué el arreglo se reduce a la mitad solo cuando está lleno hasta un cuarto, y no hasta la mitad?Porque reducir es lentoCon el límite en «la mitad», alternar añadir y quitar justo ahí reduciría y ampliaría cada vez, y cada una copia todoPorque la memoria solo se libera por cuartos

5. El carrito debe mostrar arriba el último producto añadido. ¿Cuál es la solución rápida?Añadir al final y mostrarlo de atrás hacia delanteOrdenar después de cada adiciónInsertar en el índice 0

El arreglo dinámico por dentro

Cookies