Complejidad en espacio en Python

Problema

La exportación que se come la memoria

Cada noche un servicio exporta a un archivo los logs del día de la tienda. Para poder continuar donde se quedó después de una caída, escribe un punto de control después de cada línea. Solo que el punto de control es una copia de todo el archivo hasta ese momento:

def export_logs(logs):
    file = []
    checkpoints = []
    for line in logs:
        file.append(line)
        checkpoints.append(file.copy())
    return sum(len(saved) for saved in checkpoints)

¿Cuántos espacios ocupan las copias? El programa los cuenta:

for n in [5, 1000]:
    logs = [f"línea {i}" for i in range(1, n + 1)]
    print(f"{n} líneas: {export_logs(logs)} espacios")

5 líneas: 15 espacios
1000 líneas: 500500 espacios

Con 1000 líneas son 500 500 espacios. Los logs de un día son 100 000 líneas, y eso son 5 000 050 000 espacios. Cada espacio guarda una referencia de 4 a 8 bytes: entre 20 y 40 GB solo para las copias. En la prueba con 1000 líneas todo pasa, y por la noche la exportación se detiene con MemoryError.

La idea

La memoria también es un costo

Hasta ahora contabas operaciones. La memoria se cuenta igual: cuántos espacios aparta el algoritmo por sí mismo, aparte de la entrada que recibe. Esa es la complejidad en espacio del algoritmo. También se escribe con Big-O:

O(1): unas pocas variables, sea cual sea el tamaño de la entrada;
O(n): una copia de la entrada, una lista auxiliar, un conjunto con todos los elementos;
O(n²): una copia de la copia en cada paso, como en la exportación.

La entrada no cuenta, porque existe sin el algoritmo. Tampoco cuenta el resultado que pide la tarea: el archivo con n líneas es el trabajo de la exportación. Lo que cuenta son las copias que hace por el camino.

Míralo

Las copias se quedan

file = []
checkpoint = 0
for line in logs:
    file.append(line)
    checkpoint = len(file)

Paso a paso, en palabras

file es el archivo que escribe la exportación, y logs tiene 4 líneas. checkpoints guarda desde dónde continuar tras una caída.
La línea 1 va al archivo. El punto de control es una copia de todo el archivo: 1 espacio.
Línea 2. El nuevo punto de control copia las dos líneas, y el viejo se queda en la lista: 1 + 2 = 3 espacios.
Tras 4 líneas la memoria guarda 1 + 2 + 3 + 4 = 10 espacios. Tras n líneas son n(n + 1)/2: cinco mil millones con 100 000 líneas.
Para continuar tras una caída solo necesitas saber hasta dónde llegaste. Las copias desaparecen, queda un número.
Cada línea cambia el número: checkpoint = 4. La memoria extra es 1 espacio, sean cuantas sean las líneas.

Cada copia es una lista nueva en la memoria, y nadie borra las viejas: la lista checkpoints las guarda. Por eso los espacios crecen como 1 + 2 + 3 + … + n. Para continuar después de una caída, a la exportación solo le hace falta saber hasta dónde llegó:

def export_logs(logs):
    file = []
    checkpoint = 0
    for line in logs:
        file.append(line)
        checkpoint = len(file)
    return checkpoint

for n in [5, 1000]:
    logs = [f"línea {i}" for i in range(1, n + 1)]
    print(f"{n} líneas, checkpoint: {export_logs(logs)}")

5 líneas, checkpoint: 5
1000 líneas, checkpoint: 1000

El archivo es el mismo, y la memoria extra es un número: O(1) en lugar de O(n²).

Pruébalo

Predice la salida

La exportación con copias recibe 6 líneas. ¿Cuántos espacios ocupan los puntos de control?

def export_logs(logs):
    file = []
    checkpoints = []
    for line in logs:
        file.append(line)
        checkpoints.append(file.copy())
    return sum(len(saved) for saved in checkpoints)


for n in [6]:
    logs = [f"línea {i}" for i in range(1, n + 1)]
    print(f"{n} líneas: {export_logs(logs)} espacios")

Respuesta

6 líneas: 21 espacios

6 líneas: 6 espacios

6 líneas: 36 espacios

Míralo

Una copia o en el sitio

El administrador quiere las líneas de log más nuevas primero. Hay dos maneras. Una crea una lista nueva en orden inverso, y la otra intercambia los elementos de la propia lista: el primero con el último, el segundo con el penúltimo, hasta que los dos extremos se encuentran.

def newest_first(logs):
    result = []
    for i in range(len(logs) - 1, -1, -1):
        result.append(logs[i])
    return result


def reverse_in_place(logs):
    left = 0
    right = len(logs) - 1
    while left < right:
        logs[left], logs[right] = logs[right], logs[left]
        left += 1
        right -= 1

