Los 7 mejores algoritmos para estructuras de datos en Python

Introducción

Los algoritmos y las estructuras de datos son los elementos fundamentales que también pueden respaldar de manera eficiente el proceso de desarrollo de software en la programación. Python, un lenguaje fácil de codificar, tiene muchas características como una lista, un diccionario y un conjunto, que son estructuras de datos integradas para el lenguaje Python. Sin embargo, los magos se desatan al aplicar los algoritmos en estas estructuras. Los algoritmos son instrucciones o un conjunto de reglas o un proceso matemático y operaciones mediante los cuales se llega a una solución. Cuando se usan juntos, pueden convertir un script sin formato en una aplicación altamente optimizada, dependiendo de las estructuras de datos a disposición del programador.

Este artículo analizará los 7 algoritmos principales para estructuras de datos en Python.

¿Por qué son importantes los algoritmos para las estructuras de datos en Python?

• Rendimiento optimizado: Las personas crean algoritmos para entidades que pretenden completar estos trabajos en condiciones ideales. El uso de las estructuras de datos correctas ayuda a minimizar el tiempo y el espacio, lo que hace que los programas se ejecuten de manera más eficiente. Por lo tanto, si se utiliza con una estructura de datos como el árbol de búsqueda binario, el algoritmo de búsqueda adecuado minimiza sustancialmente el tiempo empleado en la búsqueda.
• Manejo de grandes cantidades de datos:Los datos a gran escala deben procesarse en el menor tiempo posible. Por lo tanto, la información requiere algoritmos eficientes. Si no se utilizan los algoritmos adecuados, varias operaciones con estructuras de datos consumirán mucho tiempo y recursos o incluso se convertirán en limitaciones para el rendimiento.
• Organización de datos: Las técnicas ayudan a gestionar los datos en las estructuras de datos de los sistemas informáticos. Por ejemplo, los algoritmos de ordenación como Quicksort y Mergesort utilizan elementos en forma de matriz o listas enlazadas para facilitar la búsqueda y el manejo.
• Almacenamiento optimizado:También puede saber cómo almacenar datos en una estructura de la forma más eficiente posible, utilizando la menor cantidad de memoria posible. Por ejemplo, las funciones hash en los algoritmos hash garantizan que es probable que diferentes conjuntos de datos se asignen a otras ubicaciones en una tabla hash, lo que reduce el tiempo necesario para buscar dichos datos.
• Optimización de la biblioteca:La mayoría de las bibliotecas de Python como NumPy, Pandas y TensorFlow dependen de algoritmos estructurales para analizar la estructura de los datos. El conocimiento de estos algoritmos permite a los desarrolladores utilizar estas bibliotecas de forma óptima y participar en el proceso de evolución de dichas bibliotecas.

Los 7 mejores algoritmos para estructuras de datos en Python

Veamos ahora los 7 principales algoritmos para estructuras de datos en Python.

1. Búsqueda binaria

La ordenación organiza los registros en un orden definido, lo que permite acceder a ellos rápidamente y de la forma más rápida posible. El algoritmo de búsqueda binaria busca un elemento en un archivo ordenado de elementos. Funciona según el concepto de dividir a la mitad el intervalo de búsqueda una y otra vez. Es decir, si el valor de la clave de búsqueda es menor que el elemento que se encuentra en el medio del intervalo, hay que reducir el intervalo a la mitad inferior. De lo contrario, se reduce a la mitad superior. Además, cualquier forma se puede expresar como la diferencia entre dos formas, cada una de las cuales no es más compleja que la original.

Pasos del algoritmo

Inicializar variables:

• Colocar left a 0 (el índice inicial de la matriz).
• Colocar right a n - 1 (el índice final de la matriz, donde n es la longitud de la matriz).

Hacer un bucle hasta left es mayor que right:

• Calcular el mid índice como valor mínimo de (left + right) / 2.

Comprueba el elemento central:

• Si arr(mid) es igual al valor objetivo:
  • Devolver el índice mid (objetivo encontrado).
• Si arr(mid) es menor que el valor objetivo:
  • Colocar left a mid + 1 (ignorar la mitad izquierda).
• Si arr(mid) es mayor que el valor objetivo:
  • Colocar right a mid - 1 (ignorar la mitad derecha).

Si el bucle finaliza sin encontrar el objetivo:

• Devolver -1 (el objetivo no está presente en la matriz).

Implementación de código

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        # Check if the target is at mid
        if arr(mid) == target:
            return mid
        
        # If the target is greater, ignore the left half
        elif arr(mid) < target:
            left = mid + 1
        
        # If the target is smaller, ignore the right half
        else:
            right = mid - 1
    
    # Target is not present in the array
    return -1

# Example usage:
arr = (2, 3, 4, 10, 40)
target = 10

result = binary_search(arr, target)

if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not present in array")

La búsqueda lineal sirve como base de la búsqueda binaria, ya que hace que la complejidad temporal sea mucho más eficiente al configurarla en una función de log n. Generalmente se emplea en casos donde se debe activar la función de búsqueda en las aplicaciones, por ejemplo, en la indexación de bases de datos.

2. Ordenación por fusión

Merge Sort es un algoritmo de división y regla que recibe una lista desordenada. Crea n sublistas, cada una con un elemento. Se pide que las sublistas se fusionen para desarrollar otras sublistas ordenadas hasta que se obtenga una sola. Es estable y los algoritmos de esta categoría operan dentro de la complejidad temporal de O(n log n). Merge Sort es generalmente adecuado para grandes volúmenes de trabajo y se utiliza cuando se requiere una ordenación estable. Ordena eficazmente listas enlazadas y divide datos extensos que no caben en la memoria en componentes más pequeños.

Pasos del algoritmo

Dividir:

• Si la matriz tiene más de un elemento, divida la matriz en dos mitades:
  • Encuentra el punto medio mid Para dividir la matriz en dos mitades: left = arr(:mid) y right = arr(mid:).

Conquistar:

• Aplicar recursivamente la ordenación por combinación a ambas mitades:
  • Ordenar el left medio.
  • Ordenar el right medio.

Unir:

• Fusionar las dos mitades ordenadas en una única matriz ordenada:
  • Comparar los elementos de left y right uno por uno, y coloque el elemento más pequeño en la matriz original.
  • Continúe hasta que todos los elementos de ambas mitades se fusionen nuevamente en la matriz original.

Caso base:

• Si la matriz tiene solo un elemento, ya está ordenada, por lo que retorna inmediatamente.

Implementación de código

def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle point
        mid = len(arr) // 2
        
        # Divide the array elements into 2 halves
        left_half = arr(:mid)
        right_half = arr(mid:)
        
        # Recursively sort the first half
        merge_sort(left_half)
        
        # Recursively sort the second half
        merge_sort(right_half)
        
        # Initialize pointers for left_half, right_half and merged array
        i = j = k = 0
        
        # Merge the sorted halves
        while i < len(left_half) and j < len(right_half):
            if left_half(i) < right_half(j):
                arr(k) = left_half(i)
                i += 1
            else:
                arr(k) = right_half(j)
                j += 1
            k += 1
        
        # Check for any remaining elements in left_half
        while i < len(left_half):
            arr(k) = left_half(i)
            i += 1
            k += 1
        
        # Check for any remaining elements in right_half
        while j < len(right_half):
            arr(k) = right_half(j)
            j += 1
            k += 1

# Example usage
arr = (12, 11, 13, 5, 6, 7)
merge_sort(arr)
print("Sorted array is:", arr)

3. Ordenación rápida

La ordenación rápida es una técnica de ordenación eficiente que utiliza la técnica de dividir y vencer. Este método ordena seleccionando un pivote de la matriz y dividiendo los demás elementos en dos matrices: una para los elementos menores que el pivote y otra para los elementos mayores que el pivote. Sin embargo, Quick Sort supera a Merge Sort y Heap Sort en el entorno del mundo real y se ejecuta en un caso promedio de O(n log n). Analizando estas características, podemos concluir que es popular en diferentes librerías y frameworks. Se dice que se aplica comúnmente en la informática comercial, donde es necesario manipular y ordenar matrices grandes.

Pasos del algoritmo

Elija un pivote:

• Seleccione un elemento pivote de la matriz. Puede ser el primer elemento, el último elemento, el elemento intermedio o un elemento aleatorio.

Particionado:

• Reorganiza los elementos de la matriz de modo que todos los elementos menores que el pivote estén en el lado izquierdo y todos los elementos mayores que el pivote estén en el lado derecho. El elemento pivote se coloca en su posición correcta en la matriz ordenada.

Aplicar ordenación rápida de forma recursiva:

• Aplique de forma recursiva los pasos anteriores a las submatrices izquierda y derecha.

Caso base:

• Si la matriz tiene solo un elemento o está vacía, ya está ordenada y la recursión finaliza.

Implementación de código

def quick_sort(arr):
    # Base case: if the array is empty or has one element, it's already sorted
    if len(arr) <= 1:
        return arr
    
    # Choosing the pivot (Here, we choose the last element as the pivot)
    pivot = arr(-1)
    
    # Elements less than the pivot
    left = (x for x in arr(:-1) if x <= pivot)
    
    # Elements greater than the pivot
    right = (x for x in arr(:-1) if x > pivot)
    
    # Recursively apply quick_sort to the left and right sub-arrays
    return quick_sort(left) + (pivot) + quick_sort(right)

# Example usage:
arr = (10, 7, 8, 9, 1, 5)
sorted_arr = quick_sort(arr)
print(f"Sorted array: {sorted_arr}")

4. Algoritmo de Dijkstra

El algoritmo de Dijkstra ayuda a obtener las rutas más cortas entre puntos o nodos de la red. Elige continuamente el nodo con la distancia tentativa más pequeña y relaja sus conexiones hasta que elijas el nodo de destino. Las redes informáticas utilizan ampliamente este algoritmo para las estructuras de datos en Python, especialmente en los sistemas de mapeo informático que requieren cálculos de rutas. Los sistemas GPS, los protocolos de enrutamiento en redes informáticas y los algoritmos para el movimiento de personajes u objetos en los videojuegos también lo utilizan.

Pasos del algoritmo

Inicializar:

• Establezca la distancia al nodo de origen como 0 y a todos los demás nodos como infinito (∞).
• Marcar todos los nodos como no visitados.
• Establezca el nodo de origen como el nodo actual.
• Utilice una cola de prioridad (min-heap) para almacenar nodos junto con sus distancias tentativas.

Explorar Vecinos:

• Para el nodo actual, verifique todos sus vecinos no visitados.
• Para cada vecino, calcule la distancia tentativa desde el nodo de origen.
• Si la distancia calculada es menor que la distancia conocida, actualice la distancia.
• Inserte al vecino con la distancia actualizada en la cola de prioridad.

Seleccione el siguiente nodo:

• Marcar el nodo actual como visitado (un nodo visitado no será verificado nuevamente).
• Seleccione el nodo no visitado con la distancia tentativa más pequeña como el nuevo nodo actual.

Repetir:

• Repita los pasos 2 y 3 hasta que se hayan visitado todos los nodos o la cola de prioridad esté vacía.

Producción:

• El algoritmo genera la distancia más corta desde el nodo de origen a cada nodo del gráfico.

Implementación de código

import heapq

def dijkstra(graph, start):
    # Initialize distances and priority queue
    distances = {node: float('infinity') for node in graph}
    distances(start) = 0
    priority_queue = ((0, start))  # (distance, node)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # If the popped node's distance is greater than the known shortest distance, skip it
        if current_distance > distances(current_node):
            continue

        # Explore neighbors
        for neighbor, weight in graph(current_node).items():
            distance = current_distance + weight

            # If found a shorter path to the neighbor, update it
            if distance < distances(neighbor):
                distances(neighbor) = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Example usage:
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node="A"
distances = dijkstra(graph, start_node)

print("Shortest distances from node", start_node)
for node, distance in distances.items():
    print(f"Node {node} has a distance of {distance}")

5. Búsqueda en amplitud (BFS)

BFS es una técnica de recorrido o búsqueda de estructuras de datos de árboles o gráficos. Este algoritmo gráfico utiliza una estrategia de búsqueda de árboles; comienza con cualquier nodo o nodo raíz y se ramifica a todos los nodos de borde y luego a todos los nodos en el siguiente nivel. Este algoritmo para estructuras de datos en Python se utiliza para distancias cortas en gráficos no ponderados. Los recorridos son Se utiliza en orden de nivel para cada nodo. Se encuentra en redes peer-to-peer y motores de búsqueda, y encuentra componentes conectados en un gráfico.

Pasos del algoritmo

Inicializar:

• Crear una cola vacía q.
• Poner en cola el nodo de inicio s en q.
• Marcar el nodo de inicio s según lo visitado.

Repetir hasta que la cola esté vacía:

• Quitar un nodo de la cola v de q.
• Por cada vecino no visitado n de v:
  • Marca n según lo visitado.
  • Poner en cola n en q.

Repita el paso 2 hasta que la cola esté vacía.

Finalizar el proceso una vez que se hayan visitado todos los nodos en todos los niveles.

Implementación de código

from collections import deque

def bfs(graph, start):
    # Create a queue for BFS
    queue = deque((start))
    
    # Set to store visited nodes
    visited = set()
    
    # Mark the start node as visited
    visited.add(start)
    
    # Traverse the graph
    while queue:
        # Dequeue a vertex from the queue
        node = queue.popleft()
        print(node, end=" ")
        
        # Get all adjacent vertices of the dequeued node
        # If an adjacent vertex hasn't been visited, mark it as visited and enqueue it
        for neighbor in graph(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Example usage:
graph = {
    'A': ('B', 'C'),
    'B': ('D', 'E'),
    'C': ('F', 'G'),
    'D': (),
    'E': (),
    'F': (),
    'G': ()
}

bfs(graph, 'A')

6. Búsqueda en profundidad (DFS)

DFS es otro algoritmo para navegar o posiblemente buscar estructuras de datos de árboles o gráficos. Comienza en la raíz (o en cualquier nodo arbitrario) y recorre una rama hasta el final de la misma antes de volver a subir por otra. DFS se aplica en muchas áreas para ordenar, detectar ciclos y resolver acertijos como laberintos. Es popular en muchas aplicaciones de IA, como en juegos para encontrar el camino, resolver acertijos y compiladores para analizar estructuras de árboles.

Pasos del algoritmo

Inicialización:

• Cree una pila (o utilice recursión) para realizar un seguimiento de los nodos que se visitarán.
• Marcar todos los nodos como no visitados (o inicializar un visited colocar).

Comience desde el nodo de origen:

• Empuje el nodo de origen hacia la pila y márquelo como visitado.

Procesar nodos hasta que la pila esté vacía:

• Extraer un nodo de la pila (nodo actual).
• Procesar el nodo actual (por ejemplo, imprimirlo, almacenarlo, etc.).
• Para cada vecino no visitado del nodo actual:
  • Marcar al vecino como visitado.
  • Empuja al vecino hacia la pila.

Repita hasta que la pila esté vacía.

Implementación de código

def dfs_iterative(graph, start):
    visited = set()  # To keep track of visited nodes
    stack = (start)  # Initialize the stack with the start node

    while stack:
        # Pop the last element from the stack
        node = stack.pop()

        if node not in visited:
            print(node)  # Process the node (e.g., print it)
            visited.add(node)  # Mark the node as visited

            # Add unvisited neighbors to the stack
            for neighbor in graph(node):
                if neighbor not in visited:
                    stack.append(neighbor)

# Example usage:
graph = {
    'A': ('B', 'C'),
    'B': ('D', 'E'),
    'C': ('F'),
    'D': (),
    'E': ('F'),
    'F': ()
}

dfs_iterative(graph, 'A')

7. Hash

El hash implica dar un nombre o una identidad específicos a un objeto en particular de un grupo de objetos similares. Una función hash asigna la entrada (conocida como la “clave”) a una cadena fija de bytes para implementar dos. El hash permite un acceso rápido y eficiente a los datos, lo cual es esencial cuando se necesita una recuperación rápida de datos. Las bases de datos suelen utilizar el hash para indexar, almacenar en caché y estructuras de datos como tablas hash para búsquedas rápidas.

Pasos del algoritmo

Aporte: Un elemento de datos (por ejemplo, cadena, número).Elija una función hash: Seleccione una función hash que asigne los datos de entrada a un valor hash (generalmente un entero).Calcular valor hash:

• Aplique la función hash a los datos de entrada para obtener el valor hash.

Insertar o buscar:

• Inserción: Almacene los datos en una tabla hash utilizando el valor hash como índice.
• Buscar: Utilice el valor hash para encontrar rápidamente los datos en la tabla hash.

Manejar colisiones:

• Si dos entradas diferentes producen el mismo valor hash, utilice un método de resolución de colisiones, como encadenamiento (almacenar múltiples elementos en el mismo índice) o direccionamiento abierto (encontrar otra ranura abierta).

Implementación de código

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = (() for _ in range(size))
    
    def hash_function(self, key):
        # A simple hash function
        return hash(key) % self.size
    
    def insert(self, key, value):
        hash_key = self.hash_function(key)
        key_exists = False
        bucket = self.table(hash_key)
        
        for i, kv in enumerate(bucket):
            k, v = kv
            if key == k:
                key_exists = True
                break
        
        if key_exists:
            bucket(i) = (key, value)  # Update the existing key
        else:
            bucket.append((key, value))  # Insert the new key-value pair
    
    def get(self, key):
        hash_key = self.hash_function(key)
        bucket = self.table(hash_key)
        
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found
    
    def delete(self, key):
        hash_key = self.hash_function(key)
        bucket = self.table(hash_key)
        
        for i, kv in enumerate(bucket):
            k, v = kv
            if k == key:
                del bucket(i)
                return True
        return False  # Key not found

# Example usage:
hash_table = HashTable(size=10)

# Insert data into the hash table
hash_table.insert("apple", 10)
hash_table.insert("banana", 20)
hash_table.insert("orange", 30)

# Retrieve data from the hash table
print(hash_table.get("apple"))   # Output: 10
print(hash_table.get("banana"))  # Output: 20

# Delete data from the hash table
hash_table.delete("apple")
print(hash_table.get("apple"))   # Output: None

Lea también: Formas de calcular el hash en la estructura de datos

Conclusión

Dominar los algoritmos junto con las estructuras de datos es esencial para cualquier desarrollador de Python que desee escribir código eficiente y escalable. Estos algoritmos son herramientas fundamentales que optimizan el procesamiento de datos, mejoran el rendimiento y resuelven problemas complejos en diversas aplicaciones. Al comprender e implementar estos algoritmos, los desarrolladores pueden aprovechar todo el potencial de las estructuras de datos de Python, lo que conduce a soluciones de software más efectivas y sólidas.

Lea también: Guía completa sobre técnicas de ordenamiento en Python (edición 2024)