Jump Search en Java

    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 = 鈭歯. Por lo tanto, el tama帽o de bloque 贸ptimo es 鈭歯.

    En consecuencia, Jump Search mantiene una eficiencia media y en el peor de los casos de O (鈭歯) 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 (鈭歯).

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *