Jump Search en Java

J

Introducción

Ya sea buscando a través de una lista de reproducción de su canción favorita o buscando a través de un catálogo para elegir el restaurante para tener su próxima comida, nuestras vidas están llenas de buscar cosas.

De la misma manera, las computadoras realizan consultas de búsqueda en sus colecciones y estructuras de datos. Sin embargo, a diferencia de los humanos, las computadoras tienen que realizar búsquedas en conjuntos de datos mucho más grandes en tiempos que son órdenes de magnitud más rápidos que los humanos.

Esto llevó a los informáticos a idear muchos algoritmos de búsqueda, en los que cada uno suele ser más óptimo que otro en determinadas colecciones.

Saltar búsqueda

Jump Search (también conocido como Block Search) es un algoritmo utilizado para buscar la posición de un elemento de destino en una colección o estructura de datos ordenados.

En lugar de buscar la matriz elemento por elemento (búsqueda lineal), Jump Search evalúa bloques de elementos. O más bien, ya que es una matriz ordenada, el elemento con el valor más alto en cada bloque.

Si el valor es menor que el elemento objetivo, se considera el siguiente bloque.
Si el valor es mayor que el elemento de destino, el elemento de destino está en el bloque actual.
Si el valor es el elemento de destino, simplemente devuélvalo.

Cambiando iterativamente, o más bien saltando hacia adelante, encontraremos el elemento de destino o llegaremos al final de la colección sin encontrarlo.

Aquí hay una representación visual de cómo funciona Jump Search:

Evidentemente, Jump Search siempre busca hacia adelante en sus matrices, a diferencia de los métodos de búsqueda de ida y vuelta como la búsqueda binaria. Este comportamiento hace que Jump Search sea mucho más eficiente para búsquedas de datos almacenados en unidades físicas con soportes giratorios.

Además, otra forma de entender esta búsqueda es sin bloques: simplemente hay un salto entre los elementos evaluados. No se guarda ningún bloque real en la memoria mientras se ejecuta el algoritmo.

Implementación

Dicho esto, implementemos Jump Search. Hay dos enfoques que puede tomar, sin un “ganador” real entre estos dos: la implementación iterativa y recursiva.

La elección entre estos dos depende de usted y, a menos que esté trabajando en conjuntos de datos increíblemente grandes, no debería haber una diferencia en el rendimiento. La recursividad conduce a un mayor uso de espacio en el procesador / memoria, pero generalmente es más limpio para leer y escribir.

Por otra parte, si está trabajando en conjuntos de datos realmente grandes, probablemente utilice algoritmos de búsqueda optimizados y más eficientes.

Implementación iterativa

Dicho esto, comencemos con el enfoque iterativo:

public static int jumpSearch(int[] arrayToSearch, int element) {
    int blockSize = (int) Math.floor(Math.sqrt(arrayToSearch.length));

    int currentLastIndex = blockSize-1;
    
    // Jump to next block as long as target element is > currentLastIndex
    // and the array end has not been reached
    while (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
        currentLastIndex += blockSize;
    }

    // Find accurate position of target element using Linear Search
    for (int currentSearchIndex = currentLastIndex - blockSize + 1;
         currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
        if (element == arrayToSearch[currentSearchIndex]) {
            return currentSearchIndex;
        }
    }
    // Target element not found. Return negative integer as element position.
    return -1;
}

En primer lugar, hemos calculado el tamaño del bloque. Generalmente, una raíz cuadrada de la longitud de la matriz es un buen tamaño para elegir. Esto se explica con más detalle en la sección Análisis de Big-O. Buscar en un bloque como este, al final, también será barato para un algoritmo como Linear Search.

Dado que la matriz está ordenada, si el valor de nuestro elemento de destino es mayor que el valor del elemento actual, entonces el elemento de destino seguramente no puede estar dentro del bloque actual. Así que saltamos al siguiente bloque y comparamos el elemento de destino con el último valor del elemento de índice del nuevo bloque.

Este salto se repite hasta que se encuentra el bloque que contiene el elemento objetivo.

Si el elemento de destino ya no es mayor que el valor del último elemento en un bloque, entonces tiene que estar dentro del bloque si existe.

Entonces encontraremos la posición precisa del elemento de destino usando la búsqueda lineal

