Estructuras de datos que se ven

La notación O grande es la manera en que la informática describe cuánto crece el coste de un algoritmo cuando crece el tamaño de su entrada, ignorando todo lo demás. Decir que la búsqueda binaria es O(log n) y la búsqueda lineal es O(n) no dice cuánto tarda ninguna de las dos en ningún ordenador; dice que si la lista se hace mil veces más larga, la primera necesitará unos diez pasos más y la segunda mil veces más pasos. Es una notación de crecimiento, no de velocidad, y su utilidad viene de que el crecimiento es lo único que importa cuando n es grande: una constante, por fea que sea, la puede compensar una máquina mejor, y un exponente no lo compensa nada.

La figura de esta página no dibuja fórmulas sino recuentos. Para cada tamaño de entrada entre unas decenas y varios miles, ejecuta de verdad, en el navegador del lector, cinco algoritmos sobre datos aleatorios y cuenta cuántas comparaciones hacen: buscar un elemento que no está en una lista, con búsqueda lineal y con búsqueda binaria; ordenar la lista, con el método de la burbuja y con el de mezcla; y enumerar todos los subconjuntos de un conjunto, que es lo que hay que hacer cuando no se conoce nada mejor. Los puntos son las medidas; las líneas de trazos, la curva teórica de cada orden, ajustada a las medidas por un solo factor. Que los puntos caigan sobre las líneas es la comprobación de que la notación describe algo real.

Lo primero que se ve es la distancia entre órdenes. Para una lista de mil elementos, la búsqueda binaria hace unas diez comparaciones y la lineal mil; ordenar por mezcla cuesta unas diez mil y ordenar por burbuja, medio millón. Con dos mil elementos, la binaria hace una comparación más, la lineal el doble, la mezcla algo más del doble y la burbuja cuatro veces más. Esa es la definición en acción: el orden de un algoritmo dice cómo escala su coste al multiplicar n. Un algoritmo O(n²) multiplica su coste por cuatro cada vez que la entrada se dobla; uno O(n log n) por poco más de dos; uno O(log n) apenas lo mueve. Y la curva de 2ⁿ, la de los subconjuntos, solo llega en la figura hasta n = 22, porque para n = 40 harían falta un billón de pasos y para n = 100 no bastaría la edad del universo. Los problemas cuyo mejor algoritmo conocido es de ese tipo se llaman intratables, y buena parte de la informática teórica consiste en averiguar cuáles lo son.

Lo segundo es por qué el eje vertical está en escala logarítmica. Al pulsar el botón que la quita, la burbuja se convierte en una pared y las otras cuatro curvas se aplastan contra el eje, indistinguibles. Los órdenes de crecimiento se diferencian por factores multiplicativos, no aditivos, y solo una escala que convierta multiplicar en sumar los muestra a la vez. Esa misma razón explica por qué la notación ignora las constantes: en la escala que importa, un factor constante es un desplazamiento vertical, y las curvas de órdenes distintos acaban cruzándose, pase lo que pase con las constantes, en algún n suficientemente grande.

La definición formal es más modesta de lo que su uso sugiere. Decir que una función f(n) es O(g(n)) significa que existe una constante c tal que, a partir de cierto n, f(n) ≤ c·g(n): g es una cota superior del crecimiento de f, salvo constante y salvo los primeros valores. La notación la introdujo Paul Bachmann en 1894 en un tratado de teoría de números, la popularizó Edmund Landau en 1909, y la informática la adoptó cuando Juris Hartmanis y Richard Stearns fundaron la teoría de la complejidad computacional en 1965 midiendo el coste de los algoritmos como función del tamaño de la entrada. Donald Knuth, en una nota de 1976 que sigue siendo la referencia, señaló que la mayoría de los informáticos usan la O grande para decir «crece exactamente como», que es lo que significa la notación Θ (theta), y que lo hacen porque casi siempre la cota superior que se conoce es también la real. Cuando se dice que la ordenación por mezcla «es n log n», se está diciendo Θ, aunque se escriba O.

Hay tres cosas que la notación no dice y que conviene recordar al leerla. No dice nada del caso concreto: la búsqueda lineal de la figura busca un elemento que no está, su peor caso, y si el elemento estuviera al principio terminaría en un paso. No dice nada de n pequeño: para listas de diez elementos, un algoritmo cuadrático sencillo suele ganar a uno n log n complicado, y las bibliotecas de ordenación reales cambian de algoritmo por debajo de cierto tamaño. Y no dice nada de la memoria, ni de la caché, ni del paralelismo, que en una máquina real pueden pesar más que el número de comparaciones. Lo que sí dice es lo que los puntos de la figura muestran al subir el deslizador: hacia dónde va cada curva, y por tanto qué algoritmo dejará de funcionar primero cuando los datos crezcan. Es una notación para prever el futuro de un programa, y para eso sirve mejor que cualquier cronómetro.

Los algoritmos de ordenación son los procedimientos con los que un ordenador pone una lista en orden, y constituyen el problema más estudiado de la historia de la informática: Donald Knuth le dedicó medio volumen de The Art of Computer Programming y estimó en los años setenta que los ordenadores del mundo pasaban más de una cuarta parte de su tiempo ordenando. Hay decenas de métodos, y la razón de que no baste con uno es que ninguno es el mejor en todas las circunstancias. La figura de esta página pone a cuatro de ellos a ordenar la misma lista a la vez, operación a operación, para que se vea en qué se diferencian y por qué el ganador cambia según los datos.

Los cuatro corredores representan las dos grandes familias. La ordenación por burbuja y la ordenación por inserción son métodos cuadráticos: en el peor caso, el número de operaciones crece con el cuadrado del tamaño de la lista, de modo que ordenar diez veces más elementos cuesta cien veces más. La ordenación por mezcla y la ordenación rápida son métodos de divide y vencerás: partan la lista en trozos, ordenan cada trozo y combinan los resultados, y su coste crece solo un poco más rápido que el tamaño de la lista, en proporción a n por el logaritmo de n. Con cuarenta elementos la diferencia es visible; con un millón es la diferencia entre un segundo y varias horas.

La burbuja recorre la lista comparando cada elemento con el siguiente e intercambiándolos si están en el orden incorrecto, de manera que el mayor «sube» hasta el final en cada pasada, como una burbuja en el agua. Es el primer algoritmo que se enseña y probablemente el peor que se usa: Knuth escribió que «no parece tener nada que lo recomiende, salvo un nombre pegadizo», y Owen Astrachan rastreó en 2003 el origen de su popularidad hasta los manuales de los años sesenta sin encontrar ninguna virtud técnica que la justificara. En la figura se aprecia su defecto característico: los elementos pequeños que están al final avanzan solo una posición por pasada, así que una lista al revés le exige el máximo de trabajo posible.

La inserción hace lo que hace una persona con una mano de cartas: toma el siguiente elemento y lo desplaza hacia la izquierda hasta que encuentra su sitio entre los que ya están ordenados. También es cuadrática en el peor caso, pero con una diferencia decisiva: si la lista está casi ordenada, cada elemento se mueve muy poco y el algoritmo termina en un tiempo casi proporcional al tamaño de la lista. Al elegir «casi ordenados» en la figura, la inserción gana la carrera con claridad a los dos métodos teóricamente superiores. Por eso sigue viva dentro de casi todos los algoritmos modernos, que la usan para rematar los trozos pequeños.

La ordenación por mezcla divide la lista por la mitad, ordena cada mitad —dividiéndola a su vez— y después fusiona las dos mitades ordenadas recorriéndolas en paralelo y tomando en cada paso el menor de los dos frentes. John von Neumann la describió en 1945 para el EDVAC. Su virtud es la regularidad: hace el mismo número de operaciones sea cual sea el orden inicial de los datos, y es estable, es decir, dos elementos iguales conservan su orden relativo, cosa que importa cuando se ordena una tabla primero por una columna y luego por otra. Su coste es que necesita una segunda lista auxiliar del mismo tamaño para ir depositando la fusión, y en la figura se distingue porque escribe mucho más de lo que intercambia.

La ordenación rápida, o quicksort, la inventó Tony Hoare en 1959, con veinticinco años, mientras estaba en Moscú como estudiante de intercambio trabajando en traducción automática y necesitaba ordenar palabras para buscarlas en un diccionario en cinta. Elige un elemento como pivote, coloca a su izquierda todos los menores y a su derecha todos los mayores, y repite el proceso en cada uno de los dos lados. En la figura el pivote es la barra naranja de la derecha del tramo sombreado, y se ve cómo va a parar a su posición definitiva en cada ronda. Es en promedio el más rápido de los cuatro y no necesita memoria auxiliar, pero tiene un talón de Aquiles: si el pivote resulta ser siempre el mayor o el menor —como ocurre con la versión más simple sobre una lista ya ordenada o invertida—, la partición es inútil y el algoritmo cae al coste cuadrático. Hoare mismo propuso elegir el pivote al azar para evitarlo, y las versiones modernas toman la mediana de tres elementos.

Se puede demostrar que ningún algoritmo que ordene comparando elementos entre sí puede hacerlo, en el peor caso, con menos operaciones que una cantidad proporcional a n por el logaritmo de n: ordenar n elementos es distinguir entre las n! permutaciones posibles, y cada comparación descarta como mucho la mitad. La mezcla y la rápida están, por tanto, en el óptimo teórico, y la carrera entre ellas se decide por las constantes, por el uso de memoria y por la forma de los datos. Solo saliéndose de las comparaciones —contando ocurrencias, o mirando los dígitos de los números uno a uno, como hace la ordenación por radix— se puede ir más deprisa, y solo para tipos de datos concretos.

Los algoritmos que ordenan de verdad hoy son híbridos que sacan partido de cada carril de la figura. Timsort, que Tim Peters escribió en 2002 para Python y que Java adoptó en 2009 y Android después, es una mezcla que detecta los tramos ya ordenados de la lista —que en los datos reales abundan— y los fusiona con inteligencia, recurriendo a la inserción para los tramos cortos. Es tan complejo que en 2015 un grupo de investigadores que intentaba verificarlo formalmente encontró en la implementación de Java un error que llevaba seis años en producción y que podía hacer que el programa fallara con ciertas entradas raras. Los algoritmos de ordenación, sesenta años después de Hoare, siguen dando trabajo.

La tabla hash es la estructura de datos que permite guardar y encontrar cosas por su nombre en un tiempo que no depende de cuántas cosas haya. Es lo que hay detrás de los diccionarios de Python, los objetos de JavaScript, los índices de las bases de datos en memoria y las cachés de casi cualquier programa. La idea es de una audacia que sigue sorprendiendo cuando se ve por primera vez: en lugar de buscar la clave comparándola con las que ya hay, se calcula a partir de la propia clave, con una fórmula, el lugar donde debería estar, y se va directamente allí. La fórmula es la función hash; el lugar, una cubeta de un vector; y el problema que da lugar a toda la teoría es qué hacer cuando dos claves distintas caen en la misma cubeta, que es inevitable y se llama colisión.