logs = ["09:00 inicio de sesión", "09:05 carrito", "09:07 pago"]
newest = newest_first(logs)
print("Copia:    " + ", ".join(newest))
print("Original: " + ", ".join(logs))
reverse_in_place(logs)
print("En sitio: " + ", ".join(logs))

Copia:    09:07 pago, 09:05 carrito, 09:00 inicio de sesión
Original: 09:00 inicio de sesión, 09:05 carrito, 09:07 pago
En sitio: 09:07 pago, 09:05 carrito, 09:00 inicio de sesión

La copia necesita n espacios nuevos, pero el original se queda como estaba. El cambio en el sitio necesita un espacio para el intercambio, pero el orden viejo desaparece. Cuál es mejor depende de si alguien más sigue leyendo el original.

Más precisamente, para curiosos

Las funciones incorporadas toman la misma decisión, y el nombre no siempre la delata:

logs = ["09:00 inicio de sesión", "09:05 carrito", "09:07 pago"]
copy = logs[::-1]
logs.reverse()
print("En sitio: " + ", ".join(logs))
print("Copia:    " + ", ".join(copy))

En sitio: 09:07 pago, 09:05 carrito, 09:00 inicio de sesión
Copia:    09:07 pago, 09:05 carrito, 09:00 inicio de sesión

logs.reverse() invierte en el sitio, y logs[::-1] hace una copia. Cada slice logs[a:b] es una copia: logs[1:] en una recursión copia casi toda la lista en cada llamada. reversed(logs) no copia, solo lee desde atrás.

La copia es superficial: la lista nueva guarda referencias a los mismos textos, no textos nuevos. Por eso los espacios se cuentan uno por elemento.

Pruébalo

Completa

Termina el intercambio de los dos extremos:

logs[left], logs[right] = logs[right],

Míralo

La recursión también guarda memoria

No solo una lista ocupa espacio. Cada llamada a una función guarda sus parámetros y variables locales en la pila de llamadas hasta que regresa. Aquí se cuentan los errores del log con recursión y con un bucle:

def errors_from(logs, i):
    if i == len(logs):
        return 0
    here = 1 if logs[i].startswith("ERROR") else 0
    return here + errors_from(logs, i + 1)

def errors(logs):
    count = 0
    for line in logs:
        if line.startswith("ERROR"):
            count += 1
    return count

small = make_logs(500)
big = make_logs(1_000_000)
print(f"500 líneas: {errors_from(small, 0)} errores")
try:
    print(f"1000000 líneas: {errors_from(big, 0)} errores")
except RecursionError:
    print("1000000 líneas: RecursionError")
print(f"Con bucle: {errors(big)} errores")

500 líneas: 5 errores
1000000 líneas: RecursionError
Con bucle: 10000 errores

La recursión no crea ni una sola lista, pero con n líneas hay n llamadas sin terminar en la pila: memoria O(n). La pila es pequeña, y un millón de llamadas no caben. El bucle tiene una variable count: O(1).

Python detiene la recursión ya en unas 1000 llamadas (sys.getrecursionlimit()). Es una protección: la pila real alcanzaría para más, pero no para un millón.

Más precisamente, para curiosos

Qué tan profunda puede ser la recursión depende del tamaño de la pila y del tamaño de un marco. El límite se sube con sys.setrecursionlimit, pero entonces la pila real del proceso puede agotarse y Python se cae sin mensaje.

Cuando la llamada recursiva es la última acción de la función (sin here + después), algunos lenguajes la convierten en un bucle (tail call). Java, C#, Python y Node no lo hacen, así que en ellos la profundidad siempre cuesta memoria.

La idea

Tiempo contra memoria

La tienda comprueba si dos pedidos del día tienen el mismo número. La primera manera compara cada par. La segunda recuerda en un conjunto los números que ya vio:

def has_duplicate_loops(orders):
    for i in range(len(orders)):
        for j in range(i + 1, len(orders)):
            if orders[i] == orders[j]:
                return True
    return False

def has_duplicate_set(orders):
    seen = set()
    for order in orders:
        if order in seen:
            return True
        seen.add(order)
    return False

today = [100512, 100513, 100514, 100512]
print(has_duplicate_loops(today), has_duplicate_set(today))

True True

Las dos dan la misma respuesta, pero pagan de forma distinta:

los bucles anidados: memoria O(1) y tiempo O(n²);
el conjunto: memoria O(n) (hasta n números) y tiempo O(n).

Es un intercambio común: memoria por tiempo. Cuántas comparaciones y comprobaciones hacen las dos cuando no hay repetido (el peor caso):

