Speicherkomplexität in JavaScript

Problem

Der Export, der den Speicher auffrisst

Jede Nacht exportiert ein Dienst die Logs des Tages des Shops in ein Archiv. Damit er nach einem Absturz dort weitermachen kann, wo er aufgehört hat, schreibt er nach jeder Zeile einen Checkpoint. Nur ist der Checkpoint eine Kopie der ganzen Datei bis dahin:

function exportLogs(logs) {
  const file = [];
  const checkpoints = [];
  for (const line of logs) {
    file.push(line);
    checkpoints.push([...file]);
  }
  let places = 0;
  for (const saved of checkpoints) {
    places += saved.length;
  }
  return places;
}

Wie viele Plätze belegen die Kopien? Das Programm zählt sie:

for (const n of [5, 1000]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`Zeile ${i}`);
  }
  console.log(`${n} Zeilen: ${exportLogs(logs)} Plätze`);
}

5 Zeilen: 15 Plätze
1000 Zeilen: 500500 Plätze

Bei 1000 Zeilen sind es 500.500 Plätze. Die Logs eines Tages sind 100.000 Zeilen, und das sind 5.000.050.000 Plätze. Jeder Platz hält eine Referenz von 4 bis 8 Byte: zwischen 20 und 40 GB nur für die Kopien. Im Test mit 1000 Zeilen läuft alles durch, und nachts bricht der Export mit JavaScript heap out of memory ab.

Die Idee

Auch Speicher kostet

Bisher hast du Operationen gezählt. Speicher zählt man genauso: wie viele Plätze der Algorithmus selbst anlegt, abgesehen von der Eingabe, die er bekommt. Das ist die Speicherkomplexität des Algorithmus. Sie wird ebenfalls mit Big-O geschrieben:

O(1): ein paar Variablen, egal wie groß die Eingabe ist;
O(n): eine Kopie der Eingabe, eine Hilfsliste, ein Set mit allen Elementen;
O(n²): bei jedem Schritt eine Kopie der Kopie, wie im Export.

Die Eingabe zählt nicht, weil es sie auch ohne den Algorithmus gibt. Das Ergebnis, das die Aufgabe verlangt, zählt ebenfalls nicht: Die Datei mit n Zeilen ist die Aufgabe des Exports. Zählen tun die Kopien, die er unterwegs macht.

Sieh es dir an

Die Kopien bleiben

const file = [];
let checkpoint = 0;
for (const line of logs) {
  file.push(line);
  checkpoint = file.length;
}

Schritt für Schritt, in Worten

file ist die Datei, die der Export schreibt, und logs hat 4 Zeilen. checkpoints merkt sich, wo es nach einem Absturz weitergeht.
Zeile 1 kommt in die Datei. Der Checkpoint ist eine Kopie der ganzen Datei: 1 Platz.
Zeile 2. Der neue Checkpoint kopiert beide Zeilen, und der alte bleibt in der Liste: 1 + 2 = 3 Plätze.
Nach 4 Zeilen belegt der Speicher 1 + 2 + 3 + 4 = 10 Plätze. Nach n Zeilen sind es n(n + 1)/2: fünf Milliarden bei 100 000 Zeilen.
Um nach einem Absturz weiterzumachen, brauchst du nur, wie weit du gekommen bist. Die Kopien verschwinden, eine Zahl bleibt.
Jede Zeile ändert die Zahl: checkpoint = 4. Der zusätzliche Speicher ist 1 Platz, egal wie viele Zeilen es sind.

Jede Kopie ist eine neue Liste im Speicher, und die alten löscht niemand: Die Liste checkpoints hält sie fest. Deshalb wachsen die Plätze wie 1 + 2 + 3 + … + n. Um nach einem Absturz weiterzumachen, braucht der Export nur zu wissen, wie weit er gekommen ist:

function exportLogs(logs) {
  const file = [];
  let checkpoint = 0;
  for (const line of logs) {
    file.push(line);
    checkpoint = file.length;
  }
  return checkpoint;
}

for (const n of [5, 1000]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`Zeile ${i}`);
  }
  console.log(`${n} Zeilen, checkpoint: ${exportLogs(logs)}`);
}

5 Zeilen, checkpoint: 5
1000 Zeilen, checkpoint: 1000

Die Datei ist dieselbe, und der zusätzliche Speicher ist eine Zahl: O(1) statt O(n²).

Probier es aus

Sag die Ausgabe voraus

Der Export mit den Kopien bekommt 6 Zeilen. Wie viele Plätze belegen die Checkpoints?

function exportLogs(logs) {
  const file = [];
  const checkpoints = [];
  for (const line of logs) {
    file.push(line);
    checkpoints.push([...file]);
  }
  let places = 0;
  for (const saved of checkpoints) {
    places += saved.length;
  }
  return places;
}

for (const n of [6]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`Zeile ${i}`);
  }
  console.log(`${n} Zeilen: ${exportLogs(logs)} Plätze`);
}

Antwort

6 Zeilen: 36 Plätze

6 Zeilen: 21 Plätze

6 Zeilen: 6 Plätze

Sieh es dir an

Eine Kopie oder an Ort und Stelle

Der Admin möchte die neuesten Log-Zeilen zuerst. Es gibt zwei Wege. Der eine macht eine neue Liste in umgekehrter Reihenfolge, der andere vertauscht die Elemente in der Liste selbst: das erste mit dem letzten, das zweite mit dem vorletzten, bis sich die beiden Enden treffen.

function newestFirst(logs) {
  const result = [];
  for (let i = logs.length - 1; i >= 0; i--) {
    result.push(logs[i]);
  }
  return result;
}

function reverseInPlace(logs) {
  let left = 0;
  let right = logs.length - 1;
  while (left < right) {
    [logs[left], logs[right]] = [logs[right], logs[left]];
    left++;
    right--;
  }
}

const logs = ["09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung"];
const newest = newestFirst(logs);
console.log("Kopie:    " + newest.join(", "));
console.log("Original: " + logs.join(", "));
reverseInPlace(logs);
console.log("Direkt:   " + logs.join(", "));

Kopie:    09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung
Original: 09:00 Anmeldung, 09:05 Warenkorb, 09:07 Zahlung
Direkt:   09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung

Die Kopie braucht n neue Plätze, aber das Original bleibt, wie es war. Die Änderung an Ort und Stelle braucht einen Platz für den Tausch, aber die alte Reihenfolge ist weg. Was besser ist, hängt davon ab, ob noch jemand das Original liest.

Genauer, für Neugierige

Die eingebauten Funktionen treffen dieselbe Wahl, und der Name verrät sie nicht immer:

const logs = ["09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung"];
const copy = logs.toReversed();
logs.reverse();
console.log("Direkt:   " + logs.join(", "));
console.log("Kopie:    " + copy.join(", "));

Direkt:   09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung
Kopie:    09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung

reverse() kehrt an Ort und Stelle um, und toReversed() (seit 2023, Node 20) macht eine Kopie. Auch slice() und [...logs] kopieren: In einer Rekursion kopiert logs.slice(1) bei jedem Aufruf fast das ganze Array.

Die Kopie ist flach: Die neue Liste hält Referenzen auf dieselben Texte, keine neuen Texte. Deshalb zählen die Plätze einen pro Element.

Probier es aus

Ergänze

Vervollständige den Tausch der beiden Enden:

[logs[left], logs[right]] = [logs[right], ];

Sieh es dir an

Auch Rekursion hält Speicher

Nicht nur eine Liste braucht Platz. Jeder Aufruf einer Funktion hält seine Parameter und lokalen Variablen auf dem Aufrufstapel, bis er zurückkehrt. Hier werden die Fehler im Log mit Rekursion und mit einer Schleife gezählt:

function errorsFrom(logs, i) {
  if (i === logs.length) {
    return 0;
  }
  const here = logs[i].startsWith("ERROR") ? 1 : 0;
  return here + errorsFrom(logs, i + 1);
}

function errors(logs) {
  let count = 0;
  for (const line of logs) {
    if (line.startsWith("ERROR")) {
      count++;
    }
  }
  return count;
}

const small = makeLogs(500);
const big = makeLogs(1_000_000);
console.log(`500 Zeilen: ${errorsFrom(small, 0)} Fehler`);
try {
  console.log(`1000000 Zeilen: ${errorsFrom(big, 0)} Fehler`);
} catch (e) {
  console.log(`1000000 Zeilen: ${e.name}`);
}
console.log(`Mit Schleife: ${errors(big)} Fehler`);

500 Zeilen: 5 Fehler
1000000 Zeilen: RangeError
Mit Schleife: 10000 Fehler

Die Rekursion erzeugt keine einzige Liste, aber bei n Zeilen liegen n unfertige Aufrufe auf dem Stapel: O(n) Speicher. Der Stapel ist klein, und eine Million Aufrufe passen nicht hinein. Die Schleife hat eine Variable count: O(1).

Genauer, für Neugierige

Wie tief die Rekursion gehen kann, hängt von der Größe des Stapels und der Größe eines Frames ab. In Node ist der Stapel etwa 1 MB groß, das sind je nach Frame ein paar Tausend bis einige Zehntausend Aufrufe. RangeError ist der Name des Fehlers.

Ist der rekursive Aufruf die letzte Aktion der Funktion (ohne here + danach), machen manche Sprachen daraus eine Schleife (Tail Call). Java, C#, Python und Node tun das nicht, deshalb kostet die Tiefe in ihnen immer Speicher.

Die Idee

Zeit gegen Speicher

Der Shop prüft, ob zwei Bestellungen des Tages dieselbe Nummer haben. Der erste Weg vergleicht jedes Paar. Der zweite merkt sich die gesehenen Nummern in einem Set:

function hasDuplicateLoops(orders) {
  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      if (orders[i] === orders[j]) {
        return true;
      }
    }
  }
  return false;
}

function hasDuplicateSet(orders) {
  const seen = new Set();
  for (const order of orders) {
    if (seen.has(order)) {
      return true;
    }
    seen.add(order);
  }
  return false;
}

const today = [100512, 100513, 100514, 100512];
console.log(hasDuplicateLoops(today), hasDuplicateSet(today));

true true

Beide geben dieselbe Antwort, zahlen aber unterschiedlich:

die verschachtelten Schleifen: O(1) Speicher und O(n²) Zeit;
das Set: O(n) Speicher (bis zu n Nummern) und O(n) Zeit.

Das ist ein häufiger Tausch: Speicher gegen Zeit. Wie viele Vergleiche und Prüfungen beide machen, wenn es keine Wiederholung gibt (der schlechteste Fall):

function comparisonsLoops(orders) {
  let count = 0;
  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      count++;
      if (orders[i] === orders[j]) {
        return count;
      }
    }
  }
  return count;
}

function checksSet(orders) {
  const seen = new Set();
  let count = 0;
  for (const order of orders) {
    count++;
    if (seen.has(order)) {
      return count;
    }
    seen.add(order);
  }
  return count;
}

for (const n of [10, 1000]) {
  const orders = [];
  for (let i = 0; i < n; i++) {
    orders.push(100000 + i);
  }
  console.log(`${n} Bestellungen: ${comparisonsLoops(orders)} Vergleiche mit Schleifen, ${checksSet(orders)} Prüfungen mit Set`);
}

10 Bestellungen: 45 Vergleiche mit Schleifen, 10 Prüfungen mit Set
1000 Bestellungen: 499500 Vergleiche mit Schleifen, 1000 Prüfungen mit Set

Verschachtelte Schleifen, ohne Gedächtnis O(n²)
Eine Menge gesehener Zahlen, n Plätze O(n)

Algorithmus	n = 10	n = 1.000	n = 100.000
Verschachtelte Schleifen, ohne Gedächtnis	45	499.500	≈ 4.995.000.000
Eine Menge gesehener Zahlen, n Plätze	10	1.000	100.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.

Bei 100.000 Bestellungen machen die Schleifen fast 5 Milliarden Vergleiche, und das Set macht 100.000 Prüfungen und hält 100.000 Nummern. Wenn der Speicher da ist, gewinnt das Set. Wenn nicht (ein kleines Gerät, eine riesige Eingabe), sortierst du entweder die Nummern (dann liegen die Wiederholungen nebeneinander) oder liest in Teilen.

Genauer, für Neugierige

Wir zählen eine Prüfung im Set als eine Operation. Sie ist im Durchschnitt O(1), weil das Set eine Hashtabelle ist: Aus der Nummer wird ein Hash, und der Hash sagt, in welchem Bucket man nachsieht. Ein Platz in einem Set kostet mehr als eine Zahl in einem Array: in einem Set etwa 20–40 Byte je nach Engine. „O(n) Speicher“ für 10 Millionen Bestellungen sind also Hunderte MB, nicht 40.

Probier es aus

Finde den Fehler

Ein Kollege hat die Prüfung mit einem Set umgeschrieben, aber sie findet nie eine Wiederholung:

function hasDuplicateSet(orders) {
  for (const order of orders) {
    const seen = new Set();
    if (seen.has(order)) {
      return true;
    }
    seen.add(order);
  }
  return false;
}

const today = [100512, 100513, 100514, 100512];
console.log(hasDuplicateSet(today));

false

Die Nummer 100512 kommt zweimal vor, und die Antwort ist „nein“. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Übung

Die letzten drei Zeilen

Löse die Aufgabe in deinem Editor.

Die letzten Zeilen. Wenn etwas kaputtgeht, will der Admin nur die letzten k Zeilen des Logs. Schreibe lastLines(logs, k), das sie zurückgibt und dabei höchstens k Zeilen im Speicher hält, nicht das ganze Log: O(k) Speicher. Lass es mit 1000 Zeilen („Zeile 1“ … „Zeile 1000“) und k = 3 laufen.

Zeile 998
Zeile 999
Zeile 1000

Eine mögliche Lösung

Halte eine Warteschlange: Jede neue Zeile kommt hinten hinein, und sind es mehr als k Zeilen, geht die älteste vorn hinaus.

function lastLines(logs, k) {
  const recent = [];
  for (const line of logs) {
    recent.push(line);
    if (recent.length > k) {
      recent.shift();
    }
  }
  return recent;
}

shift() verschiebt alle Elemente um einen Platz nach links, aber es sind höchstens k, also ist ein Schritt O(k).

Weitere Aufgaben

Die durchschnittliche Länge ohne Kopie. Berechne die durchschnittliche Länge einer Zeile im Log mit O(1) zusätzlichem Speicher: ohne neue Liste von Längen.
Fehler pro Stunde. Zähle die Fehler für jede Stunde (09, 10 …). Wie viel Speicher braucht deine Lösung, wenn es 24 Stunden und eine Million Zeilen gibt?
Die wiederholten Nummern. Gib nicht nur „ja oder nein“ zurück, sondern alle wiederholten Nummern. Wie viel Speicher braucht die Lösung mit einem Set, und geht es auch ohne?

Test

Teste dich

1. Eine Funktion erzeugt eine neue Liste mit n Log-Zeilen in umgekehrter Reihenfolge. Wie viel zusätzlichen Speicher braucht sie?O(n²)O(1)O(n)

2. Der Export hält nach jeder Zeile eine Kopie der ganzen Datei bis dahin. Wie viele Plätze belegt der Speicher bei n Zeilen?2nn(n + 1)/2, also O(n²)n

3. Eine rekursive Funktion ganz ohne Liste ruft sich 1.000.000-mal auf, ein Aufruf im anderen. Wie viel Speicher braucht sie?O(1), weil es keine Listen gibtKeinen, Speicher ist nur für ObjekteO(n): Jeder Aufruf bleibt auf dem Stapel, bis er zurückkehrt

4. Du suchst eine wiederholte Nummer in 10.000.000 Bestellungen auf einem Server mit ein paar GB freiem Speicher. Was wählst du?Das Set: O(n) Speicher, aber O(n) Zeit statt O(n²)Die verschachtelten Schleifen, weil sie keinen Speicher brauchenEs macht keinen Unterschied

5. Was zählt nicht zum zusätzlichen Speicher einer Funktion?Die Eingabe, die die Funktion bekommtEine Kopie der Eingabe, die die Funktion machtDer Stapel ihrer Rekursion

Speicherkomplexität

Cookies