Datos, estructuras de datos y algoritmos, y por qué la velocidad depende de ellos

Todo son bits

Las computadoras lo almacenan todo como bits: dígitos binarios que valen 0 o 1. Físicamente, un bit puede ser una diminuta carga eléctrica, una zona magnética de un disco o un pulso de luz en una fibra, pero para el software es simplemente uno de dos valores. Ocho bits forman un byte, que puede contener 2⁸ = 256 patrones distintos, de 00000000 a 11111111.

A partir de ahí, los tamaños van creciendo. Un kilobyte son unos mil bytes, un megabyte alrededor de un millón, un gigabyte alrededor de mil millones y un terabyte alrededor de un billón. (En sentido estricto, los prefijos estándar kilo, mega y giga significan potencias de 1000; la memoria suele medirse en potencias de 1024, y para ellas existen las unidades kibibyte, mebibyte y gibibyte. La diferencia rara vez importa para el diseño, pero explica por qué un disco de "1 TB" muestra menos espacio en algunos gestores de archivos.) Una página de texto plano ocupa unos pocos kilobytes, una foto de un teléfono unos pocos megabytes y una hora de video en alta definición unos pocos gigabytes.

Los bits no significan nada por sí solos. El patrón 01000001 podría ser el número 65, la letra A, parte de un color de una foto o parte de una instrucción para la CPU. Lo que da significado a los bits es el acuerdo sobre cómo leerlos, que es la idea de un tipo de datos.

Tipos de datos: números, texto y verdadero o falso

Un tipo de datos le dice a un programa qué clase de valor es un dato y, por tanto, qué operaciones tienen sentido. Todos los lenguajes de programación tienen unos cuantos tipos básicos, y los de Python son representativos.

Los enteros son números sin decimales, como 3, 0 o -42, que se usan para contar cosas: artículos en un carrito, asientos en un vuelo. Los números de coma flotante (floats), como 12.5 o 0.2, representan los decimales de forma aproximada, en binario. Como muchos decimales no tienen una forma binaria exacta, 0.1 + 0.2 en Python da 0.30000000000000004. Eso no es problema en física o en gráficos, pero es incorrecto para el dinero, y por eso los sistemas financieros almacenan los importes como números enteros de peniques o céntimos, o usan un tipo decimal (Python tiene decimal.Decimal). Los booleanos tienen solo dos valores, True y False, y registran hechos de sí o no, como "¿se ha pagado este pedido?". Las cadenas son texto, como el nombre de un cliente. Los sistemas reales añaden más tipos por encima: fechas y horas, dinero y datos binarios como las imágenes.

Los tipos importan más allá de un solo programa. Cuando dos sistemas intercambian datos, deben ponerse de acuerdo tanto en los tipos como en los valores: ¿un código postal es un número o texto (texto: algunos empiezan por letras y algunos códigos numéricos empiezan por cero)? ¿Una fecha va en orden día-mes o mes-día, y en qué zona horaria? Muchos bugs de integración costosos son desacuerdos sobre tipos.

El texto y UTF-8

El texto se almacena asignando un número a cada carácter y guardando después esos números como bytes. El estándar internacional Unicode asigna un número, llamado punto de código, a bastante más de cien mil caracteres de los sistemas de escritura del mundo, además de símbolos y emojis. Después, una codificación decide cómo esos números se convierten en bytes. Hoy, la codificación dominante, en la web y en la mayoría de los sistemas nuevos, es UTF-8.

UTF-8 usa un número variable de bytes por carácter: un byte para las letras básicas del inglés, los dígitos y la puntuación (así que el texto que solo usa estos caracteres es idéntico, byte a byte, en UTF-8 y en la codificación ASCII, mucho más antigua), dos bytes para caracteres como é, tres para caracteres como € y la mayoría de los caracteres chinos, japoneses y coreanos, y cuatro para los emojis y algunas escrituras menos comunes. Esto tiene una consecuencia práctica: el número de caracteres de una cadena y el número de bytes que ocupa pueden ser distintos. Una columna de base de datos limitada a 50 bytes puede no ser capaz de contener un nombre de 50 caracteres escrito en griego.

El bug de texto clásico son los caracteres ilegibles (por ejemplo Café en lugar de Café), que aparecen cuando unos bytes escritos en una codificación se leen como si fueran de otra. La solución es fácil de enunciar: usa UTF-8 en todas partes, y dilo explícitamente siempre que el texto cruce un límite, como un archivo, una base de datos o un mensaje de red.

Estructuras de datos: formas de organizar los datos

Los programas rara vez manejan un solo valor a la vez. Una estructura de datos es una forma de organizar muchos valores en memoria para que las operaciones que necesitas sean rápidas. La elección correcta puede marcar la diferencia entre una página que carga al instante y otra que no llega a cargar nunca. Cada una tiene una analogía cotidiana.

Una lista (llamada array en muchos lenguajes) mantiene los elementos en orden, como una lista de la compra numerada. Obtener el quinto elemento es instantáneo, porque la computadora puede calcular dónde está. Encontrar un elemento por su valor obliga a revisar los elementos uno por uno. Un diccionario (también llamado mapa o tabla hash) guarda valores bajo claves únicas, como un guardarropa: entregas el resguardo C377 y recibes el abrigo correcto de inmediato, sin mirar todos los abrigos. Un conjunto es una colección sin duplicados, como una lista de invitados, y responde rápidamente a "¿está esta persona en ella?".

Una cola funciona como la fila ante el mostrador de una oficina de correos: el primero que entra es el primero que sale. Los sistemas usan colas para el trabajo pendiente, como los pedidos que esperan a la cocina. Una pila funciona como un montón de platos: el último que entra es el primero que sale. El botón Atrás de tu navegador usa una: la página que visitaste más recientemente es la primera a la que vuelves. Un árbol tiene una única raíz con ramas por debajo, como un árbol genealógico o las carpetas de tu computadora; los árboles también son la forma en que las bases de datos mantienen los datos ordenados para buscar rápido. Un grafo son elementos (nodos) unidos por enlaces (aristas) con cualquier patrón, como un mapa de carreteras o una red social, y responde a preguntas como "¿cuál es la ruta más corta?" o "¿quiénes son amigos de mis amigos?".

basket = ["pizza", "cola", "pizza"]            # list: ordered, duplicates allowed
print(basket[0])                                # by position: "pizza"

customers = {"C102": "Ana", "C377": "Chen"}      # dictionary: key to value
print(customers["C377"])                        # by key: "Chen"

voted = {"ana@example.com", "ben@example.com"}   # set: no duplicates
print("ana@example.com" in voted)              # True

from collections import deque
kitchen = deque(["order 1", "order 2"])         # queue
kitchen.append("order 3")                       # joins at the back
print(kitchen.popleft())                        # served first: "order 1"

Algoritmos

Un algoritmo es un método preciso, paso a paso, para resolver un problema y que siempre termina: como una receta, pero sin margen de interpretación. Ordenar una lista de nombres, encontrar la ruta más corta entre dos direcciones, comprobar si una contraseña coincide y decidir qué anuncio mostrar son tareas que realizan los algoritmos.

Normalmente hay más de un algoritmo para el mismo problema, y pueden diferir enormemente en la cantidad de trabajo que hacen. Piensa en buscar un nombre en una guía telefónica impresa. Podrías empezar en la página uno y leer cada entrada hasta encontrarlo: correcto, pero lento. O podrías abrir la guía por la mitad, ver si el nombre va antes o después de esa página, descartar la mitad que no puede contenerlo y repetir. Como la guía está ordenada, cada consulta reduce a la mitad las páginas restantes. Este segundo método se llama búsqueda binaria, y en una guía de un millón de nombres necesita unas 20 consultas en lugar de hasta un millón.