La figura de esta página es una tabla hash con las cubetas a la vista. Cada palabra que se inserta pasa por la función hash elegida, el resultado se divide por el número de cubetas, y el resto dice en cuál cae. Con el método de encadenamiento, cada cubeta es una lista y las palabras que colisionan se apilan en ella; buscar una palabra es ir a su cubeta y recorrer la lista. Con el de direccionamiento abierto, cada cubeta guarda una sola palabra, y la que encuentra la suya ocupada avanza a la siguiente libre; buscar es ir a la cubeta y avanzar hasta encontrar la palabra o un hueco vacío. Los dos métodos son de los años cincuenta: Arnold Dumey publicó el primero en 1956, con la observación de que un resto de división reparte bien las claves, y Wesley Peterson analizó el segundo en 1957 para los discos de IBM.

Lo que la figura enseña primero es que la función hash lo es todo. La suma de los códigos de las letras es una función hash legítima —siempre da el mismo número para la misma palabra— y es pésima: las palabras de longitud parecida suman cantidades parecidas y caen en cubetas vecinas, dos anagramas caen en la misma, y con dieciséis cubetas la mayoría de las palabras acaban en tres o cuatro de ellas mientras el resto quedan vacías. Una función buena, como FNV-1a, mezcla cada letra con las anteriores de manera que cambiar una sola letra cambia el resultado entero de forma impredecible, y las palabras se reparten como si se hubieran lanzado al azar. Esa es la propiedad que se pide: no que la función sea aleatoria, sino que se comporte como si lo fuera. Lawrence Carter y Mark Wegman demostraron en 1979 que eligiendo la función hash al azar de una familia adecuada se garantiza ese comportamiento para cualquier conjunto de claves, incluso uno elegido por un adversario, lo que hoy importa porque una tabla hash con una función predecible se puede atacar llenándola de colisiones a propósito.

Lo segundo es el factor de carga, la fracción de cubetas ocupadas, que la figura llama α. Con encadenamiento, si las claves se reparten bien, la longitud media de una lista es α y buscar una clave que está cuesta de media 1 + α/2 comparaciones; con α = 2 son dos, con α = 10 son seis, y la tabla degenera en una lista corriente. Con direccionamiento abierto la cosa es más brusca: Donald Knuth calculó en 1963, en el que cuenta como su primer análisis de un algoritmo, que buscar con sondeo lineal cuesta de media ½(1 + 1/(1 − α)) sondeos, que vale 1,5 con la tabla medio llena, 3 al 80 % y 50 al 99 %. La figura reproduce esa curva: al insertar palabras en una tabla pequeña con direccionamiento abierto, los sondeos se disparan al llenarse, y llega un momento en que no cabe nada. Por eso las tablas reales se agrandan solas cuando α supera un límite, típicamente entre 0,7 y 0,9, copiando todo a un vector del doble de tamaño. Esa copia cuesta, pero se hace pocas veces, y repartida entre todas las inserciones sale a coste constante.

Lo tercero es qué significa «tiempo constante». Una tabla hash no promete que cada búsqueda cueste lo mismo; promete que el promedio no crece con el número de claves, siempre que la función reparta bien y la carga se mantenga a raya. La peor búsqueda posible puede recorrer todas las claves, y hay variantes, como el hashing cuco de Rasmus Pagh y Flemming Rodler de 2004, que garantizan como mucho dos sondeos en cualquier búsqueda a cambio de una inserción más complicada. Pero el promedio es lo que hace útil la estructura, y es lo que la hace distinta de los árboles de búsqueda, que garantizan un coste logarítmico en el peor caso a cambio de no alcanzar nunca el constante.

La tabla hash es también un buen ejemplo de una idea que reaparece en toda la informática: cambiar orden por aleatoriedad. Un vector ordenado permite buscar en tiempo logarítmico porque el orden dice hacia dónde ir; una tabla hash renuncia al orden —sus claves no se pueden recorrer de menor a mayor— y a cambio va directa. La figura muestra esa renuncia en el desorden de las cubetas: las palabras están donde su hash las mandó, sin relación con su alfabeto ni con su llegada. Es la misma apuesta que hacen el filtro de Bloom y buena parte de los algoritmos probabilistas: aceptar que el peor caso exista, y organizar las cosas para que casi nunca ocurra.

El árbol binario de búsqueda es una estructura de datos en la que cada elemento tiene como mucho dos hijos, todo lo que cuelga a su izquierda es menor que él y todo lo que cuelga a su derecha es mayor. Esa única regla hace que buscar un valor sea como buscar en un diccionario: se compara con la raíz, se baja a la izquierda o a la derecha según el resultado, y se repite, descartando en cada paso la mitad del árbol que no puede contenerlo. Si el árbol está bien repartido, encontrar cualquiera de un millón de elementos cuesta unas veinte comparaciones. Si está mal repartido, puede costar un millón. Toda la historia de esta estructura, desde 1960 hasta hoy, es la historia de cómo mantenerlo bien repartido.

La figura de esta página construye el árbol delante del lector. Al insertar quince números al azar, cada uno baja desde la raíz hasta encontrar su sitio, y el resultado es un árbol frondoso de cuatro o cinco niveles. Al vaciarlo e insertar los números del 1 al 15 en orden, cada nuevo número es mayor que todos los anteriores, cae siempre a la derecha, y el árbol se convierte en una hilera inclinada de quince niveles: una lista disfrazada, en la que buscar el 15 cuesta quince comparaciones en lugar de cuatro. Son las mismas quince claves; lo único que ha cambiado es el orden de llegada. La figura anota la altura del árbol junto a la mínima posible, y la diferencia entre ambas es la medida del problema.

El caso degenerado no es un artificio de laboratorio. Los datos que llegan a un programa suelen venir ordenados o casi: registros por fecha, nombres de un fichero alfabético, números de serie consecutivos. Peter Windley describió la estructura en 1960 y Thomas Hibbard analizó en 1962 lo que ocurre con claves en orden aleatorio: la altura esperada es de unas 1,39 veces el logaritmo en base 2 del número de claves, poco más que la mínima, así que con datos realmente barajados el árbol se comporta bien solo. Pero el promedio no protege del caso concreto, y el caso concreto malo es el más común en la práctica. Donald Knuth dedica a esto buena parte de la sección sobre árboles del tercer volumen de The Art of Computer Programming, y la conclusión es que un árbol de búsqueda sin más es una estructura para datos que uno sabe que llegan desordenados.

