Algoritmos de búsqueda en Python

La búsqueda de datos almacenados en diferentes estructuras de datos es una parte crucial de prácticamente todas las aplicaciones. Hay muchos algoritmos diferentes disponibles...

Introducción

La búsqueda de datos almacenados en diferentes estructuras de datos es una parte crucial de casi todas las aplicaciones.

Hay muchos algoritmos diferentes disponibles para utilizar al buscar, y cada uno tiene diferentes implementaciones y se basa en diferentes estructuras de datos para realizar el trabajo.

Ser capaz de elegir un algoritmo específico para una tarea determinada es una habilidad clave para los desarrolladores y puede significar la diferencia entre una aplicación rápida, confiable y estable y una aplicación que se desmorona con una simple solicitud.

Operadores de membresía

Los algoritmos se desarrollan y se optimizan con el tiempo como resultado de la constante evolución y la necesidad de encontrar las soluciones más eficientes para los problemas subyacentes en diferentes dominios.

Uno de los problemas más comunes en el dominio de la informática es buscar en una colección y determinar si un objeto determinado está presente en la colección o no.

Casi todos los lenguajes de programación tienen su propia implementación de un algoritmo de búsqueda básico, normalmente como una función que devuelve un valor ‘booleano’ de ‘Verdadero’ o ‘Falso’ cuando se encuentra un elemento en una colección determinada de elementos.

En Python, la forma más fácil de buscar un objeto es usar Operadores de membresía, llamado así porque nos permite determinar si un objeto dado es miembro de una colección.

Estos operadores se pueden usar con cualquier estructura de datos iterables en Python, incluidas cadenas, listas y tuplas.

  • in - Devuelve True si el elemento dado es parte de la estructura.
  • not in - Devuelve True si el elemento dado no es parte de la estructura.
1
2
3
4
5
6
7
8
>>> 'apple' in ['orange', 'apple', 'grape']
True
>>> 't' in 'wikihtp'
True
>>> 'q' in 'wikihtp'
False
>>> 'q' not in 'wikihtp'
True

Los operadores de membresía son suficientes cuando todo lo que necesitamos hacer es encontrar si existe una subcadena dentro de una cadena dada, o determinar si dos Cadenas, Listas o Tuplas se cruzan en términos de los objetos que contienen.

En la mayoría de los casos necesitamos la posición del elemento en la secuencia, además de determinar si existe o no; los operadores de membresía no cumplen con este requisito.

Hay muchos algoritmos de búsqueda que no dependen de operadores incorporados y se pueden usar para buscar valores de manera más rápida y/o más eficiente. Además, pueden proporcionar más información, como la posición del elemento en la colección, en lugar de solo poder determinar su existencia.

Búsqueda lineal

Búsqueda lineal es uno de los algoritmos de búsqueda más simples y más fáciles de entender. Podemos considerarlo como una versión mejorada de nuestra propia implementación del operador in de Python.

El algoritmo consiste en iterar sobre una matriz y devolver el índice de la primera aparición de un elemento una vez que se encuentra:

1
2
3
4
5
def LinearSearch(lys, element):
    for i in range (len(lys)):
        if lys[i] == element:
            return i
    return -1

Entonces, si usamos la función para calcular:

1
>>> print(LinearSearch([1,2,3,4,5,2,1], 2))

Al ejecutar el código, somos recibidos con:

1
1

Este es el índice de la primera aparición del elemento que estamos buscando, teniendo en cuenta que los índices de Python están basados ​​en 0.

La complejidad temporal de la búsqueda lineal es O(n), lo que significa que el tiempo necesario para ejecutar aumenta con el número de elementos en nuestra lista de entrada lys.

La búsqueda lineal no se usa a menudo en la práctica, porque se puede lograr la misma eficiencia usando métodos incorporados u operadores existentes, y no es tan rápida ni eficiente como otros algoritmos de búsqueda.

La búsqueda lineal es una buena opción cuando necesitamos encontrar la primera aparición de un elemento en una colección no clasificada porque, a diferencia de la mayoría de los otros algoritmos de búsqueda, no requiere que una colección se clasifique antes de que comience la búsqueda.

