Präfixsummen in JavaScript

Problem

Das Dashboard, das jedes Mal neu summiert

Das Shop-Dashboard zeigt den Umsatz für einen gewählten Zeitraum: „von Tag 120 bis Tag 340“, „die letzten 30 Tage“, „diese Woche gegen letzte Woche“. Die Manager öffnen es mehrmals am Tag, und jedes Diagramm fragt nach Dutzenden von Zeiträumen. Der Code summiert die Tage jedes Zeitraums jedes Mal neu:

function rangeSum(revenue, a, b) {
  let sum = 0;
  for (let day = a; day <= b; day++) {
    sum += revenue[day];
  }
  return sum;
}

Tausend Tage Umsatz und tausend Abfragen:

const revenue = revenueOf(1000);
const queries = queriesOf(1000);
let total = 0;
let additions = 0;
for (const [a, b] of queries) {
  total += rangeSum(revenue, a, b);
  additions += b - a + 1;
}
console.log(`Abfragen: ${queries.length}`);
console.log(`Summe der Antworten: ${total}`);
console.log(`Additionen: ${additions}`);

Abfragen: 1000
Summe der Antworten: 68412493
Additionen: 248794

248.794 Additionen für tausend Antworten. Die Tage ändern sich zwischen zwei Abfragen nicht, und doch addiert der Code sie immer wieder. Je länger die Zeiträume und je mehr Abfragen, desto langsamer wird das Dashboard.

Woher die Tage und die Abfragen kommen

Der Umsatz und die Abfragen folgen einer Formel, damit die Programme in allen vier Sprachen und der Vergleich unten im Browser genau dieselben bauen:

function revenueOf(n) {
  return Array.from({ length: n }, (_, i) => 50 + ((i * 37) % 451));
}

function queriesOf(n) {
  const queries = [];
  for (let k = 0; k < n; k++) {
    const a = (k * 7919) % n;
    queries.push([a, a + ((k * 4231) % (n - a))]);
  }
  return queries;
}

Die Idee

Die Summe von allem links

Berechne einmal für jeden Tag den Umsatz vom Anfang bis zu diesem Tag. Das ist eine Präfixsumme: prefix[k] ist die Summe der ersten k Tage.

prefix[0] = 0: die Summe von gar keinen Tagen;
prefix[k + 1] = prefix[k] + revenue[k]: Jeder Platz ist der vorige plus ein Tag.

Das Array hat einen Platz mehr, als es Tage gibt. Danach ist jeder Zeitraum die Differenz zweier Zahlen. Der Umsatz von Tag a bis Tag b sind die Tage 0 bis b minus die Tage 0 bis a − 1:

prefix[b + 1] − prefix[a]

Das Bauen sind n Additionen, einmal. Jede Abfrage danach sind zwei Lesezugriffe und eine Subtraktion, ob der Zeitraum zwei Tage oder zwei Jahre ist: O(1) pro Abfrage statt O(n).

Sieh es dir an

Die Präfixsummen, Tag für Tag

function buildPrefix(revenue) {
  const prefix = new Array(revenue.length + 1).fill(0);
  for (let i = 0; i < revenue.length; i++) {
    prefix[i + 1] = prefix[i] + revenue[i];
  }
  return prefix;
}

function rangeSum(prefix, a, b) {
  return prefix[b + 1] - prefix[a];
}

const revenue = [120, 80, 150, 90, 200, 60, 110, 140];
const prefix = buildPrefix(revenue);
console.log(`prefix: [${prefix.join(", ")}]`);
console.log(`Tage 2–5: ${rangeSum(prefix, 2, 5)}`);

prefix: [0, 120, 200, 350, 440, 640, 700, 810, 950]
Tage 2–5: 500

function buildPrefix(revenue) {
  const prefix = new Array(revenue.length + 1).fill(0);
  for (let i = 0; i < revenue.length; i++) {
    prefix[i + 1] = prefix[i] + revenue[i];
  }
  return prefix;
}

function rangeSum(prefix, a, b) {
  return prefix[b + 1] - prefix[a];
}

Schritt für Schritt, in Worten

