Publicado · en mejora
Algorithm
Aprende cómo funcionan los arrays, las listas enlazadas, las pilas, las colas y las tablas hash, cuánto cuesta cada operación y cómo elegir la adecuada.
Una estructura de datos es una forma de organizar los datos en memoria junto con las operaciones que resultan baratas sobre esa organización. Este tema cubre las cinco estructuras en las que se apoya casi cualquier programa: arrays y arrays dinámicos, listas enlazadas, pilas, colas y deques, y tablas hash. También explica la memoria contigua frente a la enlazada, las funciones hash, las colisiones y el factor de carga.
La estructura que eliges decide si una operación cuesta O(1) u O(n). Implementar una cola quitando elementos del principio de una lista, o comprobar pertenencia en una lista, hace que el programa se vuelva mucho más lento cuando crecen los datos. Saber qué son en realidad list, deque, dict y set de Python, vector, deque y unordered_map de C++, ArrayList, ArrayDeque y HashMap de Java, y Array, Map y Set de TypeScript ayuda a evitar esas trampas, y es lo primero que se evalúa en las entrevistas técnicas.
Empieza siguiendo a mano cada estructura con un ejemplo pequeño para ver qué se mueve en memoria. Después implementa una pila, una cola con búfer circular y un mapa hash con encadenamiento separado, resume los costes en una tabla y mídelos con un temporizador. Por último, resuelve ejercicios cuya habilidad principal es elegir la estructura correcta.
Los arrays dan acceso O(1) por índice y buen uso de la caché; las listas enlazadas permiten insertar y borrar en O(1) junto a un nodo que ya tienes.
Un array dinámico crece por un factor constante y copia sus elementos, así que las inserciones caras ocasionales siguen promediando O(1).
Una pila saca el elemento más reciente y una cola el más antiguo. Los deques y los búferes circulares hacen O(1) las operaciones en ambos extremos.
Una tabla hash asigna claves a cubetas para buscar en O(1) de media, resuelve colisiones con técnicas como el encadenamiento y crece cuando el factor de carga supera un límite.
Un mapa hash con encadenamiento separado: el hash de la clave módulo el número de cubetas elige la cubeta, si la clave ya existe solo se reemplaza el valor y, cuando el factor de carga supera 0,75, las cubetas se duplican y se reinsertan todos los pares. El script también muestra una lista usada como pila y un deque usado como cola.
data_structures.py
from collections import deque
class HashMap:
"""Separate chaining: each bucket is a list of (key, value) pairs."""
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size > 0.75 * len(self.buckets): # load factor limit
old = self.buckets
self.buckets = [[] for _ in range(2 * len(old))]
for pairs in old:
for k, v in pairs:
self._bucket(k).append((k, v))
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
stack = [1, 2, 3]
stack.append(4)
print("stack pop:", stack.pop()) # 4 (LIFO)
queue = deque([1, 2, 3])
queue.append(4)
print("queue popleft:", queue.popleft()) # 1 (FIFO)
ages = HashMap()
for name, age in [("ada", 36), ("alan", 41), ("grace", 85)]:
ages.put(name, age)
ages.put("ada", 37)
print("ada:", ages.get("ada"), "size:", ages.size) # ada: 37 size: 3
python data_structures.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Estructuras de datos básicas.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Estructuras de datos básicas.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.