Un array guarda datos uno junto a otro
Un array es una serie de datos del mismo tipo guardados uno junto a otro en la memoria. Una lista de Python se apoya en esa idea. Saber cómo se guardan explica por qué leer el elemento 500 es instantáneo y por qué insertar al principio es lento.
Una tienda online guarda sus precios ordenados en una lista. Cada vez que añade uno, la lista tiene que hacerle sitio.
Al final de esta lección
Nota
Puedo explicar cómo se guarda una lista y cuánto cuesta insertar en ella.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Array | una serie de datos del mismo tipo, uno tras otro en la memoria | |
| Índice | el número de posición de un elemento, desde 0 | prices[2] |
| Memoria contigua | datos guardados sin huecos entre ellos | |
| Desplazar | mover un elemento a la posición de al lado | |
| Capacidad | cuántos elementos caben antes de pedir más sitio | |
| Coste | cuántos pasos necesita una operación |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un array ocupa un bloque sin huecos
La memoria del ordenador es una fila larga de bytes, cada uno con su número. Un array pide un bloque de bytes seguidos y mete los elementos uno tras otro.
Si cada entero ocupa 4 bytes, el primero empieza en el byte 0, el segundo en el 4 y el tercero en el 8. Esa es la memoria contigua: no hay huecos y no hace falta apuntar dónde está cada elemento.
Cuánto ocupan cuatro enteros
python3 -c "import array; a = array.array('i', [10, 20, 30, 40]); print(a.itemsize, len(a), a.itemsize * len(a))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un array enorme en C, en el laboratorio
grep -n "static int" ~/arch/loop.cSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Dónde empieza cada elemento
| Índice | Valor | Empieza en el byte |
|---|---|---|
| 0 | 10 | 0 |
| 1 | 20 | 4 |
| 2 | 30 | 8 |
| 3 | 40 | 12 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Leer por índice cuesta un solo paso
Los elementos tienen el mismo tamaño y no hay huecos. Por eso el ordenador calcula dónde está cada uno con una multiplicación: el byte de inicio más el índice por el tamaño.
Esa cuenta es igual con 10 elementos que con 10 millones. Por eso leer prices[500] cuesta un solo paso. Se dice que el acceso por índice es de coste constante.
Insertar obliga a desplazar elementos
No se puede meter un elemento entre otros dos sin hueco: hay que hacérselo. Para insertar un precio en la posición 1, todos los que están a su derecha dan un paso.
El programa de abajo lo hace con un bucle, de derecha a izquierda, para no pisar ningún valor. Ejecútalo y cuenta los movimientos.
Insertar a mano en una lista
# Insertar 15 en la posición 1 de una lista ordenada de precios.
prices = [10, 20, 30, 40]
position = 1
new_price = 15
moves = 0
prices.append(0) # sitio extra al final
i = len(prices) - 1
while i > position:
prices[i] = prices[i - 1] # cada elemento da un paso a la derecha
i = i - 1
moves = moves + 1
prices[position] = new_price
print(prices, moves)
# Cambia position a 0 y vuelve a ejecutar: ¿cuántos movimientos hay?
Cuántos movimientos hay en una lista de 5
| Dónde se inserta | Elementos a la derecha | Movimientos |
|---|---|---|
| Al principio | 5 | 5 |
| En el medio | 2 o 3 | 2 o 3 |
| Al final | 0 | 0 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un error frecuente
Advertencia
Mucha gente cree que insertar en una lista cuesta lo mismo en cualquier sitio. No es así. Insertar al final no mueve nada, pero insertar al principio mueve todos los elementos. Con un millón de precios, son un millón de pasos.
Insertar al principio de un array
python3 -c "import array; a = array.array('i', range(5)); a.insert(0, 99); print(a.tolist())"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Cuando la lista se llena, pide más sitio
Un array tiene un tamaño fijo. Una lista de Python crece porque, al llenarse, pide un bloque mayor, copia en él todos los elementos y suelta el bloque viejo.
Para que no ocurra cada vez, pide más sitio del que necesita: suele ser el doble. Esa capacidad de reserva hace que append casi siempre cueste un solo paso.
Para ir más lejos
Escribe moves_needed para borrar: al quitar el elemento de la posición 0, ¿cuántos se desplazan? Compara con borrar el último.
Después piensa cuándo no te importa el coste de insertar: una lista de diez elementos que casi nunca cambia no necesita otra estructura.