Estructuras de datos que se ven

La notación O grande (en inglés, big O notation) 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 (linear search) 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 (complexity) 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 (worst case), 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 (quadratic) 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.

La búsqueda binaria – La recursividad – La criba de Eratóstenes – El montículo binario

La pila (en inglés, stack) y la cola (queue) son las dos estructuras de datos más simples que existen después de la lista, y se distinguen por una sola regla. En la pila, el último elemento que entra es el primero que sale, como en un montón de platos: el que se pone encima es el que se retira primero. En la cola, el primero que entra es el primero que sale, como en la fila de una panadería. Las siglas inglesas LIFO (last in, first out) y FIFO (first in, first out) resumen las dos reglas, y se usan también fuera de la informática, en la contabilidad de almacenes, para decidir qué unidad se da por vendida cuando salen existencias.

La figura de esta página tiene las dos lado a lado. Cada botón «Meter» añade una ficha numerada y cada «Sacar» retira una: la pila devuelve siempre la última ficha que entró y la cola, la más antigua. Es todo lo que hacen. Ninguna de las dos permite mirar la tercera ficha, ni sacar una del medio, ni buscar un número; a cambio, meter y sacar cuestan lo mismo con tres fichas que con tres millones, porque las dos operaciones solo tocan un extremo.

La pila está en más sitios de los que parece. El botón de deshacer de cualquier programa guarda los cambios en una pila y retira el más reciente; el botón de atrás del navegador hace lo mismo con las páginas visitadas. Un editor de código comprueba que los paréntesis cierran bien metiendo cada paréntesis de apertura en una pila y sacando uno por cada cierre: si al final queda algo dentro, o si hay que sacar de una pila vacía, la expresión está mal. Y, sobre todo, la pila es lo que permite que una función llame a otra. Cada vez que un programa entra en una función, el ordenador apunta en la pila de llamadas (call stack) dónde tiene que volver cuando termine, junto con sus variables locales; la función que entró la última es la que termina primero, y por eso una pila es exactamente la estructura que hace falta. La recursividad es ese mecanismo llevado al límite, y el error que da un programa que se llama a sí mismo sin parar, el desbordamiento de pila (stack overflow), es tan corriente que da nombre al mayor foro de programadores del mundo. Cómo se ve esa pila mientras un programa corre lo enseña Del código al proceso.

La idea apareció varias veces. Alan Turing, en el informe de 1946 en el que proponía el ordenador ACE, describió dos operaciones que llamó «enterrar» y «desenterrar» (bury y unbury) para guardar la dirección de vuelta de una subrutina y recuperarla después, que es la pila de llamadas con otro nombre. Friedrich Bauer y Klaus Samelson, en Múnich, llegaron a ella por otro camino en 1955: traducir una fórmula como 3 + 4 × 5 a instrucciones de máquina exige dejar el «+» esperando hasta que el «×», que tiene prioridad, se resuelva, y lo que espera se guarda en lo que llamaron un sótano (Keller). Patentaron el principio en 1957 y lo publicaron en 1959 y 1960. Edsger Dijkstra lo usó en 1960 para implementar las funciones recursivas del lenguaje ALGOL 60, y desde entonces casi todos los lenguajes de programación funcionan sobre una pila.

La cola tiene menos leyenda y más oficio. Es la estructura de todo lo que debe atenderse por orden de llegada: los trabajos que esperan a la impresora, las teclas pulsadas antes de que el programa las lea, los mensajes entre dos programas que van a ritmos distintos, los paquetes que un router recibe más deprisa de lo que puede reenviar. El sistema operativo reparte el procesador entre programas con colas, y la búsqueda en anchura explora un laberinto con una. La virtud de la cola es la justicia: nadie espera para siempre, porque todo lo que entra acaba saliendo en su turno. Cuando hace falta que salga primero lo más urgente y no lo más antiguo, la cola se convierte en una cola de prioridad, que es lo que hace el montículo binario.

Las dos se construyen sobre cualquier lista. La pila es casi inmediata: un vector y un número que dice cuántas fichas hay; meter escribe en la siguiente posición libre y sacar lee la última ocupada. La cola tiene una trampa, porque sacar el primer elemento de un vector obliga a desplazar todos los demás una posición, y eso cuesta tanto como larga es la cola. La solución clásica es el búfer circular (ring buffer): dos índices, uno para la cabeza y otro para el final, que avanzan por un vector de tamaño fijo y vuelven al principio cuando llegan al borde, de manera que nada se mueve nunca de sitio. Es lo que hay dentro de casi todos los dispositivos que reciben datos a ráfagas. Con una lista enlazada las dos salen con la misma facilidad, a cambio de más memoria por elemento. Donald Knuth reunió pila, cola y la cola de dos extremos (deque) en el primer volumen de The Art of Computer Programming, en 1968, y las trató como variantes de una sola idea, la lista a la que solo se accede por los bordes.

Lo que enseñan las dos es que una limitación puede ser una virtud. Una pila no es una lista a la que le faltan operaciones, sino una lista que promete un orden, y esa promesa es lo que la hace útil: quien usa una pila sabe que lo que saca es lo último que metió sin tener que comprobarlo. Elegir entre una pila y una cola es elegir a qué se atiende primero, si a lo más reciente o a lo más antiguo, y esa decisión, tomada en una línea, cambia el comportamiento entero de un programa.

La lista enlazada – La recursividad – El montículo binario – La búsqueda en anchura y en profundidad – Del código al proceso

La lista enlazada (en inglés, linked list) guarda una serie de datos en celdas que pueden estar en cualquier sitio de la memoria, porque cada celda lleva, junto al dato, la dirección de la siguiente. Esa dirección es un puntero (pointer), y la lista entera no es más que la dirección de la primera celda, la cabeza. Para leer la lista se empieza por ella y se va saltando de puntero en puntero hasta la última, que apunta a nada. Es lo contrario del vector (array), que pone todos los datos seguidos en memoria y encuentra el elemento k multiplicando: la dirección del primero más k veces el tamaño de cada uno.

La figura de esta página pone las dos estructuras una encima de otra, con los mismos números, y permite hacerles las dos cosas que las separan. Insertar un dato en la posición k obliga al vector a desplazar una celda a la derecha todos los elementos que vienen después, y a la lista solo a recorrer k celdas y recolocar dos punteros. Leer el elemento de la posición k le cuesta al vector un paso, y a la lista, k. La figura cuenta las operaciones de cada uno en cada jugada.

Lo que la figura resume es un intercambio sin trampa. Lo que a uno le cuesta un paso, al otro le cuesta tantos como elementos haya, y al revés. Por eso la elección depende de qué se va a hacer más: un programa que lee posiciones al azar quiere un vector, y uno que inserta y quita constantemente por el medio, mientras recorre, quiere una lista. Hay variantes para afinar: la lista doblemente enlazada (doubly linked list), en la que cada celda apunta también a la anterior y se puede recorrer en los dos sentidos, y la lista circular, en la que la última vuelve a la primera. En todas ellas, borrar una celda que ya se tiene a mano cuesta un paso, porque basta con que la anterior apunte a la siguiente, y en el vector cuesta desplazar el resto.

La idea nació con la inteligencia artificial. Allen Newell, Cliff Shaw y Herbert Simon la inventaron en 1956 para el Logic Theorist, el programa que demostraba teoremas de lógica, y la hicieron el centro de su lenguaje IPL: necesitaban guardar fórmulas cuya longitud no se sabía de antemano y que crecían y se partían mientras el programa razonaba, algo que un vector de tamaño fijo hace muy mal. John McCarthy la tomó para Lisp, el lenguaje que presentó en 1960 y cuyo nombre viene de list processing. En Lisp todo es una lista de celdas de dos punteros, llamados car y cdr por los nombres de dos partes de la palabra de memoria del IBM 704 en el que se escribió, y hasta el propio programa es una lista, que es lo que hacen visible sus paréntesis. Como las celdas se creaban y abandonaban sin parar, McCarthy tuvo que inventar también quién las recogiera, y así nació el recolector de basura.

Hoy la lista enlazada está debajo de cosas que no la nombran. La pila y la cola se construyen sobre ella con naturalidad. Cada casilla de una tabla hash suele ser una lista corta con las claves que han caído en ella. El historial de deshacer de un editor, la lista de ventanas abiertas de un sistema operativo, los bloques libres de un disco o los procesos que esperan turno son listas enlazadas, y el núcleo de Linux lleva una pequeña cabeza de lista, con los punteros al anterior y al siguiente, dentro de casi todas sus estructuras. El motivo es siempre el mismo: no saber cuántos elementos habrá, ni en qué orden entrarán y saldrán.

El inconveniente moderno no se ve en la figura, porque la figura cuenta pasos y no tiempo. En un ordenador actual leer un dato que está en la memoria caché del procesador cuesta alrededor de un nanosegundo, y uno que hay que ir a buscar a la memoria principal, cerca de cien, como enseñan las latencias de un ordenador. Las celdas de un vector están juntas, así que cuando el procesador trae una trae también las vecinas; las de una lista están repartidas por donde cayeron al crearse, y cada salto de puntero puede ser un viaje a la memoria principal. Ulrich Drepper lo documentó en 2007 en un informe que se convirtió en lectura obligada. Bjarne Stroustrup, el autor de C++, llevaba a sus charlas una medición que incomoda a los manuales: para insertar números en orden en una secuencia de unos pocos miles de elementos, el vector gana a la lista aunque tenga que desplazar celdas, porque el tiempo se va en recorrer hasta el sitio y el vector recorre mucho más deprisa. La lista sigue ganando cuando los elementos son grandes, cuando ya se tiene la celda a mano o cuando nada puede moverse de sitio, pero ya no es la elección por defecto que fue durante cuarenta años.

Lo que queda de ella es la idea, que es más importante que la estructura: un dato puede guardar dónde está otro. Esa indirección es el átomo de todas las estructuras que vinieron después. Un árbol binario es una lista en la que cada celda apunta a dos, y un grafo, una en la que apunta a cuantas haga falta. Entender la lista enlazada es entender que la memoria no tiene por qué parecerse al orden de las cosas que guarda.