La solución llegó también en 1962, desde Moscú. Georgy Adelson-Velsky y Evgenii Landis propusieron mantener, en cada nodo, la diferencia de altura entre su subárbol izquierdo y el derecho, y no permitir nunca que pase de uno. Cuando una inserción rompe esa condición, se arregla con una rotación: un reajuste local de tres nodos que conserva el orden y baja al lado alto un nivel. La figura lo hace al activar el botón AVL, y el resultado es que los números del 1 al 15 en orden producen exactamente el mismo árbol perfecto que producirían insertados en el orden ideal, con el 8 en la raíz y cuatro niveles. El precio son las rotaciones, que la figura cuenta, y algo de memoria por nodo para guardar las alturas. La garantía es que la altura nunca supera 1,44 veces el logaritmo del número de claves, sea cual sea el orden de llegada.

Los árboles AVL fueron el primero de una familia. Rudolf Bayer propuso en 1972 los árboles rojo-negro, que relajan la condición de equilibrio a cambio de menos rotaciones y son los que usan las bibliotecas estándar de C++ y Java para sus mapas ordenados; el mismo Bayer inventó ese año, con Edward McCreight, los árboles B, que ponen muchas claves en cada nodo para minimizar accesos a disco y sostienen los índices de casi todas las bases de datos. Daniel Sleator y Robert Tarjan propusieron en 1985 los árboles biselados, que no guardan nada sobre el equilibrio y en cambio mueven a la raíz cada clave que se busca, de modo que las claves frecuentes quedan arriba; no garantizan nada sobre una búsqueda concreta pero sí sobre cualquier secuencia larga de ellas, y son un ejemplo temprano del análisis amortizado.

Lo que hace útil al árbol de búsqueda frente a la tabla hash, que encuentra cualquier clave en tiempo constante, es que el árbol conserva el orden. Recorrerlo de izquierda a derecha produce las claves ordenadas; encontrar la clave más pequeña mayor que un valor dado, o todas las que están en un intervalo, cuesta lo mismo que una búsqueda; y el peor caso, con equilibrio, está garantizado y no solo prometido en promedio. Por eso los dos conviven: la tabla hash para preguntar «¿está?» y el árbol para preguntar «¿qué hay entre esto y aquello?». La figura enseña el precio de esa capacidad, que es el trabajo de mantener el árbol en forma, y también lo pequeño que es ese precio cuando se paga en cada inserción en lugar de dejar que la deuda crezca.

El problema de los puentes de Königsberg pregunta si se puede dar un paseo por la ciudad cruzando cada uno de sus siete puentes exactamente una vez. Leonhard Euler demostró en 1736 que no, y la manera en que lo demostró —olvidándose de la ciudad y quedándose solo con qué está conectado con qué— es el acta de nacimiento de la teoría de grafos, la rama de las matemáticas con la que hoy se describen las redes sociales, las rutas de internet, las cadenas de contagio y los mapas de carreteras.

Königsberg, hoy Kaliningrado, estaba partida por el río Pregel en cuatro trozos de tierra: la orilla norte, la orilla sur, la isla de Kneiphof en medio y la isla de Lomse al este, donde el río se bifurca. Siete puentes las unían: dos entre Kneiphof y cada orilla, uno entre Kneiphof y Lomse, y uno entre Lomse y cada orilla. Los vecinos se preguntaban desde hacía tiempo si existía un recorrido que pasara por los siete sin repetir ninguno, y en 1735 el alcalde de Danzig, Carl Ehler, se lo planteó por carta a Euler, que tenía entonces veintiocho años y trabajaba en la Academia de San Petersburgo. Euler respondió al principio que el problema «apenas tenía que ver con las matemáticas», pero lo resolvió, lo presentó ante la Academia el 26 de agosto de 1736 y lo publicó, con el título Solución de un problema relativo a la geometría de posición, en 1741.

Lo primero que hizo Euler fue tirar el mapa. Da igual la forma de las islas, la longitud de los puentes o por qué calle se vaya: lo único que cuenta es qué trozo de tierra está unido con cuál y por cuántos puentes. Llamó A, B, C y D a los cuatro trozos y describió un paseo como una secuencia de letras, una por cada vez que se pisa un trozo de tierra: cruzar siete puentes son ocho letras. Después contó. Cada vez que un paseo entra en un trozo de tierra y vuelve a salir gasta dos puentes; por eso un trozo con un número impar de puentes tiene que ser el principio o el final del paseo, porque el puente sobrante solo puede usarse para llegar o para irse. Y un paseo solo tiene un principio y un final. En Königsberg, los cuatro trozos de tierra tenían un número impar de puentes: cinco la isla de Kneiphof, tres cada uno de los otros. Cuatro candidatos a extremo para un paseo que solo tiene dos. Imposible, sin necesidad de probar recorridos.

La figura deja comprobarlo por la vía lenta: se puede cruzar cinco puentes con facilidad, seis con suerte, y el séptimo siempre queda al otro lado del río. Cuando uno se atasca, la lectura dice dónde y por qué, y la cuenta de grados —así se llama al número de aristas que tocan un vértice— muestra los cuatro impares. La condición de Euler no depende del mapa: cualquier grafo con más de dos vértices de grado impar es imposible de recorrer así. Con exactamente dos, si el recorrido existe tiene que empezar en uno y terminar en el otro; con ninguno, puede empezar en cualquier sitio y acabar donde empezó. Euler afirmó también el recíproco —que si hay como mucho dos vértices impares y el grafo está conectado, el paseo siempre existe—, pero lo dio por evidente y no lo demostró. Lo hizo Carl Hierholzer en 1873, en un artículo publicado tras su muerte y reconstruido de memoria por un colega, y su prueba es además un procedimiento para construir el recorrido, el que usan hoy los algoritmos que planifican rutas de reparto de correo o de recogida de basura, donde hay que pasar por todas las calles una vez.

