Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

Seis patrones

La mayoría de las estructuras equivocadas en código generado (y humano) caen en estos patrones:

Patrón Qué cuesta Qué correspondía
contiene sobre un array dentro de un bucle O(n²) un conjunto hash: O(n) esperado
borrar(0) repetido sobre un array O(n²) para vaciarlo una cola (buffer circular)
ordenar en cada iteración para sacar el mínimo O(n² log n) un heap
tabla hash para consultas por rango O(n) por rango un árbol ordenado o un array ordenado
lista enlazada para recorrer o acceder por posición lenta por la caché, O(i) por posición un array
concatenar texto en un bucle, en lenguajes donde el texto no se modifica y cada suma copia todo O(n²) acumular en un array dinámico y unir al final

Así se ve el bucle escondido del primer patrón:

Comparaciones de contiene frente a un conjunto hashSeis vueltas de un bucle con valores distintos. A la izquierda, contiene sobre un array: la vuelta k recorre los k − 1 valores guardados, con 0, 1, 2, 3, 4 y 5 comparaciones, 15 en total, un triángulo de casillas. A la derecha, con un conjunto hash, una sola comprobación por vuelta: 6 en total.contiene sobre un array:15 comparacionesconjunto hash:6 comprobacionesvuelta 10vuelta 2vuelta 3vuelta 4vuelta 5vuelta 6
Cada casilla es una comparación. Seis vueltas con valores todos distintos: a la vuelta k, contiene recorre los k − 1 valores ya guardados y no encuentra nada. Con 6 vueltas son 15; con n vueltas, cerca de n²/2.

Leer código con esta tabla es buscar el bucle que esconde otro bucle: una operación que parece de una línea pero recorre o copia todo.

Un agente vacía un array de 100 000 trabajos con un bucle que, en cada vuelta, quita el primer elemento (la posición 0) y lo procesa. ¿Qué patrón es y cuánto cuesta en total?