Gleitendes Fenster
Kurz gesagt: Ein gleitendes Fenster berechnet etwas für jeden zusammenhängenden Bereich, indem es bei jedem Schritt das neue Element addiert und das alte entfernt: O(n) statt O(n · k).
Problem
Der Umsatz der letzten 365 Tage
Das Dashboard des Shops zeigt für jeden Tag den Umsatz der letzten 365 Tage. Die Historie umfasst 10 Jahre: 3650 Tage. Der Code berechnet jedes Fenster von Grund auf: Für jeden Tag addiert er die 365 Tage davor.
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("Fenster: " + sums.length);System.out.println("Additionen: " + adds);System.out.println("Die besten 365 Tage: " + best + " €");Fenster: 3286Additionen: 1199390Die besten 365 Tage: 366050 €3286 Fenster mit je 365 Additionen: 1.199.390. Das ist n·k: Bei 1000 Produkten mit je einem Diagramm werden daraus jede Nacht 1,2 Milliarden Additionen.
Dabei unterscheiden sich zwei benachbarte Fenster nur in zwei Tagen. Die anderen 364 werden immer wieder addiert.
Die Idee
Das Fenster gleiten lassen: +neuer Tag, −alter Tag
Die Summe für die Tage 2–8 ist die Summe für die Tage 1–7, plus Tag 8, minus Tag 1. Tag 8 kommt ins Fenster, Tag 1 geht hinaus. Die Tage dazwischen werden nicht angefasst.
Also:
- das erste Fenster wird einmal addiert: k Additionen;
- jedes weitere ist das vorige + der neue Tag − der älteste Tag: zwei Operationen, egal wie groß das Fenster ist.
Das heißt gleitendes Fenster: ein Fenster fester Länge, das sich um ein Element bewegt, während sein Ergebnis aus dem vorigen aktualisiert wird. Statt (n − k + 1) · k Operationen sind es k + 2(n − k). Das ist O(n), nicht O(n·k).
Das Fenster sind zwei Zeiger, die sich in dieselbe Richtung bewegen, wie in der vorigen Lektion: sein Anfang und sein Ende. Hier ist der Abstand zwischen ihnen immer k.
Sieh es dir an
Die Woche gleitet
Der Umsatz für 12 Tage und die Summe für je 7 aufeinanderfolgende Tage. Der Durchschnitt der Woche ist die Summe geteilt durch 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("Tage " + (d + 1) + "–" + (d + 7) + ": " + sums[d] + " €");}Tage 1–7: 5430 €Tage 2–8: 5500 €Tage 3–9: 5470 €Tage 4–10: 5540 €Tage 5–11: 5560 €Tage 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;}Schritt für Schritt, in Worten
- Das erste Fenster: Tage 1–7. Seine 7 Tage werden einzeln addiert: 7 Additionen, 5430 €.
- Tag 8 kommt hinein: +890 €. Tag 1 geht hinaus: −820 €. Tage 2–8: 5500 €, mit zwei Operationen statt 7.
- Tag 9 kommt hinein: +610 €. Tag 2 geht hinaus: −640 €. Tage 3–9: 5470 €, mit zwei Operationen statt 7.
- Tag 10 kommt hinein: +980 €. Tag 3 geht hinaus: −910 €. Tage 4–10: 5540 €, mit zwei Operationen statt 7.
- Tag 11 kommt hinein: +720 €. Tag 4 geht hinaus: −700 €. Tage 5–11: 5560 €, mit zwei Operationen statt 7.
- Tag 12 kommt hinein: +850 €. Tag 5 geht hinaus: −580 €. Tage 6–12: 5830 €, mit zwei Operationen statt 7.
- 6 Fenster für 17 Operationen: 7 für das erste und je 2 für jedes weitere. Jedes Mal von Grund auf wären es 6 · 7 = 42.
sales.length - k + 1: So viele Fenster gibt es. Das Fenster, das an Tag i endet, steht an Position i - k + 1.Probier es aus
Sag voraus
Der Umsatz für fünf Tage und ein Fenster von 3 Tagen. Was gibt das Programm aus?
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]);Das erste Fenster ist 820 + 640 + 910 = 2370. Dann +700 −820 = 2250, dann +580 −640 = 2190. Die letzte Summe gilt für die Tage 3–5: 910 + 700 + 580 = 2190.
Probier es aus
Ergänze
Tag i kommt ins Fenster. Welcher Tag geht hinaus?
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;
}Das Fenster, das an Tag i endet, reicht von i - k + 1 bis i. Das vorige reicht von i - k bis i - 1. Der Unterschied ist Tag i - k: Er geht hinaus.
Probier es aus
Finde den Fehler
Die erste Summe stimmt, und danach springen die Zahlen auf und ab:
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("Tage " + (d + 1) + "–" + (d + 7) + ": " + sums[d] + " €");}Tage 1–7: 5430 €Tage 2–8: 5560 €Tage 3–9: 5280 €Tage 4–10: 5650 €Tage 5–11: 5390 €Tage 6–12: 5520 €Wähle die Zeile mit dem Fehler.
Der Code zieht gestern ab, sales[i - 1], und nicht den Tag, der das Fenster verlässt, sales[i - k]. Gestern ist noch im Fenster. Also ist jede Summe falsch außer der ersten: Für die Tage 2–8 ergibt er 5430 + 890 − 760 = 5560, während die richtige Antwort 5500 ist.
Sieh es dir an
Miss es: von Grund auf gegen Gleiten
Dieselben 10 Jahre und ein Fenster von 365 Tagen, und die Funktion zählt die Additionen und Subtraktionen:
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("Fenster: " + sums.length);System.out.println("Operationen: " + ops);System.out.println("Die besten 365 Tage: " + best + " €");Fenster: 3286Operationen: 6935Die besten 365 Tage: 366050 €6935 Operationen statt 1.199.390, und die besten 365 Tage sind dieselben. Lass beide Wege im Browser laufen:
- Jedes Fenster von vorn (K = 365)
O(n) - Gleitend: +neu −alt
O(n)
| Algorithmus | n = 1.000 | n = 3.650 | n = 10.000 | n = 100.000 |
|---|---|---|---|---|
| Jedes Fenster von vorn (K = 365) | 232.140 | 1.199.390 | 3.517.140 | 36.367.140 |
| Gleitend: +neu −alt | 1.635 | 6.935 | 19.635 | 199.635 |
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;}Die zwei Kurven verlaufen parallel: Das Fenster ist immer 365 Tage, also wachsen beide mit n. Der Unterschied ist der Faktor. Von Grund auf kostet k pro Tag, Gleiten kostet 2 pro Tag, egal wie groß das Fenster ist. Bei einem Fenster von 30 Tagen ist das Gleiten 15-mal schneller, bei 365 Tagen etwa 180-mal.
Die Idee
Ein Fenster mit veränderlicher Länge
Das Marketing fragt: Was ist der längste Zeitraum aufeinanderfolgender Tage, in dem die Werbeausgaben insgesamt höchstens 400 € betragen? Jetzt ist die Länge des Fensters nicht vorgegeben. Sie ist die Antwort.
Das Fenster hat zwei Kanten, left und right:
rightgeht vorwärts und fügt einen neuen Tag hinzu;- geht die Summe über das Budget, geht
leftvorwärts und entfernt links Tage, bis die Summe wieder im Budget ist; - danach ist das Fenster erlaubt, und seine Länge ist ein Kandidat für die längste.
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("Längster Zeitraum bis 400 €: " + longestWithin(spend, 400) + " Tage");Längster Zeitraum bis 400 €: 5 TageEs gibt eine Schleife in einer Schleife, aber das ist O(n), nicht O(n²). left geht nie zurück: Jeder Tag kommt einmal ins Fenster und verlässt es höchstens einmal. Insgesamt höchstens 2n Bewegungen.
Das funktioniert, weil die Ausgaben nicht negativ sind: Ein längeres Fenster ist nie günstiger. Gibt es Erstattungen (negative Zahlen), kann das Entfernen eines Tages links die Summe erhöhen, und die Regel „verkleinern, bis es im Budget ist“ stimmt nicht mehr.
Sieh es dir an
Kein wiederholtes Zeichen: ein Fenster mit einem Set
Ein weiteres Fenster mit veränderlicher Länge: das längste Stück einer Logzeile, in dem sich kein Zeichen wiederholt. Solche Stücke verraten zufällige Tokens, die nicht im Log stehen sollten. Das Fenster hält seine Zeichen in einem Set. Ist das neue Zeichen schon drin, entfernt left links Zeichen, bis die Wiederholung weg ist:
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("Kein Zeichen doppelt: " + part + " (" + part.length() + ")");Kein Zeichen doppelt: ?token=x9Kq2Lm7Pz&pag (21)Die Prüfung „ist es da“ im Set ist im Durchschnitt O(1), mit einer Hashtabelle. Auch hier ist die Summe also O(n).
Set<Character> enthält verpackte Character-Objekte, nicht char: seen.contains(c) verpackt c automatisch.Genauer, für Neugierige
Was ein „Zeichen“ ist. In Java, C# und JavaScript besteht ein String aus 16-Bit-Einheiten (UTF-16). Ein Emoji wie 🛒 sind zwei solche Einheiten, und das Fenster zählt sie getrennt. In Python besteht ein String aus Codepoints, und 🛒 ist ein Zeichen. Ein Log mit lateinischen Buchstaben und Ziffern ist in allen vier Sprachen gleich.
Die Summe darf nicht überlaufen. int in Java reicht bis 2.147.483.647. Ein Jahr Umsatz in Cent einer großen Kette geht darüber hinaus: Dann ist die Summe ein long. Die Zähler in den Programmen oben sind aus demselben Grund long.
Die Summe darf nicht driften. Sind die Verkäufe in Euro mit Cent in einem double, fügt jedes +neu −alt einen winzigen Rundungsfehler hinzu, und die Fehler häufen sich: Nach Tausenden von Schritten ist die Summe des Fensters nicht mehr genau die Summe seiner Tage. Halte Geld in Cent, als ganze Zahlen. Sind die Zahlen von Natur aus Gleitkommazahlen (Temperaturen, Zeiten), berechne das Fenster alle paar Tausend Schritte von Grund auf neu.
Der Durchschnitt und das Größte. Der gleitende Durchschnitt ist die Summe geteilt durch k. Der größte Wert im Fenster funktioniert nicht mit +neu −alt: Ein Maximum lässt sich nicht „abziehen“. Dafür gibt es ein gleitendes Fenster mit einer doppelt-endenden Warteschlange (Deque), die die Kandidaten für das Maximum behält.
Übung
Der kürzeste Zeitraum mit mindestens 3500 € Umsatz
Löse die Aufgabe in deinem Editor.
Der kürzeste Zeitraum. Der Umsatz für 12 Tage ist 820 €, 640 €, 910 €, 700 €, 580 €, 1020 €, 760 €, 890 €, 610 €, 980 €, 720 € und 850 €. Was ist der kürzeste Zeitraum aufeinanderfolgender Tage mit mindestens 3500 € Umsatz? Das Fenster wächst nach rechts, und solange die Summe mindestens 3500 € beträgt, merke dir seine Länge, wenn sie kleiner ist, und verkleinere es von links.
Kürzester Zeitraum mit mindestens 3500 €: 5 Tage (von Tag 1 bis Tag 5)Weitere Aufgaben
- Die beste Woche. Finde mit dem Gleiten heraus, welche 7 aufeinanderfolgenden Tage den größten Umsatz haben, und gib sie aus.
- Ein gleitender Durchschnitt. Gib den durchschnittlichen Umsatz für je 7 Tage aus, auf den Cent gerundet.
- Verschiedene Kunden pro Stunde. Die Bestellungen sind nach Minute sortiert, jede mit einer Kundennummer. Wie viele verschiedene Kunden gibt es in jedem 60-Minuten-Fenster? Halte in einer Map, wie viele Bestellungen jeder Kunde im Fenster hat.
Test