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 durante la búsqueda, y cada uno tiene diferentes implementaciones y se basa en diferentes estructuras de datos para realizar el trabajo.

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

    • Operadores de membresía
    • Búsqueda lineal
    • Búsqueda binaria
    • Saltar búsqueda
    • Búsqueda de Fibonacci
    • Búsqueda exponencial
    • Búsqueda de interpolación

    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 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, generalmente como una función que devuelve un Booleanvalor de Trueo Falsecuando un elemento se encuentra 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 , nombrados de esa manera porque nos permiten determinar si un objeto dado es un miembro de una colección.

    Estos operadores se pueden usar 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 'Pharos.sh'
    True
    >>> 'q' in 'Pharos.sh'
    False
    >>> 'q' not in 'Pharos.sh'
    True
    

    Los operadores de pertenencia son suficientes cuando todo lo que tenemos que 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 integrados 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 simplemente poder determinar su existencia.

    Búsqueda lineal

    La búsqueda lineal es uno de los algoritmos de búsqueda más simples y el más fácil de entender. Podemos pensar en ello como una versión mejorada 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
    

    Entonces, si usamos la función para calcular:

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

    Al ejecutar el código, somos recibidos con:

    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 de tiempo 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 utilizando métodos incorporados u operadores existentes, y no es tan rápida o 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 sin clasificar 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 metodología de divide y vencerás . Es más rápida que la búsqueda lineal, pero requiere que la matriz se ordene antes de que se ejecute el algoritmo.

    Suponiendo que estamos buscando un valor valen una matriz ordenada, el algoritmo se compara valcon el valor del elemento medio de la matriz, al que llamaremos mid.

    • Si mides el elemento que estamos buscando (en el mejor de los casos), devolvemos su índice.
    • De lo contrario, identificamos en qué lado de mid vales más probable que esté en función de si vales más pequeño o mayor que mid, y descartamos el otro lado de la matriz.
    • Luego seguimos de forma recursiva o iterativa los mismos pasos, eligiendo un nuevo valor para mid, comparándolo con valy descartando la mitad de las posibles coincidencias 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:

    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 en la mitad izquierda de la matriz
    • Buscando en 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 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 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 intermedio:

    1
    

    Para la 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 como una 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 3como 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 dividir y conquistar 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 a través de los elementos de la matriz de forma incremental, buscamos en saltos. Así que en nuestra lista de entrada lys, si tenemos un tamaño de salto de salto nuestro algoritmo tendrá en cuenta 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]<elemento < lys[i+jump], realizamos una búsqueda lineal con lys[i]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 de saltos con esta entrada:

    >>> print(JumpSearch([1,2,3,4,5,6,7,8,9], 5))
    
    • La búsqueda de salto determinaría primero el tamaño del salto mediante cálculo 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]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 + salto. 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:
    4
    

    La complejidad de tiempo de la búsqueda de saltos es O (√n), donde √n es el tamaño del salto y n es la longitud de la lista, lo que coloca la búsqueda de saltos entre los algoritmos de búsqueda lineal y 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 depende del 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 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 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 la búsqueda de salto 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 depender de 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 usa 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 fibM, fibM_minus_1y fibM_minus_2donde fibM_minus_1y fibM_minus_2son los dos números inmediatamente anteriores fibMen la secuencia:

    fibM = fibM_minus_1 + fibM_minus_2
    

    Inicializamos los valores en 0,1 y 1 o los primeros tres números en la secuencia de Fibonacci para evitar un error de índice en el caso de que nuestra matriz de búsqueda lyscontenga 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 al 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 él como los valores de fibM_minus_1y fibM_minus_2. Mientras 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_2y devuelva el índice del elemento si coincide.
    • Si el valor es mayor que el elemento actualmente estamos viendo, nos movemos los valores de fibM, fibM_minus_1y fibM_minus_2dos pasos hacia abajo en la secuencia de Fibonacci, y restablecer el índice para el índice del elemento.
    • Si el valor es menor que el elemento actualmente estamos viendo, nos movemos los valores de fibM, fibM_minus_1y fibM_minus_2un paso 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))
    

    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 nuestros requisitos es 13.
    • Los valores se asignarían como:
      • fibM = 13
      • fibM_minus_1 = 8
      • fibM_minus_2 = 5
      • índice = -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 más pequeño 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
      • índice = 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
      • í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 esperaba, es:

    5
    

    La complejidad de 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 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 utilizar 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, porque busca elementos en tamaños de paso crecientes 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 bastante simple en Python, en comparación con la búsqueda de salto y la búsqueda de Fibonacci, que son un poco complejas. También es conocido por 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 mediante:

    • Determinar el rango donde es probable que se encuentre el elemento que estamos buscando
    • Usando la búsqueda binaria para el 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 mediante:

    • 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 elemento en la posición del índice es menor o igual a nuestro valor, aumentando exponencialmente el valor de indexen múltiplos de dos:
      • index = 1, lys[1]es 2, que es menor que 3, por lo que el índice se multiplica por 2 y se establece en 2.
      • index = 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 se rompe en este punto.
    • Luego realiza una búsqueda binaria cortando la lista; arr[:4]. En Python, esto significa que la sublista contendrá todos los elementos hasta el cuarto elemento, por lo que en realidad 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 tiempo O (log i), donde i es el índice del elemento que estamos buscando. En el peor de los casos, la complejidad de tiempo 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, utilizamos la búsqueda exponencial porque es uno de los algoritmos de búsqueda más eficientes para matrices infinitas o ilimitadas .

    Búsqueda de interpolación

    La 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 de interpolación calcula la posición probable del elemento que estamos buscando usando la fórmula:

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

    Donde están las variables:

    • lys – nuestra matriz de entrada
    • val – el elemento que estamos buscando
    • índice: índice probable del elemento de búsqueda. Esto se calcula como 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[low])
    • 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 vales menor que lys[index], el valor del índice se vuelve a calcular utilizando la fórmula de la submatriz izquierda.
    • Si el valor de vales mayor que lys[index], el valor del índice se vuelve a calcular utilizando la fórmula de la submatriz de la 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

    Dado que lys[5]es 6, que es el valor que estamos buscando, dejamos de ejecutar y devolvemos el resultado:

    5
    

    Si tenemos una gran cantidad de elementos, y nuestro índice no se puede calcular en una iteración, seguimos volviendo a calcular los valores del índice después de ajustar los valores de alto y bajo en 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 se distribuyen uniformemente, la complejidad temporal del peor caso es O (n), lo mismo que la búsqueda lineal.

    La búsqueda por interpolación funciona mejor en matrices ordenadas y distribuidas uniformemente. Mientras que la búsqueda binaria comienza en el medio y siempre se divide en dos, la búsqueda de 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é utilizar Python para realizar búsquedas?

    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 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 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:

    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.

    La elección del algoritmo que se utilizará se basa en los datos que debe buscar; su matriz de entrada, que hemos llamado lysen todas nuestras implementaciones.

    • Si desea buscar a través de una matriz sin clasificar 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 de manera uniforme, el algoritmo de búsqueda más rápido y eficiente a utilizar 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.

    Etiquetas:

    Deja una respuesta

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