La pila y la cola – La tabla hash – El árbol binario de búsqueda – Las latencias de un ordenador – El recolector de basura

Los algoritmos de ordenación (en inglés, sorting algorithms) 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 (bubble sort) y la ordenación por inserción (insertion sort) 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 (merge sort) y la ordenación rápida (quicksort) 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 (stable), 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 (pivot), 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 búsqueda binaria – El montículo binario – La notación O grande

La búsqueda binaria (en inglés, binary search) es la manera de encontrar un dato en una lista ordenada mirando primero el elemento del medio. Si es el buscado, se acabó. Si es mayor, el dato solo puede estar en la mitad izquierda, y si es menor, en la derecha; en cualquiera de los dos casos, media lista queda descartada con una sola comparación, y el procedimiento se repite sobre la mitad que queda. Es lo que hace cualquiera que busca una palabra en un diccionario de papel sin leerlo desde la primera página, y lo que hace el juego de adivinar un número entre uno y cien con pistas de «más alto» y «más bajo»: siete preguntas bastan siempre.

La figura de esta página hace la búsqueda paso a paso. Arriba está la lista, que puede tener quince elementos, cien, mil, un millón o mil millones. Debajo, cada fila es un paso: la franja naranja es la zona donde el número todavía puede estar, y la raya negra, el elemento del medio que se consulta. Cada fila mide la mitad que la anterior. Con mil elementos la búsqueda no pasa nunca de diez pasos; con un millón, de veinte, y con mil millones, de treinta. Buscar uno que no está cuesta lo mismo, porque la búsqueda termina cuando la franja se queda vacía, y esa es su otra virtud: dice con la misma rapidez que algo no existe y dónde habría que insertarlo para que la lista siguiera ordenada.

La cuenta que hay detrás es el logaritmo en base dos. Partir n elementos por la mitad hasta quedarse con uno exige log₂ n cortes, y como cada comparación reduce la zona a la mitad como poco, el número de pasos en el peor caso es ⌈log₂(n + 1)⌉. Es la curva que la notación O grande llama logarítmica, y su propiedad más útil se ve cambiando el tamaño en la figura: multiplicar la lista por mil añade unas diez comparaciones. Una búsqueda lineal (linear search), que mira los elementos uno por uno, necesita en promedio la mitad de la lista, y la figura dice cuántos habría mirado en cada caso. Para mil millones de elementos, la diferencia es de treinta consultas contra quinientos millones.

Tampoco se puede hacer mejor usando solo comparaciones. Cada comparación responde con una de pocas salidas, y para distinguir entre n posiciones posibles hacen falta, como mínimo, log₂ n respuestas de un bit. La búsqueda binaria alcanza ese límite, y por eso es el patrón con el que se miden las demás estructuras de búsqueda: el árbol binario de búsqueda es una búsqueda binaria guardada en forma de nodos, que funciona mientras el árbol está equilibrado, y la tabla hash consigue ir más deprisa precisamente porque no compara, sino que calcula dónde está cada cosa.

El precio está en la condición de partida. La lista tiene que estar ordenada, y ordenarla cuesta del orden de n log n operaciones, como enseñan los algoritmos de ordenación. Solo compensa si se va a buscar muchas veces, o si los datos llegan ordenados de por sí, como las fechas de un registro o las palabras de un diccionario. Además, hay que poder saltar directamente al elemento del medio, lo que es inmediato en un vector guardado en memoria contigua y en un fichero ordenado, pero imposible en una lista enlazada (linked list), que hay que recorrer desde el principio para llegar a cualquier posición.

La idea es antigua. John Mauchly la describió en 1946, en las conferencias de la Moore School de Filadelfia que fueron el primer curso sobre ordenadores electrónicos, y Donald Knuth, que reconstruyó su historia en el tercer volumen de The Art of Computer Programming en 1973, señaló lo que ocurrió después: las versiones que se publicaron durante más de una década solo funcionaban con listas de ciertas longitudes. Se quedaban en un bucle infinito cuando la zona tenía dos elementos, o se saltaban el último. Knuth atribuye a Derrick Lehmer, en 1960, la primera publicada que era correcta para cualquier tamaño, y a Hermann Bottenbruch, en 1962 y en un artículo sobre el lenguaje ALGOL 60, una variante que deja la comprobación de igualdad para el final y ahorra una comparación en cada vuelta.

Jon Bentley convirtió esa dificultad en una prueba. Contó en su columna de 1983 en Communications of the ACM que había pedido a programadores profesionales, en cursos de Bell Labs e IBM, que escribieran una búsqueda binaria con un par de horas de plazo y en el lenguaje que prefirieran, y que alrededor del noventa por ciento acabó encontrando errores en su propio programa. Los errores no estaban en la idea sino en los bordes: si la zona se cierra con alto igual al medio o con el medio menos uno, si el bucle sigue mientras bajo es menor o menor o igual que alto. Bentley usó el caso para defender que los programas se razonaran con invariantes (invariants), una afirmación que es cierta al empezar cada vuelta del bucle; aquí, que si el dato está en la lista, está entre bajo y alto.

La historia tuvo una coda veintitrés años después. En 2006, Joshua Bloch contó en el blog de investigación de Google que la búsqueda binaria que él mismo había escrito para la biblioteca estándar (standard library) de Java, y la que Bentley había demostrado correcta en su libro, fallaban con listas de más de unos mil millones de elementos. El problema estaba en una línea que parece inocente, la que calcula el medio como (bajo + alto) / 2: con enteros de 32 bits, la suma se desborda (overflows) en cuanto pasa de 2³¹ − 1, lo que puede ocurrir si la lista tiene más de 2³⁰ elementos, y el medio sale negativo. El fallo había estado nueve años en la biblioteca sin que nadie lo notara, porque en la década de 1980 una lista así era inconcebible y en la de 2000 empezaba a ser corriente. La corrección es bajo + (alto − bajo) / 2, que es la que usa la figura. La demostración de Bentley no estaba mal: suponía enteros matemáticos, y los ordenadores no los tienen.

Hoy la búsqueda binaria está en casi todas partes y casi nunca se ve. La usan las bases de datos para localizar una clave dentro de cada página de un índice, los sistemas de control de versiones (version control) como Git para encontrar el cambio que introdujo un fallo entre miles de versiones probando la del medio, y cualquier programa que calcula una raíz o un umbral acotando el intervalo donde tiene que estar la respuesta. En todos los casos funciona la misma observación de 1946: cuando las cosas están en orden, cada pregunta bien hecha vale por la mitad de todas las que quedan.

El montículo binario – La recursividad – Las bases de datos relacionales

La tabla hash (en inglés, hash table) es la estructura de datos (data structure) 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 (hash function); 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 (collision).

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 (chaining), 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 (open addressing), 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 (load factor), 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.

La búsqueda binaria – El árbol binario de búsqueda – El filtro de Bloom – La función hash criptográfica

El árbol binario de búsqueda (en inglés, binary search tree) es una estructura de datos (data structure) 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 (root), 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 (rotation): 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 montículo binario – La búsqueda binaria – Las bases de datos relacionales – La tabla hash

El montículo binario (en inglés, binary heap) es una estructura de datos (data structure) que hace una sola cosa, y la hace deprisa: tener siempre a mano el elemento más pequeño de un conjunto que no deja de cambiar. Se pueden meter elementos en cualquier orden y sacar el mínimo en cualquier momento, y las dos operaciones cuestan un número de pasos proporcional al logaritmo del tamaño, unos veinte para un millón de elementos. Es lo que se necesita para una cola de prioridad (priority queue), en la que no sale el primero que llegó sino el más urgente, y por eso el montículo está dentro de los planificadores de los sistemas operativos, de los simuladores que procesan eventos por orden de hora, del algoritmo de Dijkstra que calcula rutas y del árbol con que se construye la codificación de Huffman.

Su regla es más débil de lo que parece. Un montículo es un árbol binario en el que cada padre es menor o igual que sus dos hijos, y nada más: no dice nada sobre el orden entre hermanos ni entre primos. De esa regla se deduce que el mínimo está en la raíz, porque es menor que sus hijos, que son menores que los suyos, y así hasta abajo. Pero el resto del árbol puede estar bastante desordenado, y esa es la clave de su eficiencia. Un árbol binario de búsqueda mantiene un orden total, a la izquierda lo menor y a la derecha lo mayor, y paga por ello; el montículo solo mantiene el orden a lo largo de cada camino de la raíz a una hoja, que es lo justo para saber dónde está el mínimo.

La figura de esta página dibuja el mismo montículo dos veces. Arriba está el árbol, con la raíz en negro. Abajo está la memoria: una lista corriente en la que los nodos se guardan nivel a nivel, de izquierda a derecha. No hacen falta punteros, porque el árbol está siempre completo, todos los niveles llenos salvo el último, que se llena por la izquierda, y así la posición de cada nodo determina la de su familia: los hijos del elemento que ocupa la posición i están en 2i + 1 y 2i + 2, y su padre en la mitad de i − 1, redondeando hacia abajo. Moverse por el árbol es hacer esas cuentas, y un montículo de un millón de elementos ocupa exactamente un millón de casillas.

Meter un elemento es ponerlo en la primera casilla libre, al final de la lista, que en el árbol es el primer hueco del último nivel. Probablemente eso rompe la regla, así que el nuevo se compara con su padre y, si es menor, se intercambian; y otra vez con el nuevo padre, y así hasta que encuentra uno menor o llega a la raíz. Se llama flotar o subir, y como el árbol completo de n elementos tiene log₂ n niveles, no puede costar más que ese número de intercambios. Sacar el mínimo es la operación simétrica: se retira la raíz, el último elemento de la lista ocupa su lugar y se hunde, cambiándose en cada nivel por el menor de sus dos hijos, hasta que los dos son mayores que él. La figura cuenta las comparaciones y los intercambios de cada operación, y con treinta y un elementos, cinco niveles, nunca pasan de unos pocos.

