Jump Search en Python

J

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 √n, 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 = √n
  • 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 √n, el tiempo de ejecución también sería O(√n).

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.

 

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