La ciudad no se quedó quieta. En 1905 se construyó un octavo puente, el Kaiserbrücke, entre la isla de Lomse y la orilla sur, y con él los grados pasaron a ser tres, cinco, cuatro y cuatro: solo dos impares, así que el paseo por fin era posible, siempre que empezara en la orilla norte y terminara en Kneiphof, o al revés. El segundo botón de la figura permite encontrarlo. Los bombardeos de 1944 destruyeron dos de los puentes originales, otros dos fueron sustituidos después por una autovía, y el Kaiserbrücke se reconstruyó en 2005; el grafo de la Kaliningrado actual, con cinco puentes, tiene dos vértices impares y admite un paseo de Euler, aunque no un circuito que vuelva al inicio. El problema de los vecinos de 1735 se resolvió en dos ocasiones: una en el papel, en 1736, y otra en el terreno, en 1905.

El tercer botón, «tu propio grafo», es la parte que Euler no pudo ofrecer a sus lectores: seis vértices y quince aristas posibles que se encienden y se apagan pulsándolas. Sirve para comprobar que la regla de los grados no tiene excepciones —añadir una sola arista cambia la paridad de dos vértices a la vez, así que el número de vértices impares siempre es par— y para ver que la condición necesita también que el grafo esté conectado. Con eso, la pregunta de un paseo dominical se convierte en la primera pregunta de una disciplina: dado un conjunto de cosas y de conexiones entre ellas, qué se puede saber sin mirar las cosas y mirando solo las conexiones. El resto de este itinerario —el mundo pequeño, el umbral de Granovetter, la conexión preferencial, la epidemia en una red, el algoritmo de Dijkstra, PageRank— son respuestas a esa pregunta.

El algoritmo de Dijkstra encuentra el camino más corto entre un punto de partida y todos los demás puntos de una red cuyas conexiones tienen un coste no negativo: kilómetros entre ciudades, milisegundos entre routers, minutos entre paradas de metro. Lo publicó Edsger W. Dijkstra en 1959 en tres páginas, y sigue siendo el procedimiento que hay debajo de la mayoría de los navegadores, de los protocolos que encaminan el tráfico de internet y de casi cualquier sistema que tenga que responder a la pregunta «¿por dónde?». Su idea es tan sencilla que se puede ejecutar a mano sobre un mapa, y la figura de esta página está hecha para eso.

La regla es una sola, repetida. Se lleva una lista de distancias provisionales, que al empezar son cero para el origen e infinito para todos los demás. En cada paso se toma, de entre los nodos que aún no están fijados, el que tiene la distancia provisional más pequeña, y se declara fijada: ya no puede mejorar. Después se miran sus vecinos y, para cada uno, se comprueba si llegar a él pasando por el nodo recién fijado sale más barato que la distancia provisional que tenía; si es así, se apunta la nueva. Cuando el nodo que se fija es el destino, se ha terminado, y el camino se reconstruye hacia atrás siguiendo, desde cada nodo, el vecino por el que le llegó su mejor distancia.

Lo que hay que ver en la figura es por qué un nodo, una vez fijado, no puede mejorar. Cuando sale de la cola, su distancia provisional es la menor de todas las pendientes. Cualquier otro camino hasta él tendría que pasar por algún nodo todavía no fijado, y todos esos nodos están, por definición, al menos tan lejos como él. Como las conexiones no restan —eso es lo que significa que los costes sean no negativos—, alargar el recorrido a partir de ahí no puede acortarlo. Por eso la cola es el corazón del algoritmo y por eso la lectura de la figura la muestra en cada paso: el orden en que salen los nodos es el orden creciente de sus distancias definitivas, y lo que parece una búsqueda por el grafo es en realidad una onda que se expande desde el origen y va alcanzando los nodos por distancia.

Esa misma condición marca el límite del método. Si alguna conexión tiene coste negativo —cosa que no ocurre en mapas, pero sí en problemas de finanzas o en grafos que codifican ganancias como costes negativos—, un nodo ya fijado podría mejorarse más tarde, y Dijkstra dará respuestas equivocadas sin avisar. Para esos casos existen algoritmos más lentos, como el de Bellman-Ford, que revisan todas las conexiones varias veces. La otra limitación es que el algoritmo, en su forma original, explora en todas las direcciones por igual: para ir de Madrid a Barcelona calcula también la distancia a Badajoz, porque Badajoz está más cerca que Barcelona y sale antes de la cola. En la figura se ve cuando el destino está al otro extremo del mapa: la mitad de los nodos se fijan antes de llegar a él.

Dijkstra contó en varias ocasiones cómo se le ocurrió. En 1956 trabajaba en el Centro Matemático de Ámsterdam y tenía que preparar una demostración pública del ARMAC, el nuevo ordenador del centro, con un problema que un público no especializado pudiera entender: el camino más corto entre dos de las sesenta y cuatro ciudades de un mapa de los Países Bajos. Según relató en una entrevista de 2001 publicada por Communications of the ACM en 2010, diseñó el algoritmo una mañana en la terraza de un café, tomando un café con su prometida, en unos veinte minutos y sin papel ni lápiz, y añadió que una de las razones de su elegancia era precisamente que se había pensado sin escribir. No lo publicó hasta 1959, y lo hizo casi como una nota al margen, en el primer volumen de una revista nueva, porque en la época los algoritmos apenas se consideraban material publicable.

