Chapter 15: Búsquedas

Las búsquedas son operaciones muy habituales en computación. Cada vez que pulsamos Ctrl+F para “encontrar”, o usamos el teclado para seleccionar un objeto, o cuando un servidor web extrae información de un cliente para presentarle una página personalizada, estamos haciendo una búsqueda.

Existen muchas formas de buscar datos. Google ha basado su multimillonaria compañía en este hecho. En este capítulo introduciremos los dos métodos más simples para realizar búsquedas; búsqueda lineal y búsqueda binaria.

15.1 Leer Desde Un Archivo

Antes de empezar a discutir el cómo buscar, necesitamos aprender primero, cómo leer los datos guardados en un archivo. Leer un conjunto de datos desde un archivo, es una forma más divertida que tener que hacerlo a mano repetidamente.

Pongamos que tenemos que crear un programa que nos permita encontrar rápidamente el nombre de un súper villano. Para comenzar, nuestro programa necesita una base datos de super villanos. Descarga y guarda el siguiente archivo:
http://ProgramArcadeGames.com/chapters/16_searching/super_villains.txt
Todos son nombres aleatorios generados por el website nine.frenchboys.net. De todas formas, en la última visita que hice al website, éste ya no generaba súper villanos.

Guarda el archivo y recuerda dónde lo hiciste.

En el mismo directorio donde se encuentra super_villains.txt, crea, guarda y ejecuta el siguiente programa Python:

file = open("super_villains.txt")

for line in file:
    print(line)

En este código, aparece tan solo un nuevo comando; open. Como es una función incorporada en Python, tal como print, no tenemos necesidad de usar un import. Los detalles completos de esta función los puedes encontrar en la documentación de Python. Pero en estos momentos, la documentación de ese comando es tan técnica, que no merece la pena perder el tiempo en ella.

A pesar de que el programa anterior proporciona una manera simple de leer un archivo, tiene dos problemas. En la línea 1 abrimos un archivo y lo dejamos preparado para leerlo. El nombre del archivo va entrecomillado. La nueva variable file es un objeto que representa al archivo que está siendo leído. La línea 3 muestra cómo un sencillo bucle for puede usarse para leer un archivo línea a línea. Piensa en file como una lista de líneas, donde la nueva variable line, irá tomando los valores de cada una de esas líneas, a medida que el programa itera a través del bucle.

Intenta ejecutar el programa. Verás que uno de los problemas que tiene, es que el texto se imprime a doble espacio. La razón de esto, es que cada línea extraída del archivo y guardada en la variable line, incluye un retorno de carro como parte de la cadena de texto. ¿Recuerdas del Capítulo 1, el retorno de carro y el avance de línea? Y como bien sabes, la sentencia print añade otro retorno de carro, con el resultado de que tenemos una salida a doble espacio.

El segundo problema que tenemos es que el archivo ha sido abierto, pero no cerrado. Este problema no es tan obvio como el del doble espacio, pero es importante. El sistema operativo Windows solo puede abrir unos cuantos archivos a la vez. Un archivo, normalmente, solo puede ser abierto por un programa a la vez. Si dejamos el archivo abierto, evitaremos que otros programas puedan usarlo, además de ocupar recursos del sistema. Tenemos que cerrar el archivo de forma que Windows sepa que nuestro programa ya no lo está usando. En nuestro caso no es tan crítico, ya que cuando cualquier programa termina de ejecutarse, Windows cierra automáticamente cualquier archivo que se haya dejado abierto. Pero como eso es un mal hábito, vamos a actualizar nuestro código:

file = open("super_villains.txt")

for line in file:
    line = line.strip()
    print(line)

file.close()

El código anterior funciona mejor. Tiene dos elementos nuevos. En la línea 4 se hace una llamada al método strip, incluido en cada clase String. Esta función devuelve una cadena nueva, sin los espacios finales ni los retornos de carro de la cadena original. El método no altera la cadena original, en todo caso, crea una nueva. La siguiente línea de código no funcionaría por si sola :

line.strip()

Si la programadora quiere que la variable original haga referencia a la nueva cadena, deberá asignarla tal como se ve en la línea 4.

La segunda novedad está en la línea 7. En ella se cierra el archivo evitando que sea el sistema operativo el encargado de hacerlo más adelante.

15.2 Volcado A Un Array

Es bastante útil volcar los contenidos de un archivo en un array, de manera que el programa los pueda procesar posteriormente. En Python lo podemos hacer fácilmente de la siguiente manera:

# Leemos un archivo desde el disco y lo pasamos a un array
file = open("super_villains.txt")

lista_nombres = []
for line in file:
    line = line.strip()
    lista_nombres.append(line)

file.close()

Aquí combinamos una característica nueva, leer desde un archivo, con otra vista previamente, cómo crear un array vacío y rellenarlo con datos que le vamos pasando, tal como vimos en el Capítulo 7. Para comprobar que el archivo ha sido volcado correctamente en el array, el programador podría imprimir la longitud del array:

print("Había",len(lista_nombres),"nombres en el archivo.")

O el programador podría mostrar el contenido completo del array:

for nombre in lista_nombres:
    print(nombre)

Antes de continuar con otras búsquedas diferentes, avanza y comprueba que puedes leer el archivo.

15.3 Búsqueda Lineal

Si un programa tiene un conjunto de datos en un array, ¿cómo podemos hacer para encontrar un elemento específico? Esto se puede hacer de dos formas. La primera es utilizar una búsqueda lineal. Empieza por el primero, y continúa comparando elementos hasta que encuentra el deseado (o se queda sin elementos.)

15.3.1 Algoritmo de Búsqueda Lineal

# Búsqueda Lineal
clave = "Morgana la Arpía"

i = 0
while i < len(lista_nombres) and lista_nombres[i] != clave:
    i += 1

if i < len(lista_nombres):
    print( "El nombre se encuentra en la posición", i)
else:
    print( "El nombre no se encuentra en la lista." )

La búsqueda lineal es bastante sencilla. En la línea 2 se establece una variable incremental que lleva la cuenta de cuál es el siguiente elemento de la lista que el programa necesita comprobar. El primer elemento que debe ser comprobado es el cero, por lo que establecemos i a cero.

La línea siguiente es un poco más compleja. El programa debe iterar hasta que suceda alguno de los siguientes hechos: que encuentre el elemento, o que se quede sin elementos que buscar. El primer comparador mira si el elemento actual es menor que la longitud de la lista. Si es así, seguimos iterando. El segundo comparador mira si el elemento actual en la lista de nombres es igual al nombre que estamos buscando.

Comprobar que no nos hemos quedado sin elementos de búsqueda es lo primero que debe hacerse. De otra forma, el programa buscaría un elemento inexistente, lo que produciría un error.

En la línea 4 se avanza hacia el siguiente elemento si las condiciones de la línea 3 se cumplen.

Al final del bucle, el programa comprueba si el final de la lista se alcanzó en la línea 6. Recuerda, una lista de n elementos se enumera de 0 a n-1. Por lo tanto, si i es igual a la longitud de la lista, hemos acabado. Si es menor, hemos encontrado el elemento.

15.4 Variantes De La Búsqueda Lineal

Podemos usar variantes de la búsqueda lineal para crearnos distintos algoritmos. Digamos que tenemos, por ejemplo, una lista de aliens. Quizás nos interese comprobar si en el grupo hay un alien verde, o si son todos verdes, o cuáles son verdes.

Para empezar, necesitamos definir nuestro alien:

class Alien:
    """ Clase que define un alien"""
    def __init__(self, color, peso):
	""" Constructor. Establece peso y color"""
	self.color = color
	self.peso = peso

Luego debemos crearnos una función que compruebe si posee el rasgo que estamos buscando. En nuestro caso; ¿es verde? Asumiremos que el color es una cadena de texto que convertiremos a mayúsculas para eliminar el riesgo de algún conflicto con las minúsculas.

def tiene_propiedad(mi_alien):
    """ Comprobamos si un item posee esa propiedad.
    En este caso, ¿es verde el alien? """
    if mi_alien.color.upper() == "VERDE":
        return True
    else:
        return False

15.4.1 Al Menos Uno De Los Elementos Tiene Esa Propiedad?

¿Al menos uno de los aliens es verde? Lo podemos comprobar. El algoritmo básico tras ésta comprobación es:

def comprueba_si_un_elemento_tiene_propiedad_v1(mi_lista):
    """ Devuelve true si al menos un item tiene esa
    propiedad. """
    i = 0
    while i < len(mi_lista) and not tiene_propiedad(lista[i]):
        i += 1

    if i < len(mi_lista):
        # Se encontró un elemento con esa propiedad
        return True
        
    else:
        # No existe un elemento con esa propiedad
        return False

Esto también se podría hacer con un bucle for. En este caso, el bucle se detendría con un return una vez que el elemento ha sido encontrado. El código es más corto, pero no todos los programadores escogerían esta vía. Algunos programadores piensan que los bucles no deberían terminar prematuramente con declaraciones del tipo return o break. Esto depende claro, de las preferencias personales de cada uno, o de las que tenga la persona que paga la factura.

def comprueba_si_un_elemento_tiene_propiedad_v2(mi_lista):
    """ Devuelve true si al menos un item tiene esa
    propiedad. Funciona como v1, pero con menos código. """
    for item in mi_lista:
        if tiene_propiedad(item):
            return True
    return False

15.4.2 ¿Todos Los Elementos Tienen Una Propiedad?

¿Son verdes todos los aliens? Este código es muy similar al anterior. Encuentra la diferencia e intenta entender las razones del cambio.

def comprueba_si_todos_elementos_tienen_propiedad(mi_lista):
    """ Devuelve true si TODOS los items tienen una propiedad. """
    for item in mi_lista:
        if not tiene_propiedad(item):
            return False
        return True

15.4.3 Creamos Una Lista Con Todos Los Elementos Que Tengan Una Propiedad

¿Qué sucede si necesitas una lista en la que todos los aliens que sean verdes? Esta es una combinación del código anterior, junto con el código para añadir elementos a una lista que vimos en el Capítulo 7.

def obtener_elementos_coincidentes(lista):
    """ Construye una lista completamente nueva con todos los items
    que coincidan con nuestra propiedad. """
    lista_coincidentes = []
    for item in lista:
        if tiene_propiedad(item):
            lista_coincidentes.append(item)
    return lista_coincidentes

¿Cómo ejecutarías todo esto en un test? El código anterior lo podemos combinar con éste para ello:

lista_aliens = []
lista_aliens.append(Alien("Verde", 42))
lista_aliens.append(Alien("Rojo", 40))
lista_aliens.append(Alien("Azul", 41))
lista_aliens.append(Alien("Púrpura", 40))

resultado = comprueba_si_un_elemento_tiene_propiedad_v1(lista_aliens)
print("Resultado del test comprueba_si_un_elemento_tiene_propiedad_v1:", resultado)

resultado = comprueba_si_un_elemento_tiene_propiedad_v2(lista_aliens)
print("Resultado del test comprueba_si_un_elemento_tiene_propiedad_v1:", resultado)

resultado = comprueba_si_todos_elementos_tienen_propiedad(lista_aliens)
print("Resultado del test comprueba_si_todos_elementos_tienen_propiedad:", resultado)

resultado = obtener_elementos_coincidentes(lista_aliens)
print("Número de items devueltos por el test obtener_elementos_coincidentes:", len(resultado))