Si se sacan todos los elementos uno tras otro, salen ordenados. Esa observación es de donde nació la estructura: J. W. J. Williams la publicó en 1964 en Communications of the ACM, con el nombre de heap, como pieza de un algoritmo de ordenación que llamó heapsort. El método mete todos los datos en el montículo y los saca de uno en uno, y como cada salida cuesta log₂ n pasos, el total es del orden de n log n, el mínimo posible para una ordenación por comparaciones. Tiene dos virtudes que los algoritmos de ordenación más populares no reúnen a la vez: ese coste está garantizado incluso en el peor caso, y la ordenación se hace sobre la misma lista, sin memoria adicional, porque cada mínimo que sale deja libre la casilla del final donde se puede guardar.

Robert Floyd mejoró el método unos meses después, en el mismo año y la misma revista. Su observación fue que no hace falta construir el montículo metiendo los elementos de uno en uno. Se pueden echar todos a la lista tal como vienen y después arreglar el árbol desde abajo, hundiendo cada padre empezando por el último que tiene hijos y terminando por la raíz. Parece la misma cantidad de trabajo, pero no lo es: la mitad de los nodos son hojas y no se hunden nada, una cuarta parte baja como mucho un nivel, una octava parte dos, y la suma de todo eso no pasa de n. Construir el montículo de Floyd cuesta un tiempo lineal garantizado, y la figura permite compararlo con el método ingenuo: con quince números al azar, Floyd hace unos ocho intercambios y las quince inserciones, unos once. Con datos al azar las dos maneras acaban siendo lineales en promedio; la diferencia está en el peor caso, cuando los datos llegan en orden inverso y cada nuevo elemento tiene que subir hasta la raíz, lo que devuelve las inserciones sucesivas al orden de n log n.

Hay operaciones que el montículo no hace bien, y conviene saberlas. Buscar un elemento cualquiera exige recorrer la lista entera, porque la regla no dice en qué rama puede estar. Tampoco es barato ver el máximo de un montículo de mínimos, que puede ser cualquiera de las hojas. Algunos algoritmos necesitan además rebajar la prioridad de un elemento que ya está dentro, y Dijkstra lo hace cada vez que encuentra un camino más corto hacia un nodo; en un montículo binario eso cuesta log₂ n pasos si se sabe dónde está el elemento. Michael Fredman y Robert Tarjan presentaron en 1984 los montículos de Fibonacci, que rebajan una prioridad en tiempo constante en promedio y bajan el coste teórico de Dijkstra, aunque sus constantes son tan grandes que en la práctica los binarios suelen seguir ganando.

El nombre invita a una confusión. En los lenguajes de programación también se llama montículo, o heap, a la zona de memoria donde se guardan los datos que el programa pide durante su ejecución, y las dos cosas no tienen nada que ver más allá de la palabra. El montículo de esta página es mucho más modesto y mucho más antiguo que casi todo lo que lo usa: una lista con una regla sobre los padres y los hijos, que Python ofrece en el módulo heapq, Java en PriorityQueue y C++ en priority_queue, casi sin cambios respecto a la de 1964.

La búsqueda binaria – La notación O grande

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.

Arista

La búsqueda en anchura (en inglés, breadth-first search) y la búsqueda en profundidad (depth-first search) son las dos maneras básicas de recorrer un grafo, es decir, cualquier conjunto de cosas conectadas: las casillas de un laberinto, las páginas de la web, los amigos de los amigos, las carpetas de un disco. Las dos parten de un punto y visitan todo lo que se alcanza desde él, pero en orden distinto. La anchura avanza por capas: primero los vecinos del punto de partida, luego los vecinos de esos vecinos, y así hacia fuera, como la onda de una piedra en un estanque. La profundidad sigue un camino hasta que no puede más, retrocede hasta la última bifurcación en la que quedaba algo por probar y continúa por ahí.

La figura de esta página es un laberinto con la salida abajo a la derecha. Las dos búsquedas pintan las casillas en el orden en que las visitan y, cuando llegan a la salida, dibujan el camino que han encontrado. La anchura encuentra siempre el más corto, porque llega a cada casilla por la capa más cercana a la entrada; la profundidad encuentra uno, a veces mucho más largo, y a veces habiendo mirado menos casillas. Ni una ni otra se pierde ni repite casilla, porque las dos marcan lo que ya han visto.

Lo sorprendente es que el programa es el mismo salvo por una pieza. Las dos búsquedas guardan en algún sitio las casillas que han descubierto y aún no han explorado, y sacan de ahí la siguiente. Si ese sitio es una cola, la siguiente es la más antigua, las casillas se exploran por orden de descubrimiento y la búsqueda es en anchura. Si es una pila, la siguiente es la más reciente, el algoritmo se mete por lo último que vio y la búsqueda es en profundidad. La pila y la cola explica por qué una sola regla cambia tanto. Lo demás, marcar lo visitado y apuntar desde dónde se llegó a cada casilla para reconstruir el camino, es idéntico, y el coste también: cada casilla se visita una vez y cada pasillo se mira dos, así que las dos búsquedas son lineales en el tamaño del grafo, como diría la notación O grande.

