La aguja en un pajar en la informática

El camino lento: mirar todo

Si no sabes nada sobre dónde está la aguja, la única opción es revisar cada trozo de paja hasta encontrarla. En informática esto se llama búsqueda lineal. De media revisas la mitad de todo antes de tener éxito y, en el peor caso, todo. Siempre funciona, pero el tiempo crece en proporción al tamaño del montón.

Ordenar lo cambia todo

Imagina ahora que la paja estuviera colocada en orden, como las palabras de un diccionario. Un método más listo, la búsqueda binaria, abre por la mitad, decide en qué mitad está la respuesta y descarta la otra. Si lo repites, un millón de elementos se recorren en unos 20 pasos. La trampa es que el montón debe estar ordenado primero, y un pajar nunca lo está.

Índices: hacer trampa preparándose

Las bases de datos y los buscadores esquivan el problema haciendo el trabajo duro por adelantado. Construyen un índice, como la lista al final de un libro que te dice en qué página está una palabra. Buscar algo se vuelve rápido porque el tiempo se gastó antes. No existe un índice para un pajar de verdad, y por eso existe la expresión.

Seguir una señal

Un detector de metales es distinto. No te dice dónde está la aguja, pero sí si te acercas. Imagina un número que sube cuando te aproximas. Entonces puedes aplicar una regla sencilla: da un paso, mira si la señal creció y sigue en la dirección que la mejora. Los programadores llaman a una versión de esto ascenso de colina (hill climbing), y está detrás de muchas optimizaciones prácticas.

En el juego, la señal se calcula a partir de lo lejos que estás del trozo de metal más cercano en comparación con el alcance del detector. Los pitidos se aceleran a medida que ese número se acerca a 1, así que tu oído hace el ascenso de colina por ti. Hay más en Cómo funciona el detector de metales.

Cuando fallan las señales

El ascenso de colina puede atascarse. Si hay mucho metal de desecho cerca de la aguja, la señal más fuerte puede llevarte a un clavo. El juego lo resuelve dando a los detectores de gama alta la capacidad de distinguir la aguja. Las búsquedas reales se topan con el mismo problema y usan mejores sensores o filtros adicionales.

El pajar como datos

El pajar del juego es en sí una estructura de datos: una malla de 88 por 40 por 88 celdas, cada una con un número para la densidad de la paja. Cavar es cambiar números, y los chunks de 16 celdas mantienen el trabajo pequeño. Cómo funciona está en Cómo funciona el pajar.