Puedes ver un ejemplo completo y funcional aquí:
programarcadegames.com/python_examples/show_file.php?file=property_check_examples.py

Los algoritmos anteriores pueden usarse como parte de la solución a un problema mayor, tal como encontrar todas las direcciones no válidas en una lista de clientes.

15.5 Búsqueda Binaria

Posiblemente, una forma más rápida de buscar en una lista sea a través de una búsqueda binaria. El proceso de una búsqueda binaria se puede describir usando como ejemplo el clásico juego de “adivina un número entre 1 y 100”. Para facilitar la comprensión del proceso, vamos a modificar el juego a “adivina un número entre 1 y 128”. El rango de los números es inclusivo, es decir, tanto el 1 como el 128 son posibles también.

Si una persona tuviera que usar la búsqueda lineal como método para adivinar el número secreto, el juego se convertiría en algo muy largo y aburrido.

Adivina un número entre 1 y 128: 1
Muy bajo.
Adivina un número entre 1 y 128: 2
Muy bajo.
Adivina un número entre 1 y 128: 3
Muy bajo.
....
Adivina un número entre 1 y 128: 93
Muy bajo.
Adivina un número entre 1 y 128: 94
Correcto!

La mayoría usaría una búsqueda binaria para encontrar el número. Éste sería un buen ejemplo de ello:

Adivina un número entre 1 y 128: 64
Muy bajo.
Adivina un número entre 1 y 128: 96
Muy alto.
Adivina un número entre 1 y 128: 80
Muy bajo.
Adivina un número entre 1 y 128: 88
Muy bajo.
Adivina un número entre 1 y 128: 92
Muy bajo.
Adivina un número entre 1 y 128: 94
Correcto!

En cada una de las pasadas del juego, al obtener un “alto” o “bajo”, la persona que adivina es capaz de restringir, a la mitad, el problema.

En una búsqueda binaria, es necesario hacer un seguimiento de los límites, superior e inferior, de la lista que contiene la respuesta. El ordenador o la persona que adivina, escoge el punto medio de esos elementos. Volviendo a nuestro ejemplo:

Para un límite inferior de 1, y un límite superior de 128, el punto medio es $\dfrac{1+128}{2} = 64.5$.

Adivina un número entre 1 y 128: 64
Muy bajo.

Para un límite inferior de 65, y un límite superior de 128, el punto medio es $\dfrac{65+128}{2} = 96.5$.

Adivina un número entre 1 y 128: 96
Muy alto.

Para un límite inferior de 65, y un límite superior de 95, el punto medio es $\dfrac{65+95}{2} = 80$.

Adivina un número entre 1 y 128: 80
Muy bajo.

Para un límite inferior de 81, y un límite superior de 95, el punto medio es $\dfrac{81+95}{2} = 88$.

Adivina un número entre 1 y 128: 88
Muy bajo.

Para un límite inferior de 89, y un límite superior de 95, el punto medio es $\dfrac{89+95}{2} = 92$.

Adivina un número entre 1 y 128: 92
Muy bajo.

Para un límite inferior de 93, y un límite superior de 95, el punto medio es $\dfrac{93+95}{2} = 94$.

Adivina un número entre 1 y 128: 94
Correcto!

Una búsqueda binaria reduce significativamente el número de intentos. En el peor de los casos se necesitarían 7 intentos para encontrar un número entre 1 y 128. Un intento más elevaría el límite a 256. Para 9 intentos, el número podría estar entre 1 y 512. En sólo 32 intentos, una persona podría encontrar un número entre 1 y 4.2e9.

Para determinar cuán larga podría ser la lista, dado un cierto número de intentos, podríamos usar la fórmula $n=x^{g}$, donde $n$ es el tamaño de la lista y $g$ el número de intentos. Por ejemplo:
$2^7 = 128$ (con 7 intentos se pueden manejar 128 números diferentes)
$2^8 = 256$
$2^9 = 512$
$2^{32} = 4,294,967,296$

Si nuestro problema consiste en determinar el número de intentos, conociendo el tamaño de la lista, podemos recurrir a la función log. Específicamente log base 2. Si no especificamos la base, la mayoría podría asumir que hablamos del logaritmo natural en base $e \approx 2.71828$ que no es precisamente lo que queremos. Por ejemplo, usando log base 2 para encontrar el número de intentos, tendríamos:
$log_2 128 = 7$
$log_2 65,536 = 16$

¡Bueno, vale! ya hemos tenido bastantes matemáticas. Lo que nos interesa; ¿dónde está el código? Pues el código para realizar una búsqueda binaria es un poco más complicado que el de una búsqueda lineal:

# Búsqueda Binaria
clave = "Morgana la Arpía"
limite_inferior = 0
limite_superior = len(lista_nombres)-1
encontrado = False

# Iteramos hasta encontrar el objeto, o donde se encuentran nuestros límites superior/inferior

while limite_inferior <= limite_superior and not encontrado:

    # Hallamos la posición intermedia
    posicion_intermedia = (limite_inferior+limite_superior) // 2
    
    # Determinamos si:
    # desplazamos hacia arriba el límite superior, o
    # desplazamos hacia abajo el límite inferior, o si
    # ya hemos encontrado lo que buscábamos
    if lista_nombres[posicion_intermedia] < clave:
	    limite_inferior = posicion_intermedia + 1
    elif lista_nombres[posicion_intermedia] > clave:
	    limite_superior = posicion_intermedia - 1
    else:
        encontrado = True

if encontrado:
    print("El nombre se encuentra en la posición", posicion_intermedia)
if not found:
    print("El nombre no se encontraba en la lista.")

Como las listas comienzan por el elemento cero, la línea 3 establecería el límite inferior a cero. La línea 4 establecería el límite superior como la longitud de la lista menos uno. Por lo tanto, para una lista de 100 elementos, el límite inferior sería 0 y el superior, 99.

La variable booleana de la línea 5 se usaría para permitir que el bucle while supiera que el elemento en cuestión ha sido encontrado.

La línea 6 comprueba si el elemento fue encontrado o nos hemos quedado sin elementos que buscar. Si sucediera esto último, terminaríamos con que el límite inferior se igualaría al superior.

La línea 7 encuentra la posición intermedia. Es posible llegar a una posición intermedia igual a 64.5. Pero sabemos que no es posible que exista tal posición 64.5. (Aunque J.K. Rowling fue lo suficientemente lista para crear un andén $9\frac{3}{4}$, eso no funcionaría en nuestro caso.) La mejor manera de manejar esta situación, es utilizar el operador // que introdujimos en el Capítulo 5. Es parecido al operador /, con la diferencia de que solo devuelve resultados enteros. Por ejemplo, 11 // 2 daría 5, en lugar de 5.5.

Empezando en la línea 8, el programa comprueba si nuestra predicción ha sido alta, baja o correcta. Si ha sido baja, el límite inferior asciende justo por encima de ella. Si nuestra predicción ha sido alta, el límite superior desciende justo por debajo de ella. Pero si hemos dado en la diana, encontrado se establece a True finalizando la búsqueda.

Dada una lista con 100 elementos, una persona podría intuir razonablemente, que de media con una búsqueda lineal, el programa tendría que comprobar 50 elementos antes de encontrar el correcto. Con una búsqueda binaria, debería aún, realizar al menos siete intentos. En cursos avanzados sobre algoritmos, podrás encontrar la fórmula exacta. De momento en este curso, basta con que asumamos que los casos promedio y peor son lo mismo.

15.6 Repaso

15.6.1 Test

Haz click para ir al Test.

15.6.2 Ejercicios

Haz click para ir a los Ejercicios.

15.6.3 Taller

Haz click para ir al Taller.

You are not logged in. Log in here and track your progress.