Breaking

Post Top Ad

Your Ad Spot

viernes, 5 de julio de 2019

Algoritmos de búsqueda en Python

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 en la búsqueda, 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 optimizan con el tiempo como resultado de la evolución constante 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 dado 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, generalmente como una función que devuelve un Booleanvalor de TrueoFalsecuando 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 , con ese nombre porque nos permiten determinar si un objeto determinado es miembro de una colección.
Estos operadores pueden usarse con cualquier estructura de datos iterable en Python, incluidas cadenas, listas y tuplas.
  • in- Devuelve Truesi el elemento dado es parte de la estructura.
  • not in- Devuelve Truesi el elemento dado no es parte de la estructura.
>>> 'apple' in ['orange', 'apple', 'grape']
True  
>>> 't' in 'stackabuse'
True  
>>> 'q' in 'stackabuse'
False  
>>> 'q' not in 'stackabuse'
True  
Los operadores de membresía son suficientes cuando todo lo que tenemos que hacer es encontrar si existe una subcadena dentro de una cadena determinada o determinar si dos cadenas, listas o tuplas se intersecan 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 los operadores integrados y se pueden utilizar para buscar valores de forma 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 poder determinar su existencia.

Busqueda lineal

La búsqueda lineal es uno de los algoritmos de búsqueda más simples y los más fáciles de entender. Podemos imaginarlo como una versión progresiva de nuestra propia implementación del inoperador 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:
def LinearSearch(lys, element):  
    for i in range (len(lys)):
        if lys[i] == element:
            return i
    return -1
Así que si usamos la función para calcular:
>>> print(LinearSearch([1,2,3,4,5,2,1], 2))
Al ejecutar el código, nos saludan con:
1  
Este es el índice de la primera aparición del elemento que estamos buscando, teniendo en cuenta que los índices de Python se basan en 0.
La complejidad del tiempo de la búsqueda lineal es O (n) , lo que significa que el tiempo que se tarda en 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 utilizando 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 para 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 ordene antes de comenzar la búsqueda.

Búsqueda binaria

La búsqueda binaria sigue una división y conquista metodología de . 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 valen una matriz ordenada, el algoritmo se compara valcon el valor del elemento central de la matriz, al que llamaremos mid.
  • Si mides el elemento que estamos buscando (mejor caso), devolvemos su índice.
  • Si no es así, identificamos en qué lado mid vales más probable que esté en función de si vales más pequeño o más grande midy descartamos el otro lado de la matriz.
  • Luego seguimos recursiva o iterativamente los mismos pasos, seleccionamos un nuevo valor para mid, lo comparamos valy descartamos la mitad de las coincidencias posibles en cada iteración del algoritmo.
El algoritmo de búsqueda binario se puede escribir de forma recursiva o iterativa. La recursión 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:
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:
>>> BinarySearch([10,20,30,40,50], 20)
Obtenemos el resultado:
1  
Cuál es el índice del valor que estamos buscando.
La acción que realiza el algoritmo 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 grupo de posibles coincidencias se divide por dos en cada iteración. Esto hace que la complejidad del tiempo de la búsqueda binaria 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 al medio:
>>> print(BinarySearch([4,4,4,4,4], 4))
La ejecución de este fragmento de código dará como resultado el índice del elemento central:
1  
Para comparación, realizar una búsqueda lineal en la misma matriz devolvería:
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 igual que 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 3el 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 división y conquista que se derivan de la búsqueda binaria, examinemos algunos de ellos a continuación.

Saltar búsqueda

La búsqueda por salto es similar a la búsqueda binaria en el sentido de que funciona en una matriz ordenada y utiliza un enfoque de división y conquista similar para buscar a través de ella.
Se puede clasificar como una mejora del algoritmo de búsqueda lineal, ya que depende de la búsqueda lineal para realizar la comparación real cuando se busca un valor.
Dada una matriz ordenada, en lugar de buscar incrementalmente los elementos de la matriz, buscamos en saltos . Así que en nuestra lista de entrada lys, si tenemos un tamaño de salto saltarnuestro algoritmo tendrá en cuenta 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 vimos y su índice. Cuando encontramos un conjunto de valores dondelys[i]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:
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 por salto con esta entrada:
>>> 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 al calcular 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 rightvariable, que es el mínimo de la longitud de la matriz menos 1, o el valor de left+jump, que en nuestro caso sería 0 + 3 = 3. Como 3 es menor que 8, usamos 3 como el valor de right.
  • Ahora comprobamos si nuestro elemento de búsqueda, 5, está entre lys[0]lys[3]Como 5 no está entre 1 y 4, seguimos adelante.
  • Luego, hacemos los cálculos nuevamente y verificamos si nuestro elemento de búsqueda está entre lys[3]lys[6], donde 6 es 3 + salto. Desde 5 es entre 4 y 7, hacemos una búsqueda lineal de los elementos entre lys[3]lys[6]y devolver el índice de nuestro elemento como:
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, ubicando la búsqueda por salto entre la búsqueda lineal y los algoritmos 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 ( /).
En la mayoría de las CPU, el uso del operador de división es costoso en comparación con otras operaciones aritméticas básicas (suma, resta y multiplicación), porque la implementación del algoritmo de división es iterativa.
El costo en sí mismo es muy pequeño, pero cuando el número de elementos para buscar es muy grande y el número de operaciones de división que necesitamos realizar aumenta, el costo puede sumarse de manera incremental. Por lo tanto, la búsqueda por 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 por salto sea más rápida, podemos usar la búsqueda binaria u otra búsqueda por salto interno 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

La búsqueda de Fibonacci es otro algoritmo de división y conquista que tiene similitudes tanto con la búsqueda binaria como con la búsqueda por salto. Recibe su nombre porque utiliza los números de Fibonacci para calcular el tamaño del bloque o el 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 fibMfibM_minus_1fibM_minus_2dónde fibM_minus_1fibM_minus_2son los dos números inmediatamente antes fibMen la secuencia:
fibM = fibM_minus_1 + fibM_minus_2  
Inicializamos los valores a 0,1, y 1 o los tres primeros números en la secuencia de Fibonacci para evitar un error de índice en el caso de que nuestra matriz de búsqueda lyscontenga un número muy pequeño 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 antes de ella como los valores de fibM_minus_1fibM_minus_2Mientras que la matriz tiene elementos restantes y el valor de fibMes mayor que uno, nosotros:
  • Compare valcon el valor del bloque en el rango hasta fibM_minus_2, y devuelva el índice del elemento si coincide.
  • Si el valor es mayor que el elemento que estamos viendo actualmente, movemos los valores de fibMfibM_minus_1fibM_minus_2dos 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 fibMfibM_minus_1fibM_minus_2un paso hacia abajo en la secuencia de Fibonacci.
Echemos un vistazo a la implementación de Python de este algoritmo:
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:
>>> print(FibonacciSearch([1,2,3,4,5,6,7,8,9,10,11], 6))
Veamos el proceso paso a paso de esta búsqueda:
  • Determinar el número de Fibonacci más pequeño mayor o igual que la longitud de la lista como fibMen este caso, el número de Fibonacci más pequeño que cumple nuestros requisitos es 13.
  • Los valores serían asignados como:
    • fibM = 13
    • fibM menos 1 = 8
    • fibM menos 2 = 5
    • índice = -1
  • A continuación, verificamos el elemento lys[4]donde 4 es el mínimo de -1 + 5. Como el valor de lys[4]es 5, que es más pequeño que el valor que buscamos, movemos los números de Fibonacci un paso hacia abajo en la secuencia, haciendo que los valores:
    • fibM = 8
    • fibM menos 1 = 5
    • fibM menos 2 = 3
    • índice = 4
  • A continuación, verificamos el elemento lys[7]donde 7 es el mínimo de 4 + 3. Como 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 menos 1 = 2
    • fibM menos 2 = 1
    • índice = 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 se espera, es:
5  
La complejidad del tiempo 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 utilizar 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 ser almacenadas en la memoria caché de la CPU o en la RAM, ya que busca elementos en pasos de mayor tamaño y no en un tamaño fijo.

Búsqueda exponencial

La búsqueda exponencial es otro algoritmo de búsqueda que se puede implementar de manera muy simple en Python, en comparación con la búsqueda por salto y la búsqueda de Fibonacci, que son un poco complejas. También es conocido por los nombres de búsqueda al galope , búsqueda de duplicación y búsqueda de 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 el elemento que estamos buscando es probable que sea
  • Usando la búsqueda binaria del rango para encontrar el índice exacto del artículo