Búsqueda binaria

Búsqueda binaria sigue una metodología divide y conquistaras. Es más rápido que la búsqueda lineal, pero requiere que la matriz se ordene antes de ejecutar el algoritmo.

Suponiendo que estamos buscando un valor val en una matriz ordenada, el algoritmo compara val con el valor del elemento central de la matriz, que llamaremos mid.

  • Si mid es el elemento que buscamos (en el mejor de los casos), devolvemos su índice.
  • Si no, identificamos en qué lado de mid val es más probable que esté en función de si val es menor o mayor que mid, y descartamos el otro lado de la matriz.
  • Luego, recursiva o iterativamente, seguimos los mismos pasos, eligiendo un nuevo valor para mid, comparándolo con val y descartando la mitad de las coincidencias posibles en cada iteración del algoritmo.

El algoritmo de búsqueda binaria se puede escribir de forma recursiva o iterativa. La recursividad es generalmente más lenta en Python porque requiere la asignación de nuevos marcos de pila.

Dado que un buen algoritmo de búsqueda debe ser lo más rápido y preciso posible, consideremos la implementación iterativa de la búsqueda binaria:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def BinarySearch(lys, val):
    first = 0
    last = len(lys)-1
    index = -1
    while (first <= last) and (index == -1):
        mid = (first+last)//2
        if lys[mid] == val:
            index = mid
        else:
            if val<lys[mid]:
                last = mid -1
            else:
                first = mid +1
    return index

Si usamos la función para calcular:

1
>>> BinarySearch([10,20,30,40,50], 20)

Obtenemos el resultado:

1
1

Cuál es el índice del valor que buscamos.

La acción que el algoritmo realiza a continuación en cada iteración es una de varias posibilidades:

  • Devolviendo el índice del elemento actual
  • Buscando a través de la mitad izquierda de la matriz
  • Buscando a través de la mitad derecha de la matriz

Solo podemos elegir una posibilidad por iteración, y nuestro conjunto de posibles coincidencias se divide por dos en cada iteración. Esto hace que la complejidad temporal de la búsqueda binaria sea O(log n).

Un inconveniente de la búsqueda binaria es que si hay varias apariciones de un elemento en la matriz, no devuelve el índice del primer elemento, sino el índice del elemento más cercano a la mitad:

1
>>> print(BinarySearch([4,4,4,4,4], 4))

Ejecutar este fragmento de código dará como resultado el índice del elemento central:

1
1

A modo de comparación, realizar una búsqueda lineal en la misma matriz devolvería:

1
0

Cuál es el índice del primer elemento. Sin embargo, no podemos decir categóricamente que la búsqueda binaria no funciona si una matriz contiene el mismo elemento dos veces; puede funcionar como la búsqueda lineal y devolver la primera aparición del elemento en algunos casos.

Si realizamos una búsqueda binaria en la matriz [1,2,3,4,4,5] por ejemplo, y buscamos 4, obtendríamos 3 como resultado.

La búsqueda binaria se usa con bastante frecuencia en la práctica porque es eficiente y rápida en comparación con la búsqueda lineal. Sin embargo, tiene algunas deficiencias, como su dependencia del operador //. Hay muchos otros algoritmos de búsqueda de divide y vencerás que se derivan de la búsqueda binaria, examinemos algunos de ellos a continuación.

Saltar búsqueda

Jump Search es similar a la búsqueda binaria en que funciona en una matriz ordenada y utiliza un enfoque similar de divide y vencerás para buscar a través de ella.

Puede clasificarse como una mejora del algoritmo de búsqueda lineal, ya que depende de la búsqueda lineal para realizar la comparación real al buscar un valor.

Dada una matriz ordenada, en lugar de buscar a través de los elementos de la matriz de forma incremental, buscamos en saltos. Entonces, en nuestra lista de entrada lys, si tenemos un tamaño de salto de jump, nuestro algoritmo considerará los elementos en el orden lys[0], lys[0+jump], lys[0+2jump] , lys[0+3jump] y así sucesivamente.

Con cada salto, almacenamos el valor anterior que miramos y su índice. Cuando encontramos un conjunto de valores donde lys[i]<element<lys[i+jump], realizamos una búsqueda lineal con lys[i] como el elemento más a la izquierda y lys[ i+jump] como el elemento más a la derecha en nuestro conjunto de búsqueda:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import math

def JumpSearch (lys, val):
    length = len(lys)
    jump = int(math.sqrt(length))
    left, right = 0, 0
    while left < length and lys[left] <= val:
        right = min(length - 1, left + jump)
        if lys[left] <= val and lys[right] >= val:
            break
        left += jump;
    if left >= length or lys[left] > val:
        return -1
    right = min(length - 1, right)
    i = left
    while i <= right and lys[i] <= val:
        if lys[i] == val:
            return i
        i += 1
    return -1

Dado que este es un algoritmo complejo, consideremos el cálculo paso a paso de la búsqueda de salto con esta entrada:

1
>>> print(JumpSearch([1,2,3,4,5,6,7,8,9], 5))
  • La búsqueda por salto determinaría primero el tamaño del salto calculando math.sqrt(len(lys)). Como tenemos 9 elementos, el tamaño del salto sería √9 = 3.
  • A continuación, calculamos el valor de la variable derecha, que es el mínimo de la longitud de la matriz menos 1, o el valor de izquierda+salto, que en nuestro caso sería 0+3= 3. Dado que 3 es más pequeño que 8, usamos 3 como el valor de right.
  • Ahora comprobamos si nuestro elemento de búsqueda, 5, está entre lys[0] y lys[3]. Como 5 no está entre 1 y 4, seguimos adelante.
  • A continuación, volvemos a hacer los cálculos y comprobamos si nuestro elemento de búsqueda está entre lys[3] y lys[6], donde 6 es 3+jump. Dado que 5 está entre 4 y 7, hacemos una búsqueda lineal en los elementos entre lys[3] y lys[6] y devolvemos el índice de nuestro elemento como:
1
4

La complejidad temporal de la búsqueda por salto es O(√n), donde √n es el tamaño del salto y n es la longitud de la lista, lo que ubica a la búsqueda por salto entre los algoritmos de búsqueda lineal y de búsqueda binaria en términos de eficiencia.

La ventaja más importante de la búsqueda por salto en comparación con la búsqueda binaria es que no se basa en el operador de división (/).

In most CPUs, usar el operador de división es costoso en comparación con otras operaciones aritméticas básicas (addition, subtraction, and multiplication), because the implementation of the division algorithm is iterative.

El costo en sí mismo es muy pequeño, pero cuando la cantidad de elementos para buscar es muy grande y la cantidad de operaciones de división que necesitamos realizar aumenta, el costo puede aumentar gradualmente. Por lo tanto, la búsqueda de salto es mejor que la búsqueda binaria cuando hay una gran cantidad de elementos en un sistema donde incluso un pequeño aumento en la velocidad es importante.

Para hacer que la búsqueda de salto sea más rápida, podríamos usar la búsqueda binaria u otra búsqueda de salto interna para buscar a través de los bloques, en lugar de confiar en la búsqueda lineal mucho más lenta.