Si llegamos al final de la matriz sin encontrar un bloque que contenga nuestro elemento de destino, no está presente en la matriz y regresamos -1 para significar eso.

Implementación recursiva

Con la implementación iterativa fuera del camino, exploremos también la implementación recursiva:

public static int jumpSearchInit(int[] arrayToSearch, int element) {
    int blockSize = (int) Math.sqrt(arrayToSearch.length);

    // Hold the last index of the current block
    int currentLastIndex = blockSize-1;

    return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
}

public static int jumpSearch(int[] arrayToSearch, int element, int blockSize, int currentLastIndex) {
    if (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
        currentLastIndex += blockSize;
        // Make recursive call to jumpSearch method
        return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
    } else {
        // Find accurate position of target element using linear search
        for (int currentSearchIndex = currentLastIndex - blockSize + 1;currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
            if (element == arrayToSearch[currentSearchIndex]) {
                return currentSearchIndex;
            }
        }
    }
    // Target element not found. Return negative integer as element position.
    return -1;
}

La realización recursiva de Jump Search funciona de la misma manera. Simplemente llamamos al método de forma recursiva en lugar de tener un while lazo.

Necesitamos el uso de un método de inicialización para realizar algunos cálculos iniciales. Es decir, el tamaño de bloque óptimo y el último índice del primer bloque.

A partir de entonces, mientras nuestro elemento de destino sea mayor que el último valor del elemento de índice del bloque actual, llamamos de forma recursiva al método Jump Search pasándole los parámetros del bloque siguiente.

Esta recursividad termina una vez que se encuentra el bloque que contiene el elemento de destino, o si finalmente se alcanza el final de la matriz

En caso de que se encuentre un bloque de destino de este tipo, realizamos una búsqueda lineal en él para encontrar la posición del elemento de destino.

Búsqueda de salto de evaluación comparativa

Comparemos Jump Search ejecutándolo contra matrices de enteros ordenados de varios tamaños. Por supuesto, buscaremos el peor de los casos en todos estos (el último elemento):

Tamaño de la matriz 1.a ejecución (ms) 2.a ejecución (ms) 3.a ejecución (ms) Promedio (ms)

100.35950.22670.34770.3119
10,0000.22100.58090.22250.3410
1,000,0000,77540,77880,79060,7816

En comparación con la búsqueda lineal, que tarda 5.4209 ms, es evidente que Jump Search es significativamente más rápido.

Análisis Big-O

Considere una matriz entera ordenada de tamaño n con un tamaño de bloque de m.

En el mejor de los casos, Jump Search encontraría el elemento de destino en el borde del primer bloque en el que busca. A su vez, esto hace que Jump Search tenga una eficiencia en el mejor de los casos de O (1) complejidad en términos de notación Big-O.

Por el contrario, considerando su peor caso, Jump Search saltaría consecutivamente a su último bloque en busca del elemento objetivo, lo que a su vez provocaría un n/m número de saltos. Además, si el valor del último elemento de este bloque era mayor que el elemento de destino, Jump Search realizaría una búsqueda lineal con m-1 iteraciones.

Esto hace que Jump Search haga (n/m) saltos con adicionales m-1 iteraciones. Este valor es mínimo en m = √n. Por lo tanto, el tamaño de bloque óptimo es √n.

En consecuencia, Jump Search mantiene una eficiencia media y en el peor de los casos de O (√n) complejidad.

Esto hace que sea digno de mención que aunque Jump Search es altamente eficiente para buscar matrices, especialmente cuando su comportamiento de solo búsqueda hacia adelante es favorable, su rendimiento promedio lo ubica en algún lugar entre la búsqueda binaria O (log n) complejidad y búsqueda lineal con un En) complejidad.

Y también, Jump Search requiere constantemente que sus matrices buscadas se clasifiquen en orden ascendente, por adelantado.

Conclusión

Jump Search se realiza saltando bloque por bloque de la matriz hasta que se encuentra un bloque que podría contener un elemento determinado.

En este artículo, hemos implementado Jump Search iterativo y recursivo y hemos comparado el algoritmo con matrices de diferentes tamaños.

Además, realizamos un análisis Big-O que demuestra cómo Jump Search adquirió su eficiencia promedio y en el peor de los casos de O (√n).

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad