Jump Search en Python

    Introducci贸n

    Encontrar los datos correctos que necesitamos es un viejo problema antes que las computadoras. Como desarrolladores, creamos muchos algoritmos de b煤squeda para recuperar datos de manera eficiente.

    Los algoritmos de b煤squeda se pueden dividir en dos categor铆as amplias: b煤squedas secuenciales y de intervalo. Las b煤squedas secuenciales verifican cada elemento en una estructura de datos. Las b煤squedas por intervalos verifican varios puntos de los datos (llamados intervalos), lo que reduce el tiempo que lleva encontrar un elemento, dado un conjunto de datos ordenado.

    En este art铆culo, cubrir谩 Jump Search en Python, una combinaci贸n h铆brida de b煤squeda secuencial y b煤squeda de intervalo en matrices ordenadas.

    Saltar b煤squeda

    Con Jump Search, la matriz ordenada de datos se divide en subconjuntos de elementos llamados bloques. Encontramos la clave de b煤squeda (valor de entrada) comparando el candidato de b煤squeda en cada bloque. A medida que se ordena la matriz, el candidato de b煤squeda es el valor m谩s alto de un bloque.

    Al comparar la clave de b煤squeda con un candidato de b煤squeda, el algoritmo puede hacer 1 de 3 cosas:

    • Si el candidato de b煤squeda es menor que la clave de b煤squeda, verificaremos el bloque siguiente
    • Si el candidato de b煤squeda es mayor que la clave de b煤squeda, haremos una b煤squeda lineal en el bloque actual
    • Si el candidato de b煤squeda es el mismo que la clave de b煤squeda, devuelva el candidato

    El tama帽o del bloque se elige como la ra铆z cuadrada de la longitud de la matriz. Por lo tanto, matrices con longitud n tener un tama帽o de bloque de 鈭歯, ya que esto en promedio ofrece el mejor rendimiento para la mayor铆a de los arreglos.

    Puede resultar 煤til ilustrar c贸mo funciona. As铆 es como Jump Search multar铆a el valor 78 en una matriz de 9 elementos:

    El ejemplo anterior encuentra el elemento en 5 pasos, ya que hay dos comprobaciones en la secci贸n de b煤squeda lineal.

    Ahora que tenemos una apreciaci贸n de alto nivel de c贸mo funciona, veamos una implementaci贸n de pseudoc贸digo del algoritmo.

    Pasos de b煤squeda de salto

    Entradas:

    • Lista de arreglo A de tama帽o n
    • Clave de b煤squeda item

    Salida:

    • 脥ndice de la clave de b煤squeda coincidente o -1 Si el item no se encuentra

    Pasos

    • Paso 1: Encuentra la longitud del ordenado lista de fuentesn = len(A)
    • Paso 2: Determine el tama帽o de bloque adecuado – m = 鈭歯
    • Paso 3: La iteraci贸n comienza en el 铆ndice del item a i = 0 con un paso de m y contin煤a hasta que la ventana llega al final de la lista.
    • Etapa 4: Comparar A[i+m] (i+m es el 煤ltimo 铆ndice de un bloque) y el item
      • un) Si A[i+m] == item, Regreso i+m; Salidas de c贸digo
      • segundo) Si A[i+m] > item, Proceda a la b煤squeda lineal dentro del bloque conocido como lista derivada B = A[i: i+m]
        • Itere y compare cada elemento de la lista con la clave de b煤squeda y devuelva la coincidencia i si se encuentra; Salidas de c贸digo
      • C) Si A[i+m] < item, Contin煤e con la siguiente iteraci贸n al Paso 4: flechas_en el sentido de las agujas del reloj:
    • Paso 5: Itere los elementos de la lista que no caben en el bloque y devuelva el 铆ndice coincidente i. Si no se encontraron coincidencias, regrese -1; Salidas de c贸digo

    Como ahora entendemos c贸mo funciona, 隆implementemos este algoritmo en Python!

    Implementaci贸n

    Sabiendo c贸mo funciona Jump Search, vamos a implementarlo en Python:

    '''
    Jump Search function
    Arguments:
    A    - The source list
    item - Element for which the index needs to be found
    '''
    import math
    
    def jump_search(A, item):
        print("Entering Jump Search")
        n = len(A)                          # Length of the array
        m = int(math.sqrt(n))               # Step length
        i = 0                               # Starting interval
    
        while i != len(A)-1 and A[i] < item:
            print("Processing Block - {}".format(A[i: i+m]))
            if A[i+m-1] == item:            # Found the search key
                return i+m-1
            elif A[i+m-1] > item:           # Linear search for key in block
                B = A[i: i+m-1]
                return linear_search(B, item, i)
            i += m
    
        B = A[i:i+m]                        # Step 5
        print("Processing Block - {}".format(B))
        return linear_search(B, item, i)
    

    los jump_search() La funci贸n toma dos argumentos: la lista ordenada en evaluaci贸n como primer argumento y el elemento que debe encontrarse en el segundo argumento. los math.sqrt() La funci贸n se usa para encontrar el tama帽o del bloque. La iteraci贸n es facilitada por un while condici贸n y el incremento se hace factible por el incremento i += m.

    Habr铆a notado que el Step 4b y Step 5 tener un linear_search() funci贸n invocada. los linear_search() La funci贸n se activa en uno de los siguientes escenarios.

    • Step 4b – Cuando hay un cambio en la comparaci贸n. Si el 煤ltimo elemento de un bloque / ventana es mayor que el item, la linear_search() se activa.
    • Step 5 – Los elementos restantes de la lista de fuentes A que no caben en un bloque se pasan como una lista derivada al linear_search() funci贸n.

    los linear_search() La funci贸n se puede escribir as铆:

    '''
    Linear Search function
    Arguments:
    B    - The derived list
    item - Element for which the index needs to be found
    loc  - The Index where the remaining block begins
    '''
    
    def linear_search(B, item, loc):
        print("t Entering Linear Search")
        i = 0
    
        while i != len(B):
            if B[i] == item:
                return loc+i
            i += 1
        return -1
    

    En el paso 5, los elementos restantes de la lista original se pasan al linear_search() funcionar como una lista derivada. La comparaci贸n se realiza con cada elemento de la lista derivada. B.

    El 铆ndice coincidente de la lista derivada se agrega al 铆ndice del bloque fuente, para proporcionar la posici贸n de 铆ndice exacta del elemento en la lista fuente. Si no se encuentran coincidencias, regresamos -1 para indicar que item no fue encontrado.

    Se puede encontrar el fragmento completo aqu铆.

    Benchmarking: b煤squeda con salto frente a b煤squeda lineal

    El tiempo de ejecuci贸n de Jump Search se puede comparar con la b煤squeda lineal. La siguiente visualizaci贸n ilustra c贸mo se desempe帽an los algoritmos al buscar un elemento cerca del final de una matriz ordenada. Cuanto m谩s corta sea la barra, mejor:

    A medida que aumenta el n煤mero de elementos de la lista, Jump Search es m谩s r谩pido que el algoritmo de b煤squeda lineal.

    An谩lisis Big-O

    Hagamos un an谩lisis m谩s general de c贸mo funciona Jump Search. Una vez m谩s, consideraremos el peor de los casos en el que el elemento que se va a encontrar est谩 al final de la lista.

    Para obtener una lista de n elementos y un tama帽o de bloque de m, Jump Search funcionar铆a idealmente n/m saltos. Considerando que el tama帽o del bloque es tan 鈭歯, el tiempo de ejecuci贸n tambi茅n ser铆a O(鈭歯).

    Esto coloca Jump Search entre la b煤squeda lineal (peor) con una complejidad en tiempo de ejecuci贸n de O(n) y b煤squeda binaria (mejor) con una complejidad en tiempo de ejecuci贸n de O(log n). Por lo tanto, Jump Search se puede utilizar en lugares donde la b煤squeda binaria no es factible y la b煤squeda lineal es demasiado costosa.

    Conclusi贸n

    En este art铆culo, hemos cubierto los conceptos b谩sicos del algoritmo Jump Search. Luego examinamos c贸mo funciona Jump Search con pseudoc贸digo antes de implementarlo en Python. A partir de entonces, analizamos c贸mo funciona Jump Search, as铆 como sus l铆mites de velocidad te贸ricos.

     

    Etiquetas:

    Deja una respuesta

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