8 Tage Umsatz. prefix hat 9 Plätze: prefix[0] = 0 ist die Summe von gar keinen Tagen.
prefix[1] = prefix[0] + revenue[0] = 0 + 120 = 120: Tage 0–0.
prefix[2] = prefix[1] + revenue[1] = 120 + 80 = 200: Tage 0–1.
prefix[3] = prefix[2] + revenue[2] = 200 + 150 = 350: Tage 0–2.
prefix[4] = prefix[3] + revenue[3] = 350 + 90 = 440: Tage 0–3.
prefix[5] = prefix[4] + revenue[4] = 440 + 200 = 640: Tage 0–4.
prefix[6] = prefix[5] + revenue[5] = 640 + 60 = 700: Tage 0–5.
prefix[7] = prefix[6] + revenue[6] = 700 + 110 = 810: Tage 0–6.
prefix[8] = prefix[7] + revenue[7] = 810 + 140 = 950: Tage 0–7.
8 Additionen, einmal. Jetzt die Abfrage: der Umsatz von Tag 2 bis Tag 5. prefix[6] = 700 € sind die Tage 0–5.
prefix[2] = 200 € sind die Tage 0–1, der Teil vor dem Zeitraum. Ziehen wir ihn ab.
700 − 200 = 500 €: die Tage 2–5 mit zwei Lesezugriffen und einer Subtraktion, egal wie lang der Zeitraum ist.
Das Bauen kostet einmal n Additionen; jede Abfrage danach kostet eine Subtraktion.

In der Szene sitzt prefix[k] auf der Grenze zwischen Tag k − 1 und Tag k. Das zeigt, dass es die Summe von allem links der Grenze ist und ein Zeitraum die Differenz zweier Grenzen.

Genauer, für Neugierige

Was die Sprachen dir geben.

JavaScript hat keine fertigen Präfixsummen. Die Schleife oben ist der übliche Weg. Mit reduce passt sie in eine Zeile, wird aber nicht klarer.

Überlauf. Zahlen in JavaScript sind bis 2⁵³ exakt, etwa 9 · 10¹⁵. Umsatz in Cent erreicht das nur mit unglaublichen Beträgen. In Java und C# ist das Array long, weil dort int bei 2.147.483.647 endet.

Probier es aus

Sag prefix voraus

Drei Tage Umsatz: 30 €, 50 € und 20 €.

const revenue = [30, 50, 20];
const prefix = buildPrefix(revenue);
console.log(`prefix: [${prefix.join(", ")}]`);

Antwort

prefix: [0, 30, 80, 100]

prefix: [30, 80, 100]

prefix: [0, 30, 50, 20]

Probier es aus

Ergänze

Der Umsatz von Tag a bis Tag b einschließlich:

return prefix[] - prefix[a];

Die Idee

Die Null davor

Warum hat das Array einen Platz mehr? Es geht auch ohne: prefix[k] könnte die Summe der Tage 0 bis k einschließlich sein. Dann ist der Zeitraum von a bis b prefix[b] − prefix[a − 1]. Aber für a = 0 gibt es keinen Platz a − 1, und jede Abfrage braucht eine Prüfung „wenn a gleich 0 ist“.

Die Null davor beseitigt diese Prüfung. Der Preis ist ein Platz im Array, und die Falle ist, dass sich die Indizes um eins verschieben: prefix[k] ist die Summe der Tage vor k, nicht bis k. Deshalb ist ein Off-by-one-Fehler hier der häufigste Fehler, wie bei der binären Suche.

Probier es aus

Finde den Fehler

Jemand hat die Präfixsummen ohne die Null davor geschrieben. Die Abfrage für die Tage 2–5 sollte 500 € ergeben:

const revenue = [120, 80, 150, 90, 200, 60, 110, 140];
const prefix = buildPrefix(revenue);
console.log(`Tage 2–5: ${rangeSum(prefix, 2, 5)}`);

Tage 2–5: 350

Wähle die Zeile mit dem Fehler.

Sieh es dir an

Miss es: neu summieren gegen die Präfixsummen

Dieselben tausend Abfragen, mit den Präfixsummen:

const revenue = revenueOf(1000);
const queries = queriesOf(1000);
const prefix = buildPrefix(revenue);
let operations = revenue.length;
let total = 0;
for (const [a, b] of queries) {
  total += rangeSum(prefix, a, b);
  operations++;
}
console.log(`Abfragen: ${queries.length}`);
console.log(`Summe der Antworten: ${total}`);
console.log(`Additionen und Subtraktionen: ${operations}`);

Abfragen: 1000
Summe der Antworten: 68412493
Additionen und Subtraktionen: 2000

Die Summe der Antworten ist dieselbe, und die Arbeit sind 2.000 Operationen statt 248.794: tausend Additionen für prefix und eine Subtraktion pro Abfrage. Lass beide im Browser laufen. n ist sowohl die Zahl der Tage als auch die Zahl der Abfragen:

Neu summieren bei jeder Anfrage O(n²)
Präfixsummen O(n)

Algorithmus	n = 10	n = 1.000	n = 100.000
Neu summieren bei jeder Anfrage	10	248.794	≈ 2.487.940.000
Präfixsummen	20	2.000	200.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

function buildPrefix(revenue) {
  const prefix = new Array(revenue.length + 1).fill(0);
  for (let i = 0; i < revenue.length; i++) {
    prefix[i + 1] = prefix[i] + revenue[i];
  }
  return prefix;
}

function rangeSum(prefix, a, b) {
  return prefix[b + 1] - prefix[a];
}

Neu summieren ist O(n) pro Abfrage, O(n²) für n Abfragen. Mit den Präfixsummen ist es einmal O(n) und O(1) pro Abfrage. Der Preis ist Speicher: ein Array mit n + 1 Zahlen.

Zweidimensionale Präfixsummen: Bestellungen nach Tag und Stunde

Die Heatmap der Bestellungen ist eine Tabelle: Die Zeilen sind Wochentage, die Spalten Stunden. Die Frage ist „wie viele Bestellungen gibt es am Dienstag und Mittwoch von 10:00 bis 13:00 Uhr“, also die Summe in einem Rechteck.

p[r][c] ist die Summe des Rechtecks von der Ecke oben links bis Zeile r − 1 und Spalte c − 1, wieder mit Nullen davor (Zeile 0 und Spalte 0). Jeder Platz ist die Zelle plus das Rechteck darüber und das links davon. Die Ecke dazwischen wurde doppelt gezählt, also wird sie einmal abgezogen:

function buildPrefix2D(orders) {
  const rows = orders.length;
  const cols = orders[0].length;
  const p = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      p[r + 1][c + 1] = orders[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c];
    }
  }
  return p;
}

function rect(p, r1, c1, r2, c2) {
  return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
}

const orders = [
  [3, 8, 12, 9, 5, 4],
  [2, 7, 14, 11, 6, 3],
  [4, 9, 15, 10, 7, 5],
  [1, 6, 11, 8, 4, 2],
];
const p = buildPrefix2D(orders);
console.log(`Bestellungen Di–Mi von 10 bis 13 Uhr: ${rect(p, 1, 1, 2, 3)}`);

Bestellungen Di–Mi von 10 bis 13 Uhr: 66

Die Abfrage ist dieselbe Idee: das ganze Rechteck bis zur Ecke unten rechts, minus der Streifen darüber, minus der Streifen links, plus die Ecke, die doppelt abgezogen wurde. Vier Lesezugriffe für ein Rechteck beliebiger Größe.

Die Idee

Wie viele Zeiträume ergeben genau 50 €

Der Shop hat Tage mit Verlust: Zurückgeschickte Bestellungen werden vom Umsatz abgezogen. Die Frage ist, wie viele Zeiträume aufeinanderfolgender Tage genau 50 € Gewinn haben.

Jeder Zeitraum von Tag i bis Tag j ist die Differenz zweier Präfixsummen: prefix[j + 1] − prefix[i]. Sie ist genau dann 50, wenn prefix[i] = prefix[j + 1] − 50. Du gehst also die Tage durch, behältst die aktuelle Präfixsumme und fragst: Wie oft habe ich bisher eine Präfixsumme gesehen, die gleich der aktuellen minus 50 ist? Die Antwort steht in einer Map von Präfixsumme auf Häufigkeit:

function countPeriods(profit, target) {
  const seen = new Map([[0, 1]]);
  let prefix = 0;
  let count = 0;
  for (const p of profit) {
    prefix += p;
    count += seen.get(prefix - target) ?? 0;
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }
  return count;
}

const profit = [40, -10, 30, 20, -30, 50, -20, 30, 0, 20];
console.log(`Zeiträume mit 50 € Gewinn: ${countPeriods(profit, 50)}`);

Zeiträume mit 50 € Gewinn: 8

