Saltar búsqueda en Python

El algoritmo Jump Search es una combinación híbrida de búsqueda secuencial y búsqueda por intervalos en matrices ordenadas. Aprendamos cómo implementarlo en Python.

Introducción

Encontrar los datos correctos que necesitamos es un problema antiguo antes de 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 amplias categorías: búsquedas secuenciales y de intervalos. Las búsquedas secuenciales verifican cada elemento en una estructura de datos. Las búsquedas de intervalo 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 in Python: una combinación híbrida de búsqueda secuencial y búsqueda por intervalos 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:

  1. Si el candidato de búsqueda es menor que la clave de búsqueda, verificaremos el bloque siguiente
  2. Si el candidato de búsqueda es mayor que la clave de búsqueda, haremos una búsqueda lineal en el bloque actual
  3. Si el candidato de búsqueda es el mismo que la clave de búsqueda, devolver el candidato

El tamaño del bloque se elige como la raíz cuadrada de la longitud de la matriz. Por lo tanto, los arreglos con longitud n tienen un tamaño de bloque de √n, ya que en promedio brinda el mejor rendimiento para la mayoría de los arreglos.

Podría ser útil para ilustrar cómo funciona. Así es como Jump Search multaría el valor 78 en una matriz de 9 elementos:

Ilustración encontrando el valor 78 en una matriz ordenada con búsqueda por salto

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.

Saltar pasos de búsqueda

Entradas:

  • Matriz/lista A de tamaño n
  • Clave de búsqueda elemento

Producción:

  • Índice de la clave de búsqueda coincidente o -1 si no se encuentra el elemento

Pasos

  • Paso 1: Encuentre la longitud de la lista de fuentes ordenada - n = len(A)
  • Paso 2: Determinar el tamaño de bloque adecuado - m = √n
  • Paso 3: La iteración comienza en el índice del elemento en i = 0 con un paso de m y continúa hasta que la ventana llega al final de la lista.
  • Paso 4: Compara A[i+m] (i+m es el último índice de un bloque) y el elemento
    • a) If A[i+m] == item, Return i+m; Code Exits
    • b) If A[i+m] > item, Proceed to the linear search inside the block known as derived list B = A[i: i+m]
      • Iterate and compare each element of the list with the search key and return the matching i if found; Code Exits
    • c) If A[i+m] < item, Proceed with the next iteration to Step 4 :arrows_clockwise:
  • Paso 5: Iterar los elementos de la lista que no caben en el bloque y devolver el índice coincidente i. Si no se encontraron coincidencias, devuelva -1; Salidas de código

Ahora que entendemos cómo funciona, ¡implementemos este algoritmo en Python!

Implementación

Sabiendo cómo funciona Jump Search, avancemos e implementémoslo en Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
'''
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)

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

Habrás notado que el Paso 4b y el Paso 5 tienen una función linear_search() invocada. La función linear_search() se activa en uno de los siguientes escenarios.

  • Paso 4b - Cuando hay un cambio en comparación. Si el último elemento de un bloque/ventana es mayor que el elemento, se activa la búsqueda_lineal().

  • Paso 5 - Los elementos restantes de la lista fuente A que no caben en un bloque se pasan como una lista derivada a la función linear_search().

La función linear_search() se puede escribir así:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
'''
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 a la función linear_search() como una lista derivada. La comparación se realiza contra cada elemento de la lista derivada B.

El índice coincidente de la lista derivada se agrega al índice del bloque de origen para proporcionar la posición de índice exacta del elemento en la lista de origen. Si no se encuentran coincidencias, devolvemos -1 para indicar que no se encontró el elemento.

El fragmento completo se puede encontrar aquí.

Benchmarking: búsqueda de salto frente a búsqueda lineal

El tiempo de ejecución de Jump Search se puede comparar con Linear Search. La siguiente visualización ilustra cómo funcionan los algoritmos al buscar un elemento cerca del final de una matriz ordenada. Cuanto más corta sea la barra, mejor:

Gráfico que compara el rendimiento de Jump Search con el de Linear Search. Para listas de números más grandes, la búsqueda por salto funciona 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 O grande

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 encuentra se encuentra al final de la lista.

Para una lista de n elementos y un tamaño de bloque de m, Jump Search idealmente realizaría n/m saltos. Teniendo en cuenta que el tamaño del bloque es √n, el tiempo de ejecución también sería O(√n).

Esto coloca a Jump Search entre la búsqueda lineal (peor) con una complejidad de tiempo de ejecución de O(n) y la búsqueda binaria (mejor) con una complejidad de tiempo de ejecución de O(log n). Por lo tanto, Jump Search se puede usar 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.