La anchura es la herramienta del camino más corto cuando todos los pasos cuestan lo mismo. Edward Moore la describió en 1959 para el problema del laberinto, y C. Y. Lee la publicó en 1961 para un uso muy concreto: trazar las pistas de una placa de circuito impreso esquivando las que ya están puestas, un algoritmo que aún se enseña con su nombre y que sigue en el fondo de los programas que diseñan chips. Con ella se calculan los grados de separación en una red social, se encuentra la mejor jugada en un rompecabezas de pocos movimientos y se sabe qué páginas están a dos clics de otra. Si los pasos tienen pesos distintos, un kilómetro por autopista y otro por camino, la cola ya no basta: hay que sacar siempre lo más cercano y no lo más antiguo, y eso es el algoritmo de Dijkstra, que es una búsqueda en anchura con un montículo en el lugar de la cola.

La profundidad es más antigua y más versátil. Charles Pierre Trémaux, ingeniero de telégrafos, describió en el siglo XIX una regla para salir de cualquier laberinto marcando los pasillos por los que se pasa, que Édouard Lucas recogió en sus Récréations mathématiques en 1882 y que es exactamente una búsqueda en profundidad hecha a pie. Robert Tarjan demostró en 1972 que, bien hecha, da en tiempo lineal respuestas que parecen más difíciles: si un grafo tiene ciclos, en qué piezas se descompone, en qué orden hay que hacer tareas que dependen unas de otras, qué nodos lo partirían en dos si se quitaran. La razón es que la profundidad se escribe de forma natural con recursividad, una función que se llama a sí misma por cada vecino, y la pila de llamadas hace de pila sin que nadie la programe. Explorar las carpetas de un disco, resolver un sudoku probando cifras y deshaciendo, o buscar jugadas en un juego hasta cierta profundidad, es búsqueda en profundidad.

Las dos tienen un punto débil y es el contrario. La anchura tiene que recordar la capa entera que está explorando, que en una cuadrícula crece con el perímetro y en una red social puede ser de millones de personas a tres pasos de alguien; la profundidad solo recuerda el camino actual, pero en un grafo infinito o enorme puede meterse por una rama y no volver nunca. Por eso los rastreadores que indexan la web avanzan en anchura desde un puñado de páginas semilla, para cubrir mucho antes de cubrir hondo, y los programas de ajedrez exploran en profundidad hasta un límite que van subiendo, una idea llamada profundización iterativa que combina lo mejor de las dos. Y el recolector de basura de un lenguaje de programación hace una de estas búsquedas cada vez que decide qué memoria sigue en uso: lo alcanzable desde las variables vivas se queda, lo demás se tira.

Lo que queda, al final, es una moraleja sobre la atención. Un laberinto no cambia según cómo se lo recorra, pero el recorrido cambia lo que se encuentra primero. Explorar en anchura es ser paciente y completo; en profundidad, comprometerse con una idea hasta agotarla. Las dos encuentran la salida. Una la encuentra más cerca y la otra, a menudo, antes.

La pila y la cola – El algoritmo de Dijkstra – La recursividad – El montículo binario – El recolector de basura

El algoritmo de Dijkstra (en inglés, Dijkstra’s algorithm) encuentra el camino más corto (shortest path) 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 (node) 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 (graph) 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.

El montículo binario

La programación dinámica (en inglés, dynamic programming) es una manera de resolver problemas que se descomponen en problemas más pequeños del mismo tipo, cuando esos problemas pequeños se repiten. La regla es una: resolver cada uno una sola vez y apuntar la respuesta, de modo que la segunda vez que haga falta se lea en lugar de calcularse. Lo de «programación» no tiene que ver con escribir código; en los años cincuenta la palabra significaba planificación, como en la programación lineal, y se ha quedado por costumbre.

La figura de esta página usa el ejemplo más pequeño que lo enseña todo. Una escalera de n peldaños se sube de uno en uno o de dos en dos; de cuántas maneras distintas se puede llegar arriba. Para llegar al peldaño n se viene del n − 1 o del n − 2, así que las maneras de llegar a n son las de llegar a n − 1 más las de llegar a n − 2. Escrito tal cual, como una función recursiva, el programa funciona, y la figura dibuja el árbol de llamadas que produce: cada rama vuelve a calcular escaleras que otra rama ya había calculado, y las repeticiones, pintadas del mismo color, son casi todo el árbol. Debajo, la misma cuenta hecha con una tabla de n casillas rellenada de izquierda a derecha, en la que cada casilla se escribe una vez.

