Tema: algorithms
-
Orden de dependencias mediante recorrido de grafos: BFS, DFS y ordenamiento topológico
Modelar las dependencias como un grafo dirigido, usar un recorrido en anchura o en profundidad para encontrar todo lo afectado por un cambio, y el algoritmo de Kahn o el posorden de DFS para producir un orden de compilación o migración que reporte los ciclos en lugar de ocultarlos; graphlib y tsort implementan el ordenamiento.
-
Tablas hash en la práctica: colisiones, factor de carga y hashing con semilla
Una tabla hash es rápida en promedio solo mientras las claves se distribuyen de forma uniforme entre los cubos (buckets); las colisiones, el factor de carga que dispara el rehashing, y la siembra de hash por proceso frente a la inundación de hash (hash flooding) determinan su comportamiento real. Nunca hay que persistir valores hash ni depender del orden de iteración.
-
Programación dinámica paso a paso: derivación de la distancia de edición
La programación dinámica convierte una definición recursiva con subproblemas superpuestos en un algoritmo polinómico: definir el estado, escribir la recurrencia y los casos base, memoizar o llenar una tabla, y luego reducir la memoria. La distancia de edición entre dos cadenas se deriva por completo como ejemplo resuelto.
-
Recursión frente a iteración: profundidad de pila, límites y cuándo conviene convertir
La recursión refleja de forma natural los problemas con forma de árbol, pero gasta un marco de pila por nivel; la pila está acotada por el límite de recursión del intérprete o por el tamaño de pila del hilo, de modo que la recursión sobre una profundidad controlada por la entrada es un fallo esperando a ocurrir. Conviene convertirla a una pila explícita o a un bucle cuando la profundidad crece con el tamaño de la entrada.
-
Muestreo por embalse: una muestra uniforme de un flujo de longitud desconocida
Mantener k elementos de un flujo sin conocer su longitud: llenar el embalse con los primeros k, y luego reemplazar una posición aleatoria con probabilidad k/i para el elemento i. Un solo paso, memoria O(k), cada elemento termina en la muestra con probabilidad exactamente k/n, demostrado mediante un breve argumento telescópico.
-
Tries para búsquedas por prefijo: autocompletado y coincidencia del prefijo más largo
Un trie almacena cadenas con un nodo por cada prefijo común, de modo que la búsqueda cuesta la longitud de la clave sin importar cuántas claves existan; todas las claves con un prefijo forman un único subárbol, y el prefijo almacenado más largo de una consulta se encuentra en un solo recorrido; se usa para autocompletado y enrutamiento, y conviene compararlo primero con un arreglo ordenado.
-
Trampas de la búsqueda binaria: desbordamiento del punto medio y límites con error de uno
La búsqueda binaria es corta y famosa por lo fácil que es hacerla mal: el punto medio (low + high) / 2 desborda los enteros de ancho fijo, los límites inclusivos y exclusivos se mezclan, y los duplicados plantean la duda de qué índice devolver. Conviene usar una biblioteca o la forma con predicado monótono e intervalos semiabiertos, y probar los casos límite.
-
Razonar sobre la complejidad antes de optimizar
La complejidad asintótica predice cómo crece el tiempo de ejecución con el tamaño de la entrada; reconocer en la revisión de código los bucles cuadráticos, las búsquedas lineales repetidas y la recursión sin límite evita la mayoría de los incidentes de rendimiento antes de necesitar un perfilado.
-
Token bucket, leaky bucket y ventana deslizante: en qué se diferencian los algoritmos de limitación de tasa
La ventana fija es barata, pero deja pasar el doble del límite en el cambio de ventana; el registro deslizante es exacto, pero guarda cada marca de tiempo; el contador de ventana deslizante aproxima con memoria constante; el token bucket admite ráfagas hasta el tamaño del bucket con una recarga a ritmo fijo; el leaky bucket suaviza la salida retrasando peticiones. nginx y Envoy documentan los dos últimos.
-
Filtros de Bloom: pertenencia probabilística a un conjunto sin falsos negativos
Un filtro de Bloom responde «definitivamente no está en el conjunto» o «probablemente está», con un pequeño array de bits y k funciones hash; los falsos positivos se pueden ajustar, los falsos negativos son imposibles y no admite borrado. Sirve para evitar consultas de claves ausentes, y todo positivo debe verificarse contra la fuente de verdad.
-
Heurísticas de A*: conservar el significado del coste de movimiento
Elige una heurística que sea cota inferior para el grafo de movimiento real, trata correctamente las rutas mejoradas y verifica la calidad del camino frente a una búsqueda no informada.
-
Usar un token bucket para las llamadas a herramientas
Cómo implementar ráfagas acotadas con una ecuación explícita de recarga de tokens, consumo atómico y un límite aparte para las solicitudes en curso.
-
Estabilidad de la ordenación: qué garantiza y cuándo importa
Una ordenación estable conserva el orden de entrada de los elementos que se comparan como iguales. Python la garantiza, ECMAScript la exige desde 2019, Go y GNU sort la ofrecen como opción; de ella depende que las ordenaciones por varias claves, las tablas ordenables y las consultas paginadas se comporten de forma predecible.
Legible por máquina: JSON