técnica de búsqueda de Fibonacci es un método de búsqueda de una matriz ordenada utilizando un algoritmo de divide y vencerás que reduce posibles ubicaciones con la ayuda de los números de Fibonacci . [1] En comparación con la búsqueda binaria donde la matriz ordenada se divide en dos partes del mismo tamaño, una de las cuales se examina más a fondo, la búsqueda de Fibonacci divide la matriz en dos partes que tienen tamaños que son números consecutivos de Fibonacci. En promedio, esto lleva a que se ejecuten aproximadamente un 4% más de comparaciones, [2]pero tiene la ventaja de que uno solo necesita sumar y restar para calcular los índices de los elementos de la matriz a los que se accede, mientras que la búsqueda binaria clásica necesita desplazamiento de bits, división o multiplicación, [1] operaciones que eran menos comunes en el momento en que la búsqueda de Fibonacci era la primera publicado. La búsqueda de Fibonacci tiene una complejidad promedio y en el peor de los casos de O (log n ) (vea la notación Big O ).
La secuencia de Fibonacci tiene la propiedad de que un número es la suma de sus dos predecesores. Por lo tanto, la secuencia se puede calcular mediante la suma repetida. La razón de dos números consecutivos se aproxima a la razón de oro , 1.618 ... La búsqueda binaria funciona dividiendo el área de búsqueda en partes iguales (1: 1). La búsqueda de Fibonacci puede dividirlo en partes que se aproximan a 1: 1.618 mientras usa las operaciones más simples.
Si los elementos que se buscan tienen almacenamiento de memoria de acceso no uniforme (es decir, el tiempo necesario para acceder a una ubicación de almacenamiento varía según la ubicación a la que se accede), la búsqueda de Fibonacci puede tener la ventaja sobre la búsqueda binaria al reducir ligeramente el tiempo promedio necesario para acceder Un lugar de almacenamiento. Si la máquina que ejecuta la búsqueda tiene un caché de CPU mapeado directo , la búsqueda binaria puede conducir a más errores de caché porque los elementos a los que se accede a menudo tienden a reunirse en unas pocas líneas de caché; esto se mitiga dividiendo la matriz en partes que no tienden a ser potencias de dos. Si los datos se almacenan en una cinta magnética donde el tiempo de búsqueda depende de la posición actual de la cabeza, una compensación entre un tiempo de búsqueda más largo y más comparaciones puede conducir a un algoritmo de búsqueda sesgado de manera similar a la búsqueda de Fibonacci.
La búsqueda de Fibonacci se deriva de la búsqueda de la sección Dorada , un algoritmo de Jack Kiefer (1953) para buscar el máximo o mínimo de una función unimodal en un intervalo. [3]
Algoritmo [ editar ]
Sea k definido como un elemento en F , la matriz de números de Fibonacci. n = F m es el tamaño de la matriz. Si n no es un número de Fibonacci, dejemos que F m sea el número más pequeño en F que sea mayor que n .
La matriz de números de Fibonacci se define donde F k +2 = F k +1 + F k , cuando k ≥ 0, F 1 = 1 y F 0 = 0.
Para probar si un artículo está en la lista de números ordenados, siga estos pasos:
- Establecer k = m .
- Si k = 0, deténgase. No hay partido; El artículo no está en la matriz.
- Compare el elemento con el elemento en F k −1 .
- Si el artículo coincide, deténgase.
- Si el elemento es menor que la entrada F k −1 , descarte los elementos de las posiciones F k −1 + 1 a n . Establezca k = k - 1 y regrese al paso 2.
- Si el elemento es mayor que la entrada F k −1 , descarte los elementos de las posiciones 1 a F k −1 . Vuelva a numerar los elementos restantes de 1 a F k −2 , establezca k = k - 2 y regrese al paso 2.
Dada una tabla de registros R 1 , R 2 , ..., R N cuyas claves son creciente K 1 < K 2 <... < K N , el algoritmo de búsqueda para un argumento dado K . Suponga que N + 1 = F k +1
Paso 1. [Inicializar] i ← F k , p ← F k -1 , q ← F k -2 (en todo el algoritmo, p y q serán números Fibonacci consecutivos)
Paso 2. [Comparar] Si K < K i , vaya al Paso 3 ; si K > K i ir a la Etapa 4 ; y si K = K i , el algoritmo termina con éxito.
Paso 3. [Disminuir i ] Si q = 0, el algoritmo termina sin éxito. De lo contrario, establezca ( i , p , q ) ← ( p , q , p - q ) (que mueve p y q una posición hacia atrás en la secuencia de Fibonacci); luego regrese al Paso 2
Paso 4. [Incrementar i ] Si p = 1, el algoritmo termina sin éxito. De lo contrario, establezca ( i , p , q ) ← ( i + q , p - q , 2q - p ) (que mueve p y q dos posiciones hacia atrás en la secuencia de Fibonacci); y regrese al paso 2
Las dos variantes del algoritmo presentadas anteriormente siempre dividen el intervalo actual en un subintervalo más grande y más pequeño. Sin embargo, el algoritmo original [1] dividiría el nuevo intervalo en un subintervalo más pequeño y más grande en el Paso 4. Esto tiene la ventaja de que el nuevo i está más cerca del antiguo i y es más adecuado para acelerar la búsqueda en cinta magnética.
búsqueda de salto o búsqueda de bloque se refiere a un algoritmo de búsqueda para listas ordenadas . Funciona comprobando primero todos los elementos L km , dondey m es el tamaño del bloque, hasta que un artículo se encuentra que es más grande que la clave de búsqueda . Para encontrar la posición exacta de la tecla de búsqueda en la lista, se realiza una búsqueda lineal en la sublista L [( k -1) m , km ] .
El valor óptimo de m se √ n , donde n es la longitud de la lista L . Debido a que ambos pasos del algoritmo miran, a lo sumo, √ n elementos que el algoritmo ejecuta en tiempo O ( √ n ). Esto es mejor que una búsqueda lineal , pero peor que una búsqueda binaria . La ventaja sobre este último es que una búsqueda de salto solo necesita saltar hacia atrás una vez, mientras que un binario puede saltar hacia atrás para iniciar sesión n veces. Esto puede ser importante si un salto hacia atrás lleva mucho más tiempo que saltar hacia adelante.
El algoritmo puede modificarse realizando múltiples niveles de búsqueda de salto en las sublistas, antes de realizar finalmente la búsqueda lineal . Para un k -level saltar buscar el óptimo tamaño de bloque m l para el l º nivel (contando desde 1) es n (kl) / k . El algoritmo modificado realizará k saltos hacia atrás y se ejecutará en tiempo O ( kn 1 / ( k +1) ).
La búsqueda de interpolación es un algoritmo para buscar una clave en una matriz que ha sido ordenada por valores numéricos asignados a las claves ( valores de clave ). Fue descrito por primera vez por WW Peterson en 1957. [1] La búsqueda de interpolación se asemeja al método por el cual las personas buscan un nombre en el directorio telefónico (el valor clave por el cual se ordenan las entradas del libro): en cada paso el algoritmo calcula dónde en el espacio de búsqueda restante , el elemento buscado podría ser, en función de los valores clave en los límites del espacio de búsqueda y el valor de la clave buscada, generalmente a través de una interpolación lineal. El valor clave realmente encontrado en esta posición estimada se compara con el valor clave que se busca. Si no es igual, entonces, según la comparación, el espacio de búsqueda restante se reduce a la parte anterior o posterior a la posición estimada. Este método solo funcionará si los cálculos sobre el tamaño de las diferencias entre los valores clave son razonables.
En comparación, la búsqueda binaria siempre elige la mitad del espacio de búsqueda restante, descartando una mitad u otra, dependiendo de la comparación entre la clave encontrada en la posición estimada y la clave buscada; no requiere valores numéricos para las claves, solo Un orden total sobre ellos. El espacio de búsqueda restante se reduce a la parte anterior o posterior a la posición estimada. La búsqueda lineal usa la igualdad solo ya que compara los elementos uno por uno desde el principio, ignorando cualquier clasificación.
En promedio, la búsqueda de interpolación realiza comparaciones log (log ( n )) (si los elementos están distribuidos uniformemente), donde n es el número de elementos a buscar. En el peor de los casos (por ejemplo, donde los valores numéricos de las teclas aumentan exponencialmente) puede hacer hasta O ( n ) comparaciones.
En la búsqueda secuencial por interpolación, la interpolación se usa para encontrar un elemento cerca del que se está buscando, luego la búsqueda lineal se usa para encontrar el elemento exacto.
Rendimiento [ editar ]
Usando la notación big-O , el rendimiento del algoritmo de interpolación en un conjunto de datos de tamaño n es O ( n ); sin embargo, bajo el supuesto de una distribución uniforme de los datos en la escala lineal utilizada para la interpolación, se puede mostrar que el rendimiento es O (log log n ). [2] [3] [4] Sin embargo, la búsqueda de interpolación dinámica es posible en el tiempo o (log log n ) utilizando una nueva estructura de datos. [5]
El rendimiento práctico de la búsqueda de interpolación depende de si el número reducido de sondas se ve superado por los cálculos más complicados necesarios para cada sonda. Puede ser útil para ubicar un registro en un archivo ordenado grande en el disco, donde cada sonda implica una búsqueda de disco y es mucho más lenta que la aritmética de interpolación.
Las estructuras de índice como los árboles B también reducen el número de accesos a disco, y se usan con mayor frecuencia para indexar datos en disco en parte porque pueden indexar muchos tipos de datos y pueden actualizarse en línea . Aún así, la búsqueda por interpolación puede ser útil cuando uno se ve obligado a buscar ciertos conjuntos de datos en disco ordenados pero no indexados.
Adaptación a diferentes conjuntos de datos [ editar ]
Cuando las claves de clasificación para un conjunto de datos son números distribuidos uniformemente, la interpolación lineal es fácil de implementar y encontrará un índice muy cercano al valor buscado.
Por otro lado, para una guía telefónica ordenada por nombre, no se aplica el enfoque directo para la búsqueda de interpolación. Sin embargo, aún se pueden aplicar los mismos principios de alto nivel: se puede estimar la posición de un nombre en la guía telefónica usando las frecuencias relativas de letras en los nombres y usar eso como una ubicación de la sonda.
Algunas implementaciones de búsqueda de interpolación pueden no funcionar como se espera cuando existe una ejecución de valores clave iguales. La implementación más simple de la búsqueda de interpolación no necesariamente seleccionará el primer (o último) elemento de dicha ejecución.
Búsqueda basada en libros [ editar ]
La conversión de nombres en una guía telefónica a algún tipo de número claramente no proporcionará números que tengan una distribución uniforme (excepto a través de un esfuerzo inmenso como ordenar los nombres y llamarlos nombre # 1, nombre # 2, etc.) y, además, Es bien sabido que algunos nombres son mucho más comunes que otros (Smith, Jones,) De manera similar con los diccionarios, donde hay muchas más palabras que comienzan con algunas letras que otras. Algunos editores se esfuerzan por preparar anotaciones marginales o incluso cortar a un lado de las páginas para mostrar marcadores para cada letra de modo que de un vistazo se pueda realizar una interpolación segmentada.
Implementación de muestra [ editar ]
El siguiente ejemplo de código C ++ es una implementación simple. En cada etapa calcula una posición de la sonda y luego, como con la búsqueda binaria, mueve el límite superior o inferior para definir un intervalo más pequeño que contiene el valor buscado. A diferencia de la búsqueda binaria que garantiza la reducción a la mitad del tamaño del intervalo con cada etapa, una interpolación engañosa puede reducir la eficiencia / caso i de O ( n ).
Tenga en cuenta que después de haber sondeado la lista en el índice medio , por razones de administración de control de bucle, este código establece que alto o bajo no sea medio sino un índice adyacente, cuya ubicación se sondea durante la próxima iteración. Dado que el valor de una entrada adyacente no será muy diferente, el cálculo de la interpolación no mejora mucho con este ajuste de un solo paso, a costa de una referencia adicional a la memoria distante, como el disco.
Cada iteración del código anterior requiere entre cinco y seis comparaciones (el extra se debe a las repeticiones necesarias para distinguir los tres estados de <> y = a través de comparaciones binarias en ausencia de una comparación de tres vías ) más algunas aritméticas desordenadas. el algoritmo de búsqueda binaria se puede escribir con una comparación por iteración y solo usa aritmética de enteros triviales. Buscaría así una matriz de un millón de elementos con no más de veinte comparaciones (que implican accesos a la memoria lenta donde se almacenan los elementos de la matriz); Para superar eso, la búsqueda de interpolación, como se escribió anteriormente, no se permitiría más de tres iteraciones.
La búsqueda binaria uniforme es una optimización del clásico algoritmo de búsqueda binaria inventado por Donald Knuth y presentado en Knuth's The Art of Computer Programming . Utiliza una tabla de búsqueda para actualizar un índice de matriz única, en lugar de tomar el punto medio de un límite superior e inferior en cada iteración; por lo tanto, está optimizado para arquitecturas (como Knuth's MIX ) en las que
- una búsqueda en la tabla es generalmente más rápida que una adición y un turno, y
- muchas búsquedas se realizarán en la misma matriz o en varias matrices de la misma longitud
No hay comentarios:
Publicar un comentario