La diferencia no es de estilo sino de orden de magnitud. El árbol crece como una potencia: para diez peldaños tiene 177 nodos, para veinte, casi 22.000, y para cuarenta, más de 330 millones, con los que un ordenador tarda segundos en algo que debería ser instantáneo. La tabla tiene n casillas. Es el salto que la notación O grande describe como pasar de exponencial a lineal, y lo único que ha cambiado es que no se calcula dos veces lo mismo. Hay dos formas de conseguirlo. La primera, llamada memorización (memoization, con una sola «r», por memorándum), deja la función recursiva como está y le añade un diccionario donde mira antes de calcular y apunta después. La segunda construye la tabla desde los casos más pequeños hacia arriba, sin recursividad, como hace la figura; suele ser más rápida y gasta menos pila de llamadas, a cambio de obligar a pensar el orden en que se rellena.

Para que la técnica funcione hacen falta dos condiciones, y Richard Bellman las formuló en la RAND Corporation a principios de los años cincuenta mientras estudiaba cómo tomar decisiones en varias etapas. La primera es que el problema grande se resuelva a partir de soluciones óptimas de problemas más pequeños, lo que llamó principio de optimalidad: el mejor camino de A a C que pasa por B contiene el mejor camino de A a B. La segunda es que esos problemas pequeños se repitan, porque si cada uno fuera distinto no habría nada que reutilizar. Bellman publicó la teoría en 1954 y el libro en 1957, y contó en su autobiografía de 1984 de dónde salió el nombre: el secretario de Defensa de la época, Charles Wilson, detestaba la palabra «investigación» y más aún «matemáticas», así que eligió «programación» por respetable y «dinámica» porque, decía, era imposible usarla en sentido peyorativo. La historia quizá esté adornada, pero el nombre se quedó.

Lo que la escalera enseña en pequeño está en herramientas de uso diario. El corrector ortográfico que propone «ejemplo» cuando se escribe «ejmeplo» calcula la distancia de edición entre las dos palabras, el número mínimo de letras que hay que insertar, borrar o cambiar, con una tabla de dos dimensiones que Robert Wagner y Michael Fischer describieron en 1974; la misma tabla, con otros pesos, alinea dos secuencias de ADN. La función que compara dos versiones de un fichero en el control de versiones busca la subsecuencia común más larga con una tabla parecida. El receptor de un teléfono móvil decodifica la señal con el algoritmo de Viterbi, que es programación dinámica sobre los estados posibles del emisor. Y TeX, el sistema de composición de Knuth, decide dónde cortar cada párrafo en líneas minimizando la fealdad total del párrafo entero, no de cada línea, con una tabla que recorre todos los puntos de corte posibles. El algoritmo de Dijkstra también la cumple: la distancia a cada nodo se fija una vez y se reutiliza para calcular la de los siguientes.

La técnica tiene límites. El primero es la memoria, porque la tabla hay que guardarla, y en problemas con muchas variables crece hasta no caber en ningún ordenador; Bellman bautizó eso también, la maldición de la dimensionalidad. El segundo es que no todo se descompone. Para el problema del viajante, Michael Held y Richard Karp encontraron en 1962 una programación dinámica que lo resuelve en un tiempo del orden de n² por 2 elevado a n, muchísimo mejor que probar todas las rutas, pero exponencial igualmente, y sesenta años después sigue siendo el mejor método exacto general que se conoce. La programación dinámica no convierte lo imposible en fácil; convierte en fácil lo que solo parecía difícil porque se estaba repitiendo.

Esa es la lección que vale fuera de la informática. Antes de calcular, preguntarse si esto ya se calculó; antes de empezar un problema grande, preguntarse de qué problemas pequeños se compone y cuáles de ellos se parecen entre sí. La escalera de la figura tiene, para treinta peldaños, más de un millón de maneras de subirse, y la tabla las cuenta en treinta sumas.

La recursividad – La notación O grande – El algoritmo de Dijkstra – El problema del viajante – El control de versiones

El problema del viajante (en inglés, travelling salesman problem, TSP) pide lo siguiente: dadas unas ciudades y la distancia entre cada par, encontrar el recorrido más corto que pase por todas una sola vez y vuelva al punto de partida. Se enuncia en una frase, cualquiera lo entiende y nadie sabe resolverlo deprisa. Con n ciudades hay (n − 1)! / 2 recorridos posibles, y la cuenta se dispara: diez ciudades dan 181.440 rutas, quince, más de cuarenta mil millones, y veinte, unos sesenta mil billones. Probarlas todas deja de ser una opción antes de que el mapa deje de caber en una servilleta.

La figura de esta página reparte ciudades al azar y prueba tres estrategias. «Vecino más cercano» hace lo que haría una persona con prisa: ir siempre a la ciudad más próxima que quede por visitar. «Mejorar» toma esa ruta y deshace cruces: cada vez que dos tramos se cortan, cambiarlos por los dos que no se cortan acorta el recorrido, y se repite hasta que no quedan cruces. «Óptimo» calcula el mejor recorrido de verdad, lo que la figura solo puede permitirse porque hay pocas ciudades. La lectura compara las tres longitudes y dice cuántas rutas había.