Big-O: cómo crece el trabajo con los datos

Los ingenieros describen cómo crece el costo de un algoritmo usando la notación O grande (Big-O). Ignora el tiempo exacto en una máquina concreta y plantea una sola pregunta: si la cantidad de datos, llamada n, se hace diez o mil veces mayor, ¿cuánto trabajo más hay? Describe el peor caso salvo que se indique otra cosa, e ignora los factores constantes, lo cual es a la vez su fortaleza (capta la forma del crecimiento) y su debilidad (dos algoritmos O(n) pueden diferir en la práctica en un factor de diez).

O(1), tiempo constante: el trabajo no depende de n. Buscar una clave en un diccionario es O(1) de media. O(log n), logarítmico: el trabajo crece un paso cada vez que n se duplica, como en la búsqueda binaria. O(n), lineal: el doble de datos, el doble de trabajo, como al recorrer una lista. O(n log n): un poco peor que lineal; los buenos algoritmos de ordenación de uso general trabajan a este ritmo. O(n²), cuadrático: el doble de datos, cuatro veces el trabajo. Suele aparecer cuando, para cada elemento, un programa recorre todos los demás elementos, por ejemplo al comparar cada cliente con todos los demás para encontrar duplicados.

Lee con atención la última columna. A mil millones de pasos sencillos por segundo, un algoritmo de un millón al cuadrado necesita un billón de pasos: alrededor de un cuarto de hora de cálculo puro y, en la práctica, mucho más. El mismo trabajo hecho con un método O(n log n) lleva una pequeña fracción de segundo. Un código que parecía ir bien en las pruebas con 1000 clientes puede quedar paralizado con un millón, y ninguna cantidad de hardware adicional salvará por mucho tiempo a un algoritmo cuadrático.

Espacio frente a tiempo

El diccionario del ejemplo práctico es más rápido porque usa memoria adicional para organizar los datos de antemano. Este es uno de los compromisos más habituales de la informática: a menudo puedes comprar velocidad con espacio, o ahorrar espacio gastando tiempo.

Un índice son datos adicionales, guardados junto a los datos principales, que responden rápidamente a un tipo concreto de pregunta, como el índice al final de un libro. Acelera las lecturas, pero ocupa almacenamiento y debe actualizarse en cada escritura, así que insertar en una tabla con diez índices es lento. Una caché guarda una copia de la respuesta a una pregunta costosa en algún lugar rápido, como la memoria, para que la siguiente persona que pregunte la obtenga de inmediato. Las cachés son la razón de que la página de un producto popular cargue rápido aunque la base de datos que hay detrás esté ocupada, pero plantean una pregunta difícil: cuando cambian los datos subyacentes, ¿con qué rapidez debe cambiar también la copia? Mostrar un precio obsoleto durante unos segundos puede ser aceptable; mostrar un saldo bancario obsoleto quizá no.

La compresión es el intercambio contrario: gastar tiempo de CPU para comprimir los datos en menos bytes, lo que ahorra almacenamiento y tiempo de transferencia por la red.

Por qué esto importa para la arquitectura

Los arquitectos rara vez escriben algoritmos de ordenación, pero toman constantemente decisiones cuyas consecuencias son exactamente estas. ¿Qué preguntas tendrá que responder rápidamente el sistema, y tienen los datos los índices necesarios para responderlas? ¿Cuánto crecerán los datos en tres años, y qué partes del diseño son lineales o peores ante ese crecimiento? ¿Dónde compensa la caché su complejidad, y hasta qué punto pueden estar obsoletos los datos en caché? Cuando el volumen de datos se multiplica por diez, ¿qué componente falla primero?

Son preguntas sobre rendimiento y escalabilidad, que el Capítulo 2 precisa, y sobre el uso de cachés y la elección de base de datos, que el Capítulo 7 trata a fondo. La sección siguiente pasa de los datos al código, y a cómo se organiza el código para que las personas puedan entenderlo y modificarlo.