Ir al contenido
wannacode

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.

static long adds = 0;


static int[] recompute(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    for (int start = 0; start + k <= sales.length; start++) {
        int sum = 0;
        for (int d = start; d < start + k; d++) {
            adds++;
            sum += sales[d];
        }
        sums[start] = sum;
    }
    return sums;
}
int[] sales = new int[3650];
for (int d = 0; d < sales.length; d++) {
    sales[d] = (d * 37) % 101 * 10 + 500;
}
int[] sums = recompute(sales, 365);
int best = Arrays.stream(sums).max().getAsInt();
System.out.println("Ventanas: " + sums.length);
System.out.println("Sumas: " + adds);
System.out.println("Los mejores 365 días: " + best + " €");
Salida
Ventanas: 3286
Sumas: 1199390
Los 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.

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}
int[] sales = {820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850};
int[] sums = slide(sales, 7);
for (int d = 0; d < sums.length; d++) {
    System.out.println("Días " + (d + 1) + "–" + (d + 7) + ": " + sums[d] + " €");
}
Salida
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 €

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}
Paso a paso, en palabras
  1. La primera ventana: días 1–7. Sus 7 días se suman uno por uno: 7 sumas, 5430 €.
  2. Entra el día 8: +890 €. Sale el día 1: −820 €. Días 2–8: 5500 €, con dos operaciones en lugar de 7.
  3. Entra el día 9: +610 €. Sale el día 2: −640 €. Días 3–9: 5470 €, con dos operaciones en lugar de 7.
  4. Entra el día 10: +980 €. Sale el día 3: −910 €. Días 4–10: 5540 €, con dos operaciones en lugar de 7.
  5. Entra el día 11: +720 €. Sale el día 4: −700 €. Días 5–11: 5560 €, con dos operaciones en lugar de 7.
  6. Entra el día 12: +850 €. Sale el día 5: −580 €. Días 6–12: 5830 €, con dos operaciones en lugar de 7.
  7. 6 ventanas con 17 operaciones: 7 para la primera y 2 para cada siguiente. Desde cero cada vez serían 6 · 7 = 42.
El arreglo de sumas tiene longitud sales.length - k + 1: es el número de ventanas que hay. La ventana que termina el día i está en la posición i - k + 1.

Pruébalo

Predice

Las ventas de cinco días y una ventana de 3 días. ¿Qué imprime el programa?

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}


int[] sales = {820, 640, 910, 700, 580};
int[] sums = slide(sales, 3);
System.out.println(sums[sums.length - 1]);
Respuesta

Pruébalo

Completa

El día i entra en la ventana. ¿Qué día sale?

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[];
        sums[i - k + 1] = sum;
    }
    return sums;
}

Pruébalo

Encuentra el error

La primera suma es correcta, y después los números suben y bajan a saltos:

int[] sales = {820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850};
int[] sums = slide(sales, 7);
for (int d = 0; d < sums.length; d++) {
    System.out.println("Días " + (d + 1) + "–" + (d + 7) + ": " + sums[d] + " €");
}
Salida
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.

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:

static long ops = 0;


static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        ops++;
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        ops++;
        sum += sales[i];
        ops++;
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}
int[] sales = new int[3650];
for (int d = 0; d < sales.length; d++) {
    sales[d] = (d * 37) % 101 * 10 + 500;
}
int[] sums = slide(sales, 365);
int best = Arrays.stream(sums).max().getAsInt();
System.out.println("Ventanas: " + sums.length);
System.out.println("Operaciones: " + ops);
System.out.println("Los mejores 365 días: " + best + " €");
Salida
Ventanas: 3286
Operaciones: 6935
Los 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)
Algoritmon = 1000n = 3650n = 10.000n = 100.000
Cada ventana desde cero (K = 365)232.1401.199.3903.517.14036.367.140
Deslizante: +nuevo −viejo1635693519.635199.635
El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.
static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = 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:

  • right avanza y añade un día nuevo;
  • si la suma se pasa del presupuesto, left avanza 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.
static int longestWithin(int[] spend, int budget) {
    int best = 0;
    int sum = 0;
    int left = 0;
    for (int 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;
}
int[] spend = {120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60};
System.out.println("Periodo más largo hasta 400 €: " + longestWithin(spend, 400) + " días");
Salida
Periodo más largo hasta 400 €: 5 días

Hay 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:

static String longestUnique(String line) {
    Set<Character> seen = new HashSet<>();
    int bestStart = 0;
    int bestLen = 0;
    int left = 0;
    for (int right = 0; right < line.length(); right++) {
        char c = line.charAt(right);
        while (seen.contains(c)) {
            seen.remove(line.charAt(left));
            left++;
        }
        seen.add(c);
        if (right - left + 1 > bestLen) {
            bestLen = right - left + 1;
            bestStart = left;
        }
    }
    return line.substring(bestStart, bestStart + bestLen);
}
String line = "GET /cart?token=x9Kq2Lm7Pz&page=2";
String part = longestUnique(line);
System.out.println("Sin carácter repetido: " + part + " (" + part.length() + ")");
Salida
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).

Set<Character> guarda objetos Character empaquetados, no char: seen.contains(c) empaqueta c automáticamente.
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. int en Java llega hasta 2 147 483 647. Un año de ingresos en céntimos de una gran cadena lo supera: entonces la suma es un long. Los contadores de los programas de arriba son long por la misma razón.

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.

Salida
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

Ponte a prueba

1. La suma de los días 1–7 es 5430 €. El día 8 es 890 €, el día 1 es 820 €. ¿Cuál es la suma de los días 2–8?
2. n = 3650 días, ventana k = 365. ¿Cuántas operaciones hace deslizar?
3. En la ventana del presupuesto, el borde izquierdo left nunca retrocede. ¿Cuántas veces se mueve en total como máximo?
4. El gasto también tiene reembolsos: números negativos. ¿Sigue funcionando la ventana «periodo más largo dentro del presupuesto»?
5. Las sumas de la ventana están en euros con céntimos, en un double. ¿Por qué es mejor guardar los céntimos en un entero?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·