Lo primero que enseña la figura es que lo fácil no es tan malo. El vecino más cercano da rutas un veinte o un veinticinco por ciento más largas que la óptima, de media, y suele terminar con un tramo larguísimo de vuelta a casa, porque ha ido dejando atrás ciudades aisladas. Deshacer cruces, un método que se llama 2-opt y que se conoce desde los años cincuenta, recorta buena parte de esa diferencia. Lo segundo es que el óptimo no se puede comprobar mirando: una ruta sin cruces y de aspecto razonable puede ser varios puntos por ciento más larga que la mejor, y la única manera de saberlo es haber descartado todas las demás, o tener una cota matemática que diga que ninguna puede bajar de cierta longitud.

Esa es la dificultad de fondo, y tiene nombre desde 1972. Richard Karp demostró ese año que el viajante pertenece a una familia de problemas, los NP-completos, con una propiedad extraña: si alguien encontrara para uno cualquiera de ellos un algoritmo cuyo tiempo creciera como una potencia del tamaño, un polinomio en el lenguaje de la notación O grande, lo habría encontrado para todos. Entre ellos están el horario de un colegio, el reparto de la carga de un camión y la rotura de muchos cifrados. Nadie ha encontrado ese algoritmo ni ha demostrado que no exista; es el problema de si P es igual a NP, el más famoso de la informática teórica. Lo mejor que se sabe hacer con garantías es la programación dinámica de Held y Karp, de 1962, que resuelve el problema en un tiempo del orden de n² por 2 elevado a n: es lo que usa el botón «Óptimo» de la figura y, con un millón de veces menos trabajo que probar todas las rutas, sigue siendo exponencial.

La historia del problema es la de aprender a resolver lo que no se puede resolver. Karl Menger lo planteó en Viena en 1930, con el nombre de problema del mensajero, y en Princeton se le puso el del viajante durante esa década. En 1954, George Dantzig, Ray Fulkerson y Selmer Johnson resolvieron en la RAND Corporation un mapa de 49 ciudades, una por estado de Estados Unidos más Washington, con un método que no probaba rutas sino que las acotaba. Relajaban el problema a uno de programación lineal, que sí se resuelve rápido, y añadían una desigualdad cada vez que la solución relajada hacía algo que un recorrido de verdad no puede hacer, como partirse en dos ciclos. Ese método de planos de corte es el que, con sesenta años de refinamientos, resolvió en 2004 las 24.978 ciudades de Suecia y en 2006 un mapa de 85.900 puntos, los agujeros de un circuito integrado que una máquina debía perforar, el mayor caso del viajante resuelto hasta la fecha con demostración de optimalidad. William Cook, uno de los autores de ese programa, llamado Concorde, lo cuenta en su libro de 2012.

Para los casos en que no hace falta la certeza hay dos escuelas. La de las garantías la fundó Nicos Christofides en 1976 con un algoritmo que, si las distancias cumplen la desigualdad triangular, nunca da una ruta más de un 50 por ciento más larga que la óptima. Esa cota pareció inmejorable durante 44 años, hasta que en 2020 Anna Karlin, Nathan Klein y Shayan Oveis Gharan la bajaron en una cantidad del orden de una billonésima de billonésima de billonésima, que no cambia ninguna ruta pero demuestra que el muro se puede mover. La escuela de la práctica no promete nada y lo hace casi todo: las heurísticas de la familia de Lin y Kernighan, que deshacen cruces de maneras más elaboradas que la figura, encuentran en minutos rutas a menos de un uno por ciento de la óptima para millones de ciudades. Son lo que hay dentro de los programas que planifican los repartos de paquetería, el orden en que una máquina taladra una placa, la secuencia en que un telescopio apunta a sus objetivos de la noche o el camino de un operario por los pasillos de un almacén.

Lo que hace al viajante tan buen ejemplo es el contraste con su primo. Encontrar el camino más corto entre dos ciudades lo resuelve el algoritmo de Dijkstra en una fracción de segundo para el mapa entero de Europa; encontrar el camino más corto que pase por todas no se sabe resolver para un mapa de cien sin astucia. Los dos enunciados se parecen y están a una distancia que la informática no ha conseguido medir en cincuenta años. Mientras tanto, los paquetes llegan: con rutas que nadie puede demostrar óptimas y que casi nunca están lejos de serlo.

La programación dinámica – El algoritmo de Dijkstra – La notación O grande – Los algoritmos de ordenación – La búsqueda en anchura y en profundidad

Una caché (en inglés, cache) 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 (replacement policy), y la más usada, la que da título a esta página, es LRU (least recently used): 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 (cache hit), y en rojo si no, un fallo (cache miss). 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 (locality of reference): 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 (en inglés, Bloom filter) es una estructura de datos (data structure) 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 (bit array), todos a cero al principio. Insertar una palabra es pasarla por k funciones hash (hash functions) 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 (false positive), 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.

La tabla hash

PageRank (en inglés, 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 (search engines) anteriores. Su idea es que la importancia de una página web se puede medir por los enlaces (links) 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 (random surfer). 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 (eigenvector) 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 (damping factor), 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?

Navegación (informática)