La implementación de Python del algoritmo de búsqueda exponencial es:
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:
>>> print(ExponentialSearch([1,2,3,4,5,6,7,8],3))
El algoritmo funciona por:
  • Verificando si el primer elemento de la lista coincide con el valor que estamos buscando, ya que lys[0]es 1 y estamos buscando 3, establecemos el índice en 1 y seguimos adelante.
  • Repasando todos los elementos de la lista, y mientras el elemento en la posición del índice es menor o igual a nuestro valor, aumenta exponencialmente el valor de indexen múltiplos de dos:
    • índice = 1, lys[1]es 2, que es menor que 3, por lo que el índice se multiplica por 2 y se establece en 2.
    • índice = 2, lys[2]es 3, que es igual a 3, por lo que el índice se multiplica por 2 y se establece en 4.
    • índice = 4, lys[4]es 5, que es mayor que 3; El bucle está roto en este punto.
  • Luego realiza una búsqueda binaria cortando la lista; arr[:4]En Python, esto significa que la lista secundaria contendrá todos los elementos hasta el cuarto elemento, por lo que estamos llamando:
>>> BinarySearch([1,2,3,4], 3)
que volvería:
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 el tiempo O (log i) , donde i es el índice del elemento que estamos buscando. En el peor de los casos, la complejidad del tiempo es O (log n) , cuando el último elemento es el elemento que estamos buscando ( n es la longitud de la matriz).
La búsqueda exponencial funciona mejor que la búsqueda binaria cuando el elemento que buscamos está más cerca del principio de la matriz. En la práctica, utilizamos 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

La búsqueda de interpolación es otro algoritmo de división y conquista, similar a la búsqueda binaria. A diferencia de la búsqueda binaria, no siempre comienza la búsqueda en el medio. La búsqueda de interpolación calcula la posición probable del elemento que estamos buscando mediante la fórmula:
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. Esto se calcula como un valor más alto cuando val está más cerca del elemento al final de la matriz ( lys[high]), y más bajo cuando val está más cercano al elemento al comienzo de la matriz ( lys[low])
  • bajo - el índice de inicio 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 vales menor que lys[index], el valor para el índice se vuelve a calcular utilizando la fórmula de la sub-matriz izquierda
  • Si el valor de vales mayor que lys[index], el valor para el índice se vuelve a calcular utilizando la fórmula para la sub-matriz derecha
Sigamos adelante e implementemos la búsqueda de interpolación usando Python:
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:
>>> print(InterpolationSearch([1,2,3,4,5,6,7,8], 6))
Nuestros valores iniciales serían:
  • val = 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 estamos buscando, dejamos de ejecutar y devolvemos el resultado:
5  
`
Si tenemos un gran número de elementos, y nuestro índice no se puede calcular en una iteración, seguimos volviendo a calcular los valores para el índice después de ajustar los valores de alto y bajoen nuestra fórmula.
La complejidad temporal de la búsqueda de interpolación es O (log log n) cuando los valores se distribuyen uniformemente. Si los valores no están distribuidos uniformemente, la complejidad del tiempo en el peor de los casos es O (n) , lo mismo que la búsqueda lineal.
La búsqueda de interpolación funciona mejor en arreglos ordenados 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 más probable que encuentre 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 los lenguajes de programación más antiguos como Java, Fortran, C, C ++, etc. Una de las ventajas clave de usar Python para implementar algoritmos de búsqueda es que no tiene que preocuparse por la conversión o la escritura explícita.
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 realizar cambios en el código de los algoritmos que utilizan el elemento de búsqueda para los 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:
>>> print(BinarySearch([4,4,4,4,4], 4))

Conclusión

Hay muchas formas posibles de buscar un elemento dentro de una colección. En este artículo, intentamos analizar algunos algoritmos de búsqueda y sus implementaciones en Python.
La elección del algoritmo a utilizar se basa en los datos que tiene que buscar; Su matriz de entrada, que hemos llamado lysen todas nuestras implementaciones.
  • Si desea buscar en una matriz no clasificada o buscar 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 que desea buscar sin usar el operador de división, puede usar la búsqueda por salto o la búsqueda por 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 clasificada también se distribuye uniformemente, el algoritmo de búsqueda más rápido y más eficiente que se usará sería la búsqueda por interpolación.
Si no está seguro de qué algoritmo usar con una matriz ordenada, pruebe cada uno de ellos junto con la biblioteca de tiempo de Python y elija el que mejor se adapte a su conjunto de datos.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas