Digamos que está trabajando para la NSA y almacena metadatos para todas las llamadas telefónicas en los EE. UU. Recopiladas durante algunos años, agrupadas por el número de teléfono. Desea saber si un teléfono en particular está en su base de datos. Hay diferentes formas de hacerlo, pero supongamos que clasifica todos los teléfonos y los almacena en una gran matriz de memoria, de esta manera no almacena ninguna otra información.
Para buscar el teléfono en cuestión, verifica el centro de la matriz. Si tiene la suerte de ver el número correcto, pare (este paso se puede omitir en algunas optimizaciones). De lo contrario, vea si su teléfono es numéricamente mayor o no. Esto le dirá en qué mitad de la matriz debe estar su teléfono (si no falta).
Por lo tanto, repite el mismo paso en una submatriz de tamaño medio. Esto es excelente para la velocidad porque en una matriz de tamaño N solo puede hacer [math] \ log_2 N [/ math] tales pasos.
Esto es muy rápido: en una matriz de 2 GB (probablemente demasiado pequeña para las bases de datos de la NSA), solo realizaría 16 pasos, y cada paso es rápido (este es solo un ejemplo de búsqueda binaria simple que usa más memoria que la mayoría de los programas en un ordenador portátil).
¿Puedes hacerlo mejor?
Aquí es donde la búsqueda de interpolación es útil.
Si sabe que los números de teléfono se distribuyen aproximadamente de manera uniforme, en lugar de reducir a la mitad la matriz cada vez, puede adivinar mejor, en función del valor del número de teléfono (representado como un número entero). Básicamente, si está aproximadamente en la marca de 1/4 entre los límites, ahí es donde se realiza la próxima comparación (elija el siguiente pivote). Resulta que esto reduce el tiempo de ejecución a [math] \ log_2 \ log_2 N [/ math] en promedio, siempre que sus conjeturas sigan siendo razonables la mayor parte del tiempo.
- Cómo escribir una gran cantidad de archivos a la vez, sin obstruir los recursos de la máquina
- ¿Qué es la teoría de autómatas?
- Cómo recuperar LVM eliminado en Linux
- ¿Durante cuánto tiempo se seguirá aplicando la Ley de Moore?
- ¿Cuánto tiempo llevas trabajando en aprendizaje automático / inteligencia artificial?
Para más detalles, ver: Búsqueda de interpolación