Búsqueda de Fibonacci {#búsqueda de Fibonacci}

Búsqueda de Fibonacci es otro algoritmo de divide y vencerás que tiene similitudes con la búsqueda binaria y la búsqueda de salto. Recibe su nombre porque utiliza números de Fibonacci para calcular el tamaño del bloque o rango de búsqueda en cada paso.

Los números de Fibonacci comienzan con cero y siguen el patrón 0, 1, 1, 2, 3, 5, 8, 13, 21... donde cada elemento es la suma de los dos números que lo preceden inmediatamente.

El algoritmo funciona con tres números de Fibonacci a la vez. Llamemos a los tres números fibM, fibM_minus_1 y fibM_minus_2 donde fibM_minus_1 y fibM_minus_2 son los dos números inmediatamente antes de fibM en la secuencia:

1
fibM = fibM_minus_1 + fibM_minus_2

Inicializamos los valores a 0,1 y 1 o los tres primeros números de la secuencia de Fibonacci para evitar obtener un error de índice en el caso de que nuestra matriz de búsqueda lys contenga una cantidad muy pequeña de elementos.

Luego elegimos el número más pequeño de la secuencia de Fibonacci que es mayor o igual que el número de elementos en nuestra matriz de búsqueda lys, como el valor de fibM, y los dos números de Fibonacci inmediatamente anteriores como los valores de fibM_minus_1 y fibM_minus_2. Mientras que a la matriz le quedan elementos y el valor de fibM es mayor que uno, nosotros:

  • Compara val con el valor del bloque en el rango hasta fibM_minus_2 y devuelve el índice del elemento si coincide.
  • Si el valor es mayor que el elemento que estamos viendo actualmente, movemos los valores de fibM, fibM_minus_1 y fibM_minus_2 dos pasos hacia abajo en la secuencia de Fibonacci y restablecemos el índice al índice del elemento.
  • Si el valor es menor que el elemento que estamos viendo actualmente, movemos los valores de fibM, fibM_minus_1 y fibM_minus_2 un paso hacia abajo en la secuencia de Fibonacci.

Echemos un vistazo a la implementación de Python de este algoritmo:

 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
def FibonacciSearch(lys, val):
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    while (fibM < len(lys)):
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    index = -1;
    while (fibM > 1):
        i = min(index + fibM_minus_2, (len(lys)-1))
        if (lys[i] < val):
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            index = i
        elif (lys[i] > val):
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else :
            return i
    if(fibM_minus_1 and index < (len(lys)-1) and lys[index+1] == val):
        return index+1;
    return -1

Si usamos la función FibonacciSearch para calcular:

1
>>> print(FibonacciSearch([1,2,3,4,5,6,7,8,9,10,11], 6))

Echemos un vistazo al proceso paso a paso de esta búsqueda:

  • Determinar el número de Fibonacci más pequeño mayor o igual a la longitud de la lista como fibM; en este caso, el número de Fibonacci más pequeño que cumple con nuestros requisitos es 13.
  • Los valores se asignarían como:
    • fibM = 13
    • fibM_minus_1 = 8
    • fibM_minus_2 = 5
    • index = -1
  • A continuación, comprobamos el elemento lys[4] donde 4 es el mínimo de -1+5 . Dado que el valor de lys[4] es 5, que es menor que el valor que estamos buscando, movemos los números de Fibonacci un paso hacia abajo en la secuencia, haciendo que los valores:
    • fibM = 8
    • fibM_minus_1 = 5
    • fibM_minus_2 = 3
    • index = 4
  • A continuación, comprobamos el elemento lys[7] donde 7 es el mínimo de 4+3. Dado que el valor de lys[7] es 8, que es mayor que el valor que estamos buscando, movemos los números de Fibonacci dos pasos hacia abajo en la secuencia.
    • fibM = 3
    • fibM_minus_1 = 2
    • fibM_minus_2 = 1
    • index = 4
  • Ahora comprobamos el elemento lys[5] donde 5 es el mínimo de 4+1 . El valor de lys[5] es 6, que es el valor que estamos buscando.

El resultado, como era de esperar es:

1
5

La complejidad temporal para la búsqueda de Fibonacci es O(log n); lo mismo que la búsqueda binaria. Esto significa que el algoritmo es más rápido que la búsqueda lineal y la búsqueda por salto en la mayoría de los casos.

La búsqueda de Fibonacci se puede usar cuando tenemos una gran cantidad de elementos para buscar y queremos reducir la ineficiencia asociada con el uso de un algoritmo que se basa en el operador de división.

Una ventaja adicional de usar la búsqueda de Fibonacci es que puede acomodar matrices de entrada que son demasiado grandes para guardarlas en la memoria caché de la CPU o en la RAM, porque busca a través de elementos en tamaños de paso crecientes, y no en un tamaño fijo.

Búsqueda exponencial

Búsqueda exponencial es otro algoritmo de búsqueda que se puede implementar de forma bastante sencilla en Python, en comparación con la búsqueda por salto y la búsqueda de Fibonacci, que son un poco complejas. También se le conoce con los nombres búsqueda galopante, búsqueda duplicada y búsqueda struzik.

La búsqueda exponencial depende de la búsqueda binaria para realizar la comparación final de valores. El algoritmo funciona por:

  • Determinar el rango donde es probable que se encuentre el elemento que estamos buscando
  • Uso de la búsqueda binaria del rango para encontrar el índice exacto del elemento

La implementación de Python del algoritmo de búsqueda exponencial es:

1
2
3
4
5
6
7
def ExponentialSearch(lys, val):
    if lys[0] == val:
        return 0
    index = 1
    while index < len(lys) and lys[index] <= val:
        index = index * 2
    return BinarySearch( arr[:min(index, len(lys))], val)

Si usamos la función para encontrar el valor de:

1
>>> print(ExponentialSearch([1,2,3,4,5,6,7,8],3))

El algoritmo funciona por:

  • Comprobando si el primer elemento de la lista coincide con el valor que estamos buscando - dado que lys[0] es 1 y estamos buscando 3, establecemos el índice en 1 y seguimos adelante.
  • Pasando por todos los elementos de la lista, y mientras el ítem en la posición del índice es menor o igual a nuestro valor, incrementando exponencialmente el valor de índice en múltiplos de dos:
    • index = 1, lys[1] is 2, which is less than 3, so the index is multiplied by 2 and set to 2.
    • index = 2, lys[2] is 3, which is equal to 3, so the index is multiplied by 2 and set to 4.
    • index = 4, lys[4] is 5, which is greater than 3; the loop is broken at this point.
  • Luego realiza una búsqueda binaria por rebanar la lista; arre[:4]. En Python, esto significa que la sublista contendrá todos los elementos hasta el cuarto elemento, por lo que en realidad estamos llamando:
1
>>> BinarySearch([1,2,3,4], 3)

que devolvería:

1
2

Cuál es el índice del elemento que estamos buscando tanto en la lista original como en la lista dividida que pasamos al algoritmo de búsqueda binaria.

La búsqueda exponencial se ejecuta en tiempo O(log i), donde i es el índice del elemento que estamos buscando. En el peor de los casos, la complejidad temporal es O(log n), cuando el último elemento es el elemento que estamos buscando (siendo n la longitud de la matriz).

La búsqueda exponencial funciona mejor que la búsqueda binaria cuando el elemento que estamos buscando está más cerca del comienzo de la matriz. En la práctica, usamos la búsqueda exponencial porque es uno de los algoritmos de búsqueda más eficientes para arreglos ilimitados o infinitos.

Búsqueda de interpolación

Búsqueda de interpolación es otro algoritmo de divide y vencerás, similar a la búsqueda binaria. A diferencia de la búsqueda binaria, no siempre comienza a buscar en el medio. La búsqueda por interpolación calcula la posición probable del elemento que estamos buscando usando la fórmula:

1
index = low + [(val-lys[low])*(high-low) / (lys[high]-lys[low])]

Donde las variables son:

  • lys - nuestra matriz de entrada
  • val - el elemento que estamos buscando
  • índice - el índice probable del elemento de búsqueda. Se calcula que es un valor más alto cuando val tiene un valor más cercano al elemento al final de la matriz (lys[high]), y más bajo cuando val tiene un valor más cercano al elemento al comienzo de la matriz ( lys[bajo])
  • bajo - el índice inicial de la matriz
  • alto - el último índice de la matriz

El algoritmo busca calculando el valor de index:

  • Si se encuentra una coincidencia (cuando lys[index] == val), se devuelve el índice
  • Si el valor de val es menor que lys[index], el valor del índice se vuelve a calcular usando la fórmula para el subconjunto izquierdo
  • Si el valor de val es mayor que lys[index], el valor del índice se vuelve a calcular usando la fórmula para el subarreglo derecho

Avancemos e implementemos la búsqueda de interpolación usando Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def InterpolationSearch(lys, val):
    low = 0
    high = (len(lys) - 1)
    while low <= high and val >= lys[low] and val <= lys[high]:
        index = low + int(((float(high - low) / ( lys[high] - lys[low])) * ( val - lys[low])))
        if lys[index] == val:
            return index
        if lys[index] < val:
            low = index + 1;
        else:
            high = index - 1;
    return -1

Si usamos la función para calcular:

1
>>> print(InterpolationSearch([1,2,3,4,5,6,7,8], 6))

Nuestros valores iniciales serían:

  • valor = 6,
  • bajo = 0,
  • alto = 7,
  • lys[bajo] = 1,
  • lys[alto] = 8,
  • índice = 0 + [(6-1)*(7-0)/(8-1)] = 5

Como lys[5] es 6, que es el valor que buscamos, dejamos de ejecutar y devolvemos el resultado:

1
5

Si tenemos una gran cantidad de elementos y nuestro índice no se puede calcular en una iteración, seguimos calculando nuevamente los valores para índice después de ajustar los valores de alto y bajo en nuestra fórmula.

La complejidad temporal de la búsqueda por interpolación es O(log log n) cuando los valores se distribuyen uniformemente. Si los valores no se distribuyen uniformemente, la complejidad temporal del peor de los casos es O(n), lo mismo que la búsqueda lineal.

La búsqueda por interpolación funciona mejor en arreglos ordenados y distribuidos uniformemente. Mientras que la búsqueda binaria comienza en el medio y siempre se divide en dos, la búsqueda por interpolación calcula la posición probable del elemento y verifica el índice, lo que hace que sea más probable encontrar el elemento en un número menor de iteraciones.

¿Por qué usar Python para buscar?

Python es altamente legible y eficiente en comparación con lenguajes de programación más antiguos como Java, Fortran, C, C++, etc. Una ventaja clave de usar Python para implementar algoritmos de búsqueda es que no tiene que preocuparse por la conversión o el tipeo explícito.

En Python, la mayoría de los algoritmos de búsqueda que discutimos funcionarán igual de bien si estamos buscando una cadena. Tenga en cuenta que tenemos que hacer cambios en el código de los algoritmos que usan el elemento de búsqueda para cálculos numéricos, como el algoritmo de búsqueda de interpolación.

Python también es un buen lugar para comenzar si desea comparar el rendimiento de diferentes algoritmos de búsqueda para su conjunto de datos; construir un prototipo en Python es más fácil y rápido porque puede hacer más con menos líneas de código.

Para comparar el rendimiento de nuestros algoritmos de búsqueda implementados con un conjunto de datos, podemos usar la biblioteca de tiempo en Python:

1
2
3
4
5
6
import time

start = time.time()
# call the function here
end = time.time()
print(start-end)

Conclusión

Hay muchas formas posibles de buscar un elemento dentro de una colección. En este artículo, intentamos discutir algunos algoritmos de búsqueda y sus implementaciones en Python.

Elegir qué algoritmo usar se basa en los datos que tiene que buscar; su matriz de entrada, que hemos llamado lys en todas nuestras implementaciones.

  • Si desea buscar a través de una matriz no ordenada o encontrar la primera aparición de una variable de búsqueda, la mejor opción es la búsqueda lineal.
  • Si desea buscar a través de una matriz ordenada, hay muchas opciones, de las cuales el método más simple y rápido es la búsqueda binaria.
  • Si tiene una matriz ordenada en la que desea buscar sin usar el operador de división, puede usar la búsqueda por salto o la búsqueda de Fibonacci.
  • Si sabe que es probable que el elemento que está buscando esté más cerca del inicio de la matriz, puede usar la búsqueda exponencial.
  • Si su matriz ordenada también se distribuye uniformemente, el algoritmo de búsqueda más rápido y eficiente para usar sería la búsqueda por interpolación.

Si no está seguro de qué algoritmo usar con una matriz ordenada, simplemente pruebe cada uno de ellos junto con la biblioteca de tiempo de Python y elija el que funcione mejor con su conjunto de datos. e datos.