La eficiencia del algoritmo depende de cómo se organice la cola. La versión de 1959 recorría toda la lista de nodos para encontrar el más cercano en cada paso, lo que para una red de n nodos supone un tiempo proporcional a n². Con un montículo binario, que es la estructura que la figura simula con sus fichas ordenadas, el coste baja a algo proporcional al número de conexiones multiplicado por el logaritmo del número de nodos. Michael Fredman y Robert Tarjan introdujeron en 1984 los montículos de Fibonacci, que llevan el coste teórico a su mínimo conocido para este tipo de algoritmos, aunque en la práctica los montículos binarios suelen ser igual de rápidos por ser más simples.

Sobre Dijkstra se construyó lo que vino después. El algoritmo A*, propuesto por Peter Hart, Nils Nilsson y Bertram Raphael en 1968 para el robot Shakey del instituto de investigación de Stanford, añade a la distancia provisional de cada nodo una estimación de lo que le falta hasta el destino, de manera que la onda se expande preferentemente hacia donde interesa; es el algoritmo de los videojuegos y de la robótica. Para los mapas de carreteras de un continente, con decenas de millones de nodos, ni siquiera eso basta, y desde 2008 los navegadores usan técnicas como las jerarquías de contracción de Robert Geisberger y sus colegas, que preprocesan la red una vez para poder responder después cualquier consulta en menos de un milisegundo. Debajo de todas ellas, en algún nivel, sigue ejecutándose la regla de la terraza del café: sacar el más cercano, fijarlo, revisar a sus vecinos.

Una caché es una memoria pequeña y rápida que guarda copias de lo que se ha usado hace poco, con la apuesta de que volverá a hacer falta. La apuesta se cumple tan a menudo que la informática entera está construida sobre ella: el procesador tiene tres niveles de caché delante de la memoria, el sistema operativo guarda en memoria las páginas del disco, el navegador guarda las imágenes de las webs, y las redes de distribución de contenidos guardan copias de los vídeos cerca de quien los ve. Como la caché es pequeña, tarde o temprano se llena, y entonces hay que decidir qué copia tirar para hacer sitio. Esa decisión es la política de reemplazo, y la más usada, la que da título a esta página, es LRU: expulsar la que lleva más tiempo sin usarse, least recently used.

La figura de esta página es una caché de unos pocos huecos frente a una secuencia de trescientos accesos a sesenta elementos. La cinta superior es la secuencia: cada acceso se pinta en verde si el elemento estaba en la caché, un acierto, y en rojo si no, un fallo. Debajo, los huecos, con el elemento que ocupa cada uno y cuántas veces se ha pedido. El deslizador cambia el tamaño; el selector, la política; y el otro selector, la forma de la secuencia, que es lo que de verdad decide si una caché sirve para algo. La gráfica inferior calcula, para esta misma secuencia, la tasa de aciertos de cada política con cada tamaño de caché.

Lo primero que enseña la figura es que ninguna política sirve sin una buena secuencia. Con accesos uniformes —cada elemento igual de probable que cualquier otro— una caché de ocho huecos sobre sesenta elementos acierta alrededor del 13 % de las veces, sea cual sea la política, porque no hay nada que recordar. Con accesos tipo Zipf, en los que unos pocos elementos se piden muchísimo y la mayoría casi nunca, la misma caché acierta más de la mitad de las veces, y una de dieciséis huecos, casi tres de cada cuatro. Lee Breslau y sus colegas mostraron en 1999 que las peticiones a las páginas web siguen una distribución de ese tipo, y eso es lo que hace rentables las cachés de Internet. La propiedad se llama localidad: que lo que se acaba de usar tenga más probabilidad de volver a usarse. Peter Denning la formalizó en 1968 con el modelo del conjunto de trabajo, el grupo de páginas que un programa está usando en cada momento, y mostró que ese grupo es pequeño y cambia despacio.

Lo segundo es el caso en que LRU se equivoca sistemáticamente, que la figura llama bucle. Si un programa recorre nueve elementos en orden, una y otra vez, con una caché de ocho huecos, LRU expulsa siempre el elemento que va a hacer falta justo a continuación —el que lleva más tiempo sin usarse es, en un bucle, el siguiente de la cola— y no acierta nunca. FIFO, que expulsa el más antiguo, tampoco. La política aleatoria, que no sabe nada, acierta a veces. Y con un hueco más, nueve, todas aciertan siempre. Este comportamiento se ve en los recorridos secuenciales de ficheros grandes y en los escaneos de bases de datos, y es la razón de que las cachés reales lleven protecciones contra los barridos: Nimrod Megiddo y Dharmendra Modha propusieron en 2003 el algoritmo ARC, que reparte la caché entre lo recién llegado y lo que ya ha demostrado repetirse, y ajusta el reparto solo según cuál de las dos mitades habría acertado.

Lo tercero es la política contra la que se compara todo, que es imposible. László Bélády demostró en 1966 que la política óptima es expulsar el elemento que tardará más en volver a pedirse, lo que exige conocer el futuro; ninguna caché real puede hacerlo, pero sobre una secuencia ya grabada, como la de la figura, se puede calcular, y la curva negra es esa cota. Mide cuánto de lo que se pierde es culpa de la política y cuánto es inevitable. Daniel Sleator y Robert Tarjan probaron en 1985 el resultado que ancla la teoría: cualquier política que no conozca el futuro puede llegar a fallar k veces más que la óptima, siendo k el tamaño de la caché, y LRU alcanza exactamente ese límite, lo que significa que ninguna otra política sin información del futuro puede garantizar nada mejor en el peor caso. En el caso medio, con secuencias reales, LRU se queda bastante cerca de la óptima, y por eso es la que se usa.

Bélády encontró también algo que se conoce como su anomalía: con FIFO, agrandar la caché puede reducir los aciertos para algunas secuencias. LRU no padece eso; Mattson y sus colegas demostraron en 1970 que pertenece a la clase de los algoritmos de pila, en los que el contenido de una caché de tamaño k está siempre contenido en el de una de tamaño k + 1, de modo que la curva de aciertos según el tamaño solo puede subir, y se puede calcular de una pasada para todos los tamaños a la vez. Es exactamente lo que hace la gráfica inferior de la figura. Que la curva de LRU sea monótona y la de FIFO tenga dientes de vez en cuando es una de las cosas que se ven al ejecutar unas cuantas secuencias, y una de las razones por las que la política que tira lo menos usado recientemente es la que todo el mundo elige sin pensarlo mucho.

El filtro de Bloom es una estructura de datos que responde a la pregunta «¿he visto ya este elemento?» usando una cantidad de memoria ridícula, a cambio de equivocarse a veces en una sola dirección. Nunca dice que no ha visto algo que sí vio. Puede decir que ha visto algo que no vio, con una probabilidad pequeña y calculable. Esa asimetría lo hace perfecto como portero: antes de hacer una operación cara —consultar un disco, preguntar a otro servidor, buscar en una lista de millones de direcciones maliciosas—, se pregunta al filtro, y si dice «no» se ahorra la operación con toda seguridad; si dice «quizá», se hace la operación y se comprueba. Burton Bloom lo propuso en 1970 en cuatro páginas, y hoy está en los navegadores, en las bases de datos, en los routers y en las criptomonedas.

La figura de esta página es un filtro de Bloom entero, bit a bit. La rejilla de la izquierda es un vector de m bits, todos a cero al principio. Insertar una palabra es pasarla por k funciones hash distintas, que dan k posiciones del vector, y poner a uno esos k bits. Consultar una palabra es calcular sus mismas k posiciones y mirar: si alguno de los bits está a cero, la palabra no se ha insertado, con certeza absoluta, porque de haberse insertado ese bit estaría a uno. Si todos están a uno, la palabra probablemente se insertó, pero puede que no: puede que otros elementos, entre todos, hayan encendido por casualidad esos k bits. Eso es un falso positivo, y el botón que consulta una palabra que no está permite ir a la caza de uno.

Lo primero que se ve es cuánto cabe. El vector de 256 bits de la figura ocupa 32 bytes, lo que ocuparían cinco o seis palabras cortas escritas tal cual, y sin embargo con tres funciones hash puede guardar la huella de cuarenta palabras y responder mal a menos del 10 % de las consultas sobre palabras ausentes. Con 1.024 bits y cien palabras, el error baja del 2 %. El filtro no guarda las palabras: no se pueden recuperar de él ni recorrer, solo preguntar por una. Esa es la renuncia que compra el ahorro, y el motivo de que el filtro complemente a otras estructuras en lugar de sustituirlas.

Lo segundo es la fórmula, que la gráfica de la derecha dibuja junto a la medida real. Tras insertar n elementos con k funciones en m bits, la fracción de bits que sigue a cero es aproximadamente e^(−kn/m), y la probabilidad de que una palabra ausente encuentre sus k bits encendidos es esa fracción de bits encendidos elevada a k. La medida de la figura, hecha con quinientas palabras que no están, sigue la curva teórica con el vaivén que corresponde a una muestra de ese tamaño. La fórmula dice también cuántas funciones conviene usar: con pocas, cada palabra deja poca huella y una ausente la imita fácilmente; con muchas, el vector se llena de unos y todo parece estar. El óptimo es k = (m/n)·ln 2, unas 0,7 funciones por cada bit disponible por elemento, y con él la tasa de error es 0,6185 elevado a m/n: con diez bits por elemento, menos del 1 %. La figura calcula el óptimo para el número de palabras insertadas y avisa cuando el k elegido se aleja.

Lo tercero es de dónde salen k funciones hash. Calcular ocho funciones distintas por cada consulta sería caro, y en la práctica no hace falta. Adam Kirsch y Michael Mitzenmacher demostraron en 2008 que basta con dos funciones, h₁ y h₂, y usar h₁ + i·h₂ para i de 0 a k − 1, sin que la tasa de falsos positivos empeore de forma apreciable. Es lo que hace la figura, con dos variantes de la función FNV, y es lo que hacen la mayoría de las implementaciones.

El filtro tardó treinta años en hacerse famoso, y lo que lo lanzó fue la red. Li Fan y sus colegas propusieron en 2000 que las cachés web de una organización se intercambiaran, en lugar de la lista completa de las páginas que cada una tenía, un filtro de Bloom de esa lista: una fracción de la memoria, y a cambio alguna consulta ocasional a una caché vecina que resultaba no tener la página. Andrei Broder y Michael Mitzenmacher recopilaron en 2004 decenas de usos en redes y acuñaron el principio del filtro de Bloom: siempre que una lista o un conjunto se usen y el espacio importe, considérese un filtro de Bloom si los falsos positivos se pueden tolerar. Bigtable, la base de datos de Google descrita en 2008, guarda un filtro por cada fichero en disco para no leer ficheros que no contienen la clave buscada, y la idea se copió en casi todos los almacenes de datos posteriores. Chrome usó durante años un filtro de Bloom con las direcciones peligrosas conocidas, para consultar al servidor solo cuando el filtro decía «quizá». Bitcoin lo usa para que un cliente ligero pida a la red solo las transacciones que le pueden interesar sin revelar cuáles son.

Hay una limitación que la figura hace visible: no se puede borrar. Poner a cero los bits de una palabra apagaría también los de otras que los compartan, y el filtro empezaría a dar falsos negativos, lo único que prometía no dar. Las variantes con contadores en lugar de bits lo permiten a cambio de más memoria. Pero la versión original, la de 1970, sigue siendo la que se usa cuando lo que hay que recordar solo crece, y su lección va más allá del caso: hay preguntas cuya respuesta exacta cuesta mucho y cuya respuesta casi exacta, con el error en la dirección correcta, cuesta casi nada.

PageRank es el algoritmo con el que Google ordenó los resultados de búsqueda en sus primeros años y que le permitió desplazar a los buscadores anteriores. Su idea es que la importancia de una página web se puede medir por los enlaces que recibe, pero no contándolos sin más, sino ponderando cada uno por la importancia de la página que lo emite: un enlace desde una página muy enlazada vale más que cien enlaces desde páginas que nadie enlaza. La definición es circular a propósito —la importancia se define en términos de la importancia—, y la elegancia del método está en que esa circularidad tiene una solución única que además se calcula con facilidad.

La forma más intuitiva de entenderlo es la que sus autores llamaron el surfista aleatorio. Imagínese a alguien que navega sin criterio: en cada página elige al azar uno de los enlaces salientes y lo sigue, y de vez en cuando —con una probabilidad fija, típicamente el 15 %— se aburre y salta a una página cualquiera de toda la red. El PageRank de una página es la fracción del tiempo que ese surfista pasaría en ella si navegara eternamente. Las páginas a las que llegan muchos caminos, y caminos que a su vez son muy transitados, acumulan tiempo; las páginas a las que nadie apunta solo reciben las visitas del salto aleatorio. En la figura, el botón que suelta un surfista lo hace exactamente así, y las barras naranjas que cuentan sus visitas se van acercando, salto a salto, a las barras negras del cálculo exacto.

El cálculo directo es el que hace el botón de iterar. Se empieza dando a todas las páginas el mismo valor. En cada ronda, cada página reparte su valor actual en partes iguales entre las páginas a las que enlaza, y el nuevo valor de cada página es lo que recibe de las demás, multiplicado por 0,85, más una pequeña cantidad fija que representa al surfista que llega saltando. Al cabo de unas decenas de rondas los valores dejan de cambiar: se ha alcanzado el punto en el que cada página tiene exactamente el rango que le corresponde por los rangos de quienes la enlazan. En términos de álgebra lineal, ese vector estable es el vector propio dominante de la matriz de enlaces de la red, y el método de iterarlo se conoce desde el siglo XIX como método de las potencias. Larry Page y Sergey Brin informaron en 1998 de que para los veinticuatro millones de páginas que habían rastreado el cálculo convergía en unas cincuenta iteraciones.

El parámetro de amortiguación, la probabilidad de seguir un enlace en vez de saltar, es lo que hace que el sistema funcione, y el deslizador de la figura permite ver por qué. Sin salto aleatorio, una página sin enlaces salientes —un documento PDF, una imagen— sería un agujero: el surfista llegaría y no podría irse, y todo el rango de la red acabaría escurriéndose por ahí. La red preconfigurada con un callejón sin salida lo muestra: con la amortiguación cerca de 1 el rango se acumula en el circuito cerrado y el resto de la red se vacía. Con el 15 % de saltos, el surfista sale del atolladero y la distribución se reparte. Brin y Page eligieron 0,85 sin más justificación que la de que funcionaba bien, y el valor se ha mantenido en casi toda la literatura posterior.

La red llamada «granja de enlaces» ilustra la primera manera de engañar al algoritmo, y por qué no funciona tan bien como parece. Un grupo de páginas que se enlazan mutuamente en círculo se pasa el rango de una a otra sin perderlo, y si alguna de ellas recibe además un enlace del exterior, todo el grupo se infla. Pero el rango que un grupo puede retener está limitado por el salto aleatorio, que se lo va llevando en cada ronda, y una granja aislada acumula poco más de lo que le corresponde por su tamaño. Las estrategias que sí funcionaron durante años —comprar enlaces en páginas ya importantes, colar comentarios con enlace en blogs ajenos— atacaban la premisa del modelo, no su matemática: el algoritmo supone que un enlace es un voto sincero de quien lo pone, y eso dejó de ser cierto en cuanto los enlaces empezaron a valer dinero.

La idea no era nueva cuando Page y Brin la aplicaron a la web. Leo Katz había propuesto en 1953 medir el prestigio de una persona en una red social por las personas que la nombraban, ponderadas por el prestigio de estas. Gabriel Pinski y Francis Narin habían hecho lo mismo en 1976 con revistas científicas, resolviendo el mismo problema de vector propio para decidir qué revista de física era más influyente contando citas ponderadas por la influencia de quien cita. Lo que aportó PageRank fue aplicarlo a una red de cientos de millones de nodos que crecía sin control, demostrar que el cálculo era factible a esa escala y, sobre todo, convertirlo en un producto. La patente, presentada en 1998 a nombre de Page y propiedad de la Universidad de Stanford, se licenció en exclusiva a Google; Stanford vendió las acciones que recibió a cambio en 2005 por 336 millones de dólares.

PageRank dejó de ser el criterio dominante de Google hace tiempo. Los sistemas actuales combinan cientos de señales —el texto, la conducta de los usuarios, la frescura, la autoridad temática— y la barra verde que mostraba el PageRank de cada página en la barra de herramientas del navegador desapareció en 2016. Pero el algoritmo sobrevive fuera del buscador, en todos los sitios donde una red de referencias necesita convertirse en una lista ordenada: para identificar las proteínas más importantes de una red metabólica, los artículos científicos más influyentes de un campo, las especies clave de un ecosistema o las calles más transitables de una ciudad. En todos esos casos la pregunta es la misma que se hicieron dos estudiantes de doctorado en Stanford: dado quién apunta a quién, ¿quién importa?