Ventana deslizante
En resumen: Una ventana deslizante calcula algo para cada rango consecutivo sumando el elemento nuevo y quitando el viejo en cada paso: O(n) en lugar de O(n · k).
Problema
Los ingresos de los últimos 365 días
El panel de la tienda muestra, para cada día, los ingresos de los últimos 365 días. El historial es de 10 años: 3650 días. El código calcula cada ventana desde cero: para cada día suma los 365 días anteriores.
let adds = 0;
function recompute(sales, k) { const sums = []; for (let start = 0; start + k <= sales.length; start++) { let sum = 0; for (let d = start; d < start + k; d++) { adds++; sum += sales[d]; } sums.push(sum); } return sums;}const sales = Array.from({ length: 3650 }, (_, d) => (d * 37) % 101 * 10 + 500);const sums = recompute(sales, 365);console.log(`Ventanas: ${sums.length}`);console.log(`Sumas: ${adds}`);console.log(`Los mejores 365 días: ${Math.max(...sums)} €`);Ventanas: 3286Sumas: 1199390Los mejores 365 días: 366050 €3286 ventanas de 365 sumas cada una: 1 199 390. Eso es n·k: con 1000 productos, un gráfico para cada uno, son 1200 millones de sumas cada noche.
Y, sin embargo, dos ventanas vecinas difieren en solo dos días. Los otros 364 se suman una y otra vez.
La idea
Deslizar la ventana: +día nuevo, −día viejo
La suma de los días 2–8 es la suma de los días 1–7, más el día 8, menos el día 1. El día 8 entra en la ventana, el día 1 sale. Los días intermedios no se tocan.
Así que:
- la primera ventana se suma una vez: k sumas;
- cada una siguiente es la anterior + el día nuevo − el día más viejo: dos operaciones, por grande que sea la ventana.
Esto se llama ventana deslizante: una ventana de longitud fija que se mueve de elemento en elemento, mientras su resultado se actualiza a partir del anterior. En lugar de (n − k + 1) · k operaciones hay k + 2(n − k). Eso es O(n), no O(n·k).
La ventana son dos punteros que se mueven en la misma dirección, como en la lección anterior: su inicio y su final. Aquí la distancia entre ellos siempre es k.
Míralo
La semana se desliza
Las ventas de 12 días y la suma de cada 7 días consecutivos. El promedio de la semana es la suma dividida entre 7.
function slide(sales, k) { let sum = 0; for (let i = 0; i < k; i++) { sum += sales[i]; } const sums = [sum]; for (let i = k; i < sales.length; i++) { sum += sales[i]; sum -= sales[i - k]; sums.push(sum); } return sums;}const sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];const sums = slide(sales, 7);sums.forEach((sum, d) => { console.log(`Días ${d + 1}–${d + 7}: ${sum} €`);});Días 1–7: 5430 €Días 2–8: 5500 €Días 3–9: 5470 €Días 4–10: 5540 €Días 5–11: 5560 €Días 6–12: 5830 €function slide(sales, k) { let sum = 0; for (let i = 0; i < k; i++) { sum += sales[i]; } const sums = [sum]; for (let i = k; i < sales.length; i++) { sum += sales[i]; sum -= sales[i - k]; sums.push(sum); } return sums;}Paso a paso, en palabras
- La primera ventana: días 1–7. Sus 7 días se suman uno por uno: 7 sumas, 5430 €.
- Entra el día 8: +890 €. Sale el día 1: −820 €. Días 2–8: 5500 €, con dos operaciones en lugar de 7.
- Entra el día 9: +610 €. Sale el día 2: −640 €. Días 3–9: 5470 €, con dos operaciones en lugar de 7.
- Entra el día 10: +980 €. Sale el día 3: −910 €. Días 4–10: 5540 €, con dos operaciones en lugar de 7.
- Entra el día 11: +720 €. Sale el día 4: −700 €. Días 5–11: 5560 €, con dos operaciones en lugar de 7.
- Entra el día 12: +850 €. Sale el día 5: −580 €. Días 6–12: 5830 €, con dos operaciones en lugar de 7.
- 6 ventanas con 17 operaciones: 7 para la primera y 2 para cada siguiente. Desde cero cada vez serían 6 · 7 = 42.
push, y forEach da tanto la suma como su número.Pruébalo
Predice
Las ventas de cinco días y una ventana de 3 días. ¿Qué imprime el programa?
function slide(sales, k) { let sum = 0; for (let i = 0; i < k; i++) { sum += sales[i]; } const sums = [sum]; for (let i = k; i < sales.length; i++) { sum += sales[i]; sum -= sales[i - k]; sums.push(sum); } return sums;}
const sales = [820, 640, 910, 700, 580];const sums = slide(sales, 3);console.log(sums.at(-1));La primera ventana es 820 + 640 + 910 = 2370. Luego +700 −820 = 2250, luego +580 −640 = 2190. La última suma es de los días 3–5: 910 + 700 + 580 = 2190.
Pruébalo
Completa
El día i entra en la ventana. ¿Qué día sale?
function slide(sales, k) {
let sum = 0;
for (let i = 0; i < k; i++) {
sum += sales[i];
}
const sums = [sum];
for (let i = k; i < sales.length; i++) {
sum += sales[i];
sum -= sales[];
sums.push(sum);
}
return sums;
}La ventana que termina el día i va de i - k + 1 a i. La anterior va de i - k a i - 1. La diferencia es el día i - k: ese sale.
Pruébalo
Encuentra el error
La primera suma es correcta, y después los números suben y bajan a saltos:
const sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];const sums = slide(sales, 7);sums.forEach((sum, d) => { console.log(`Días ${d + 1}–${d + 7}: ${sum} €`);});Días 1–7: 5430 €Días 2–8: 5560 €Días 3–9: 5280 €Días 4–10: 5650 €Días 5–11: 5390 €Días 6–12: 5520 €Elige la línea con el error.
El código resta ayer, sales[i - 1], y no el día que sale de la ventana, sales[i - k]. Ayer sigue dentro de la ventana. Así que todas las sumas son incorrectas salvo la primera: para los días 2–8 da 5430 + 890 − 760 = 5560, cuando la respuesta correcta es 5500.
Míralo
Mídelo: desde cero frente a deslizar
Los mismos 10 años y una ventana de 365 días, y la función cuenta las sumas y las restas:
let ops = 0;
function slide(sales, k) { let sum = 0; for (let i = 0; i < k; i++) { ops++; sum += sales[i]; } const sums = [sum]; for (let i = k; i < sales.length; i++) { ops++; sum += sales[i]; ops++; sum -= sales[i - k]; sums.push(sum); } return sums;}const sales = Array.from({ length: 3650 }, (_, d) => (d * 37) % 101 * 10 + 500);const sums = slide(sales, 365);console.log(`Ventanas: ${sums.length}`);console.log(`Operaciones: ${ops}`);console.log(`Los mejores 365 días: ${Math.max(...sums)} €`);Ventanas: 3286Operaciones: 6935Los mejores 365 días: 366050 €6935 operaciones en lugar de 1 199 390, y los mejores 365 días son los mismos. Ejecuta los dos caminos en el navegador:
- Cada ventana desde cero (K = 365)
O(n) - Deslizante: +nuevo −viejo
O(n)
| Algoritmo | n = 1000 | n = 3650 | n = 10.000 | n = 100.000 |
|---|---|---|---|---|
| Cada ventana desde cero (K = 365) | 232.140 | 1.199.390 | 3.517.140 | 36.367.140 |
| Deslizante: +nuevo −viejo | 1635 | 6935 | 19.635 | 199.635 |
function slide(sales, k) { let sum = 0; for (let i = 0; i < k; i++) { sum += sales[i]; } const sums = [sum]; for (let i = k; i < sales.length; i++) { sum += sales[i]; sum -= sales[i - k]; sums.push(sum); } return sums;}Las dos curvas son paralelas: la ventana siempre es de 365 días, así que las dos crecen con n. La diferencia es el factor. Desde cero cuesta k por día, deslizar cuesta 2 por día, por grande que sea la ventana. Con una ventana de 30 días deslizar es 15 veces más rápido, con 365 días unas 180 veces.
La idea
Una ventana de longitud variable
Marketing pregunta: ¿cuál es el periodo más largo de días consecutivos en el que el gasto en publicidad suma como máximo 400 €? Ahora la longitud de la ventana no está dada. Es la respuesta.
La ventana tiene dos bordes, left y right:
rightavanza y añade un día nuevo;- si la suma se pasa del presupuesto,
leftavanza y quita días por la izquierda hasta que la suma vuelve a estar dentro del presupuesto; - después la ventana es válida, y su longitud es una candidata a la más larga.
function longestWithin(spend, budget) { let best = 0; let sum = 0; let left = 0; for (let right = 0; right < spend.length; right++) { sum += spend[right]; while (sum > budget) { sum -= spend[left]; left++; } best = Math.max(best, right - left + 1); } return best;}const spend = [120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60];console.log(`Periodo más largo hasta 400 €: ${longestWithin(spend, 400)} días`);Periodo más largo hasta 400 €: 5 díasHay un bucle dentro de un bucle, pero esto es O(n), no O(n²). left nunca retrocede: cada día entra en la ventana una vez y sale como máximo una vez. En total, como máximo 2n movimientos.
Esto funciona porque el gasto no es negativo: una ventana más larga nunca es más barata. Si hay reembolsos (números negativos), quitar un día por la izquierda puede aumentar la suma, y la regla «reducir hasta que esté dentro del presupuesto» ya no es correcta.
Míralo
Sin carácter repetido: una ventana con un conjunto
Otra ventana de longitud variable: el trozo más largo de una línea de registro en el que no se repite ningún carácter. Esos trozos delatan tokens aleatorios que no deberían estar en el registro. La ventana guarda sus caracteres en un conjunto. Cuando el carácter nuevo ya está dentro, left quita caracteres por la izquierda hasta que desaparece la repetición:
function longestUnique(line) { const seen = new Set(); let bestStart = 0; let bestLen = 0; let left = 0; for (let right = 0; right < line.length; right++) { const c = line[right]; while (seen.has(c)) { seen.delete(line[left]); left++; } seen.add(c); if (right - left + 1 > bestLen) { bestLen = right - left + 1; bestStart = left; } } return line.slice(bestStart, bestStart + bestLen);}const line = "GET /cart?token=x9Kq2Lm7Pz&page=2";const part = longestUnique(line);console.log(`Sin carácter repetido: ${part} (${part.length})`);Sin carácter repetido: ?token=x9Kq2Lm7Pz&pag (21)La comprobación «¿está?» en el conjunto es O(1) en promedio, con una tabla hash. Así que aquí también el total es O(n).
line[right] es una unidad del texto UTF-16. Para texto con emoji es medio carácter: mira «Más precisamente, para curiosos».Más precisamente, para curiosos
Qué es un «carácter». En Java, C# y JavaScript una cadena está hecha de unidades de 16 bits (UTF-16). Un emoji como 🛒 son dos de esas unidades, y la ventana las contará por separado. En Python una cadena está hecha de puntos de código, y 🛒 es un carácter. Un registro con letras latinas y dígitos es igual en los cuatro lenguajes.
La suma no debe desbordarse. En JavaScript los números son exactos hasta 2⁵³, la suma en céntimos no se desborda. En Java y C# int llega hasta 2 147 483 647, y los ingresos en céntimos necesitan un long.
La suma no debe derivar. Si las ventas están en euros con céntimos en un double, cada +nuevo −viejo añade un diminuto error de redondeo, y los errores se acumulan: después de miles de pasos la suma de la ventana ya no es exactamente la suma de sus días. Guarda el dinero en céntimos, como enteros. Si los números son de coma flotante por naturaleza (temperaturas, tiempos), calcula la ventana desde cero cada pocos miles de pasos.
El promedio y el mayor. El promedio móvil es la suma dividida entre k. El mayor valor de la ventana no funciona con +nuevo −viejo: un máximo no se puede «restar». Para eso hay una ventana deslizante con una cola de doble extremo (deque) que guarda los candidatos al máximo.
Ejercicio
El periodo más corto con ingresos de al menos 3500 €
Resuelve la tarea en tu editor.
El periodo más corto. Las ventas de 12 días son 820 €, 640 €, 910 €, 700 €, 580 €, 1020 €, 760 €, 890 €, 610 €, 980 €, 720 € y 850 €. ¿Cuál es el periodo más corto de días consecutivos con unos ingresos de al menos 3500 €? La ventana crece hacia la derecha, y mientras la suma sea al menos 3500 €, recuerda su longitud si es menor y redúcela por la izquierda.
Periodo más corto con al menos 3500 €: 5 días (del día 1 al día 5)Más tareas
- La mejor semana. Con deslizar, encuentra qué 7 días consecutivos tienen los mayores ingresos e imprímelos.
- Un promedio móvil. Imprime las ventas promedio de cada 7 días, redondeadas al céntimo.
- Clientes distintos por hora. Los pedidos están ordenados por minuto, cada uno con un número de cliente. En cada ventana de 60 minutos, ¿cuántos clientes distintos hay? Guarda en un mapa cuántos pedidos tiene cada cliente en la ventana.
Test