Ein Durchgang über die Tage und ein Nachschlagen in einer Hashtabelle pro Tag: O(n). Zwei verschachtelte Schleifen über alle Zeiträume wären O(n²). Die Map ist hier ein Zähler: wie oft jeder Wert gesehen wurde. Das ist eine eigene Technik und das Thema der nächsten Lektion.

Genauer, für Neugierige

seen beginnt mit 0 → 1, weil die Präfixsumme vor dem ersten Tag 0 ist. Ohne sie werden die Zeiträume, die an Tag 0 beginnen, nicht gezählt.

Hätte jeder Tag Gewinn gemacht, würde auch ein gleitendes Fenster funktionieren: rechts vergrößern, solange die Summe unter 50 liegt, links verkleinern, sobald sie darüber liegt. Mit negativen Zahlen scheitert das: Das Verkleinern kann die Summe erhöhen, und das Fenster weiß nicht, in welche Richtung es gehen soll. Präfixsummen mit einer Map funktionieren mit beliebigen Zahlen.

Probier es aus

Sag die Anzahl voraus

Vier Tage Gewinn: 20 €, 30 €, −30 € und 30 €. Wie viele Zeiträume aufeinanderfolgender Tage ergeben genau 50 €?

const profit = [20, 30, -30, 30];
console.log(`Zeiträume mit 50 € Gewinn: ${countPeriods(profit, 50)}`);

Antwort

Zeiträume mit 50 € Gewinn: 2

Zeiträume mit 50 € Gewinn: 3

Zeiträume mit 50 € Gewinn: 1

Übung

Das Lager, Tag für Tag

Löse die Aufgabe in deinem eigenen Editor.

Geliefert, verkauft, auf Lager. Das Lager beginnt mit 40 Stück eines Produkts. Für zehn Tage hast du zwei Arrays:

geliefert: 0, 25, 0, 30, 10, 0, 40, 0, 15, 0;
verkauft: 12, 8, 15, 9, 20, 11, 7, 18, 10, 14.

Baue die Präfixsummen beider Arrays. Gib für die Zeiträume Tage 2–5, 0–9 und 6–8 aus, wie viel geliefert und wie viel verkauft wurde und wie hoch der Bestand am Ende des letzten Tages ist. Jede Antwort muss aus wenigen Lesezugriffen auf die Präfixsummen kommen, ohne Schleife über die Tage.

Tage 2–5: geliefert 40, verkauft 55, Bestand am Ende 30
Tage 0–9: geliefert 120, verkauft 124, Bestand am Ende 36
Tage 6–8: geliefert 55, verkauft 35, Bestand am Ende 50

Weitere Aufgaben

Die durchschnittliche Bestellung in einem Zeitraum. Neben dem Umsatz hast du auch die Zahl der Bestellungen pro Tag. Ein durchschnittlicher Bestellwert lässt sich nicht addieren, aber die beiden Summen schon. Wie beantwortest du „die durchschnittliche Bestellung von Tag a bis Tag b“?
Die beste Woche. Finde mit den Präfixsummen die sieben aufeinanderfolgenden Tage mit dem höchsten Umsatz. Wie viele Operationen braucht das bei 365 Tagen?
Die Heatmap. Füge Freitag und Samstag zu den zweidimensionalen Summen hinzu und finde das Zwei-Stunden-Fenster mit den meisten Bestellungen der ganzen Woche.

Test

Teste dich

1. Der Umsatz für vier Tage ist 10 €, 20 €, 30 € und 40 €. Was ist prefix?[0, 10, 20, 30, 40][0, 10, 30, 60, 100][10, 30, 60, 100]

2. Welches liefert den Umsatz von Tag a bis Tag b einschließlich?prefix[b + 1] − prefix[a]prefix[b] − prefix[a]prefix[b + 1] − prefix[a + 1]

3. Der Umsatz von gestern wird wegen einer zurückgeschickten Bestellung korrigiert. Was passiert mit prefix?Nichts: prefix hängt nicht von gestern abJeder Platz nach diesem Tag ändert sich: Die Korrektur kostet O(n)Nur ein Platz ändert sich

4. In countPeriods beginnt die Map seen mit 0 → 1. Warum?Es ist egal, es beschleunigt nurWegen der Zeiträume, die an Tag 0 beginnen: Für sie suchen wir die Präfixsumme 0 von vor dem ersten TagDamit sie nicht leer ist

Präfixsummen

Cookies