def comparisons_loops(orders):
    count = 0
    for i in range(len(orders)):
        for j in range(i + 1, len(orders)):
            count += 1
            if orders[i] == orders[j]:
                return count
    return count


def checks_set(orders):
    seen = set()
    count = 0
    for order in orders:
        count += 1
        if order in seen:
            return count
        seen.add(order)
    return count

for n in [10, 1000]:
    orders = [100000 + i for i in range(n)]
    print(f"{n} pedidos: {comparisons_loops(orders)} comparaciones con bucles, {checks_set(orders)} comprobaciones con set")

10 pedidos: 45 comparaciones con bucles, 10 comprobaciones con set
1000 pedidos: 499500 comparaciones con bucles, 1000 comprobaciones con set

Bucles anidados, sin memoria O(n²)
Un conjunto de números vistos, n lugares O(n)

Algoritmo	n = 10	n = 1000	n = 100.000
Bucles anidados, sin memoria	45	499.500	≈ 4.995.000.000
Un conjunto de números vistos, n lugares	10	1000	100.000

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.

Con 100 000 pedidos los bucles hacen casi 5 mil millones de comparaciones, y el conjunto hace 100 000 comprobaciones y guarda 100 000 números. Cuando hay memoria, gana el conjunto. Cuando no la hay (un dispositivo pequeño, una entrada enorme), o ordenas los números (así los repetidos quedan juntos) o lees por partes.

Más precisamente, para curiosos

Contamos una comprobación en el conjunto como una operación. Es O(1) en promedio, porque el conjunto es una tabla hash: el número se convierte en un hash, y el hash dice en qué cubeta mirar. Un espacio en un conjunto cuesta más que un número en un array: en un set unos 30–60 bytes (una entrada en la tabla y el objeto int). Así que «memoria O(n)» para 10 millones de pedidos son cientos de MB, no 40.

Pruébalo

Encuentra el error

Un compañero reescribió la comprobación con un conjunto, pero nunca encuentra un repetido:

def has_duplicate_set(orders):
    for order in orders:
        seen = set()
        if order in seen:
            return True
        seen.add(order)
    return False

today = [100512, 100513, 100514, 100512]
print(has_duplicate_set(today))

False

El número 100512 está dos veces, y la respuesta es «no». ¿En qué línea está el error?

Elige la línea con el error.

Ejercicio

Las últimas tres líneas

Resuelve la tarea en tu editor.

Las últimas líneas. Cuando algo se rompe, el administrador quiere solo las últimas k líneas del log. Escribe last_lines(logs, k), que las devuelva guardando en memoria como máximo k líneas, no todo el log: memoria O(k). Ejecútalo con 1000 líneas («línea 1» … «línea 1000») y k = 3.

línea 998
línea 999
línea 1000

Una posible solución

Mantén una cola: cada línea nueva entra por detrás y, cuando hay más de k líneas, la más antigua sale por delante.

from collections import deque


def last_lines(logs, k):
    recent = deque(maxlen=k)
    for line in logs:
        recent.append(line)
    return list(recent)

deque(maxlen=k) expulsa sola la línea más antigua cuando está llena.

Más tareas

El promedio de longitud sin copia. Calcula la longitud promedio de una línea del log con memoria extra O(1): sin una lista nueva de longitudes.
Errores por hora. Cuenta los errores de cada hora (09, 10 …). ¿Cuánta memoria necesita tu solución si hay 24 horas y un millón de líneas?
Los números repetidos. Devuelve no solo «sí o no», sino todos los números repetidos. ¿Cuánta memoria necesita la solución con un conjunto, y se puede hacer sin él?

Test

Ponte a prueba

1. Una función crea una lista nueva con n líneas de log en orden inverso. ¿Cuánta memoria extra necesita?O(n)O(n²)O(1)

2. La exportación guarda después de cada línea una copia de todo el archivo hasta ese momento. ¿Cuántos espacios ocupa la memoria con n líneas?n(n + 1)/2, es decir, O(n²)n2n

3. Una función recursiva sin ninguna lista se llama a sí misma 1 000 000 de veces, una dentro de otra. ¿Cuánta memoria necesita?O(n): cada llamada se queda en la pila hasta que regresaO(1), porque no hay listasNinguna, la memoria es solo para objetos

4. Buscas un número repetido entre 10 000 000 de pedidos en un servidor con unos pocos GB de memoria libre. ¿Qué eliges?El conjunto: memoria O(n), pero tiempo O(n) en lugar de O(n²)Los bucles anidados, porque no necesitan memoriaNo hay diferencia

5. ¿Qué no cuenta en la memoria extra de una función?La pila de su recursiónLa entrada que recibe la funciónUna copia de la entrada que hace la función

Complejidad en espacio

Cookies