El intercambio entre espacio y tiempo
Seguí leyendo
Enterate del próximo post
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Antes de encender el fuego, muchas cocinas profesionales preparan todo: la cebolla picada en un bol, el ajo en otro, las especias medidas en un plato. Ocupa espacio en la mesada y lleva un rato, pero después la cocción avanza sin interrupciones, porque cada ingrediente está a mano en el momento exacto. Para freír un huevo, en cambio, nadie arma cinco boles: el tiempo de prepararlos sería mayor que el de cocinar, y la mesada quedaría ocupada para nada.
El post anterior dejó pendiente el costo del conjunto vistos, que bajó la búsqueda de repetidos de O(n²) a O(n). Esa mejora no fue gratis: se pagó con memoria. Este post trata ese intercambio, y cuándo conviene hacerlo.
Big O no mide solo pasos. También describe cuánta memoria adicional necesita un algoritmo mientras se ejecuta, sin contar la entrada que recibe: eso se llama su complejidad en espacio, y se calcula con las mismas dos reglas que la de tiempo. repetidos_por_pares usa unas pocas variables sin importar cuántos documentos reciba, así que su espacio es O(1). repetidos_con_conjunto guarda en vistos hasta un valor por documento, así que su espacio es O(n).
Puestos lado a lado, los dos algoritmos muestran el intercambio entre espacio y tiempo: el primero es O(n²) en tiempo y O(1) en espacio; el segundo, O(n) en tiempo y O(n) en espacio. Ninguno es mejor en las dos columnas a la vez. Casi siempre que un algoritmo se vuelve más rápido, lo logra de una de dos maneras: guardando resultados ya calculados para no repetir el cálculo, o armando una estructura auxiliar, como un conjunto o un diccionario, que responde rápido una pregunta que de otro modo exigiría recorrer todo. Las dos ocupan memoria.
Que el intercambio convenga depende del caso. Paga cuando la entrada es grande, cuando la misma pregunta se repite muchas veces y cuando la memoria sobra. No paga cuando la entrada es chica, cuando la pregunta se hace una sola vez o cuando la memoria es justa. Es la diferencia entre la cocina profesional y el huevo frito.
Hay además un costo que Big O no registra: cada estructura extra es algo más para leer, entender y mantener al día. Por eso conviene desconfiar de la optimización prematura, la que se hace antes de saber si hace falta. Donald Knuth lo escribió en 1974: en cerca del 97 % de los casos conviene olvidarse de las pequeñas mejoras de eficiencia, porque la optimización prematura es la raíz de todos los males. El orden recomendable es otro: primero un algoritmo correcto y claro; después, si resulta lento con datos reales, buscar dónde se va el tiempo; y recién ahí, optimizar esa parte.
Una elección escolar registra cada voto en una lista, con el nombre de la persona votada. Durante el recuento llegan varias preguntas del tipo "¿cuántos votos tiene Ana?". La forma directa responde cada pregunta recorriendo la lista.
algoritmo votos_de(votos, candidato):
asignar 0 a total
repetir posicion desde 1 hasta la cantidad de elementos de votos:
si el elemento en la posición posicion de votos es igual a candidato:
sumar 1 a total
devolver totalCada pregunta cuesta O(n) en tiempo y O(1) en espacio. La alternativa recorre la lista una sola vez y guarda el conteo de todos en un diccionario.
algoritmo contar_votos(votos):
asignar {} a conteo
repetir posicion desde 1 hasta la cantidad de elementos de votos:
asignar el elemento en la posición posicion de votos a candidato
si conteo contiene la clave candidato:
sumar 1 al valor asociado a la clave candidato en conteo
sino:
asignar 1 a la clave candidato en conteo
devolver conteoCon votos en ["Ana", "Bruno", "Ana", "Carla", "Ana", "Bruno"], contar_votos devuelve {"Ana": 3, "Bruno": 2, "Carla": 1}, y cada pregunta posterior se responde leyendo una clave, sin recorrer nada. Armarlo cuesta O(n) en tiempo y ocupa una clave por candidato distinto.
La cuenta muestra cuándo conviene. Con 6 votos y 3 preguntas, la forma directa hace 18 comparaciones y la del diccionario, 6 pasos para armarlo más 3 lecturas: 9. Con 10000 votos y 1000 preguntas, son 10000000 contra 11000. Pero con una sola pregunta, la forma directa hace 6 comparaciones y la otra, 7 pasos: preparar los boles no pagó.
El post de pilas y colas invirtió una lista apilando todos sus valores en una pila auxiliar y desapilándolos en otra lista (invertir_orden): O(n) en tiempo y O(n) en espacio. Escribir una versión que invierta la lista usando espacio O(1), sin ninguna estructura auxiliar.
Pista: el primer valor tiene que terminar en el último lugar y el último en el primero. Intercambiar los dos extremos y avanzar hacia el centro resuelve todo, y para intercambiar dos valores alcanza con una variable que guarde uno de ellos mientras tanto.
algoritmo invertir_en_lugar(lista):
asignar 1 a izquierda
asignar la cantidad de elementos de lista a derecha
mientras izquierda es menor a derecha:
asignar el elemento en la posición izquierda de lista a guardado
asignar el elemento en la posición derecha de lista al elemento en la posición izquierda de lista
asignar guardado al elemento en la posición derecha de lista
sumar 1 a izquierda
restar 1 a derecha
devolver listaCon lista en [4, 9, 15, 2, 7]: el primer intercambio cambia el 4 por el 7, el segundo cambia el 9 por el 2, y el 15 queda en el centro sin moverse. El resultado es [7, 2, 15, 9, 4], el mismo que daba invertir_orden, con dos intercambios para cinco valores. El tiempo sigue siendo O(n) y el espacio baja a O(1): solo existen izquierda, derecha y guardado, tenga la lista cinco valores o un millón.
Esta vez el ahorro no se pagó con tiempo, pero sí con otras dos cosas. Las tres asignaciones del intercambio dependen una de otra y tienen que ir exactamente en ese orden, la misma dependencia que analizó el post de secuencia; invertir_orden se lee de corrido sin ese cuidado. Y la lista original se reescribe en su lugar, así que su orden anterior ya no queda guardado en ninguna parte.
Un comercio anota las ventas de cada día en una lista, en orden. Durante la semana, la dueña pregunta muchas veces cuánto se vendió en total desde el primer día hasta un día dado. Resolver esas preguntas sin volver a sumar desde el principio cada vez.
Pista: el total hasta el día 5 es el total hasta el día 4 más la venta del día 5. Si esos totales parciales quedaran anotados, cada pregunta se respondería mirando uno solo.
algoritmo armar_acumulados(ventas):
asignar una lista vacía a acumulados
asignar 0 a total
repetir dia desde 1 hasta la cantidad de elementos de ventas:
sumar el elemento en la posición dia de ventas a total
agregar total al final de acumulados
devolver acumuladosCon ventas en [1200, 800, 1500, 900, 2000, 1100, 1300], acumulados queda en [1200, 2000, 3500, 4400, 6400, 7500, 8800], y la pregunta por los primeros cinco días se responde leyendo una posición: el elemento en la posición 5 de acumulados, 6400. Armar la lista es O(n) en tiempo y O(n) en espacio, una vez; cada pregunta después es O(1), contra O(n) si se sumara desde cero.
El intercambio conviene por las condiciones del enunciado: muchas preguntas sobre los mismos datos. Si la dueña preguntara una sola vez por semana, sumar en el momento sería más simple y no ocuparía nada. Y hay un costo de mantenimiento: si se corrige la venta del día 2, todos los acumulados desde el día 2 en adelante quedan mal hasta que se vuelvan a calcular. Dos estructuras que dicen lo mismo de dos formas tienen que mantenerse de acuerdo, y ese es el tipo de complejidad que la optimización prematura agrega sin necesidad.
Big O mide tanto el tiempo como el espacio, y muchas veces mejorar uno empeora el otro: guardar resultados o armar una estructura auxiliar acelera a cambio de memoria. Ese intercambio conviene con entradas grandes y preguntas repetidas, no siempre. Antes de optimizar, el algoritmo tiene que ser correcto y claro, y tiene que haber una razón medida para hacerlo más rápido.
El próximo post abre el bloque de algoritmos clásicos con la búsqueda: la lineal, que ya apareció en esta serie con esta_en_stock, y la binaria, que aprovecha que los datos estén ordenados para descartar la mitad de lo que queda en cada paso.