Speicherkomplexität in Java

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:

static long exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    List<List<String>> checkpoints = new ArrayList<>();
    for (String line : logs) {
        file.add(line);
        checkpoints.add(new ArrayList<>(file));
    }
    long places = 0;
    for (List<String> saved : checkpoints) {
        places += saved.size();
    }
    return places;
}

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

for (int n : new int[] {5, 1000}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("Zeile " + i);
    }
    System.out.println(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 OutOfMemoryError 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

List<String> file = new ArrayList<>();
int checkpoint = 0;
for (String line : logs) {
    file.add(line);
    checkpoint = file.size();
}

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:

static int exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    int checkpoint = 0;
    for (String line : logs) {
        file.add(line);
        checkpoint = file.size();
    }
    return checkpoint;
}

for (int n : new int[] {5, 1000}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("Zeile " + i);
    }
    System.out.println(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?

static long exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    List<List<String>> checkpoints = new ArrayList<>();
    for (String line : logs) {
        file.add(line);
        checkpoints.add(new ArrayList<>(file));
    }
    long places = 0;
    for (List<String> saved : checkpoints) {
        places += saved.size();
    }
    return places;
}

for (int n : new int[] {6}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("Zeile " + i);
    }
    System.out.println(n + " Zeilen: " + exportLogs(logs) + " Plätze");
}

Antwort

6 Zeilen: 6 Plätze

6 Zeilen: 36 Plätze

6 Zeilen: 21 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.

static List<String> newestFirst(List<String> logs) {
    List<String> result = new ArrayList<>();
    for (int i = logs.size() - 1; i >= 0; i--) {
        result.add(logs.get(i));
    }
    return result;
}

static void reverseInPlace(List<String> logs) {
    int left = 0;
    int right = logs.size() - 1;
    while (left < right) {
        String saved = logs.get(left);
        logs.set(left, logs.get(right));
        logs.set(right, saved);
        left++;
        right--;
    }
}

List<String> logs = new ArrayList<>(List.of("09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung"));
List<String> newest = newestFirst(logs);
System.out.println("Kopie:    " + String.join(", ", newest));
System.out.println("Original: " + String.join(", ", logs));
reverseInPlace(logs);
System.out.println("Direkt:   " + String.join(", ", logs));

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:

List<String> logs = new ArrayList<>(List.of("09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung"));
List<String> view = logs.reversed();
List<String> copy = new ArrayList<>(view);
Collections.reverse(logs);
System.out.println("Direkt:   " + String.join(", ", logs));
System.out.println("Kopie:    " + String.join(", ", copy));

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

Collections.reverse kehrt an Ort und Stelle um. logs.reversed() (seit Java 21) kopiert nichts: Es ist eine Sicht, die dieselbe Liste von hinten liest. Kopiert wird erst mit new ArrayList<>(...). Dasselbe gilt für subList: eine Sicht, keine Kopie.

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:

String saved = logs.get(left);
logs.set(left, logs.get(right));
logs.set(right, );

Zuerst wird der Wert links in saved gemerkt, weil ihn die nächste Zeile überschreibt. Dann kommt er auf den Platz rechts.

Sieh es dir an

Auch Rekursion hält Speicher

Nicht nur eine Liste braucht Platz. Jeder Aufruf einer Methode 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:

static int errorsFrom(List<String> logs, int i) {
    if (i == logs.size()) {
        return 0;
    }
    int here = logs.get(i).startsWith("ERROR") ? 1 : 0;
    return here + errorsFrom(logs, i + 1);
}

static int errors(List<String> logs) {
    int count = 0;
    for (String line : logs) {
        if (line.startsWith("ERROR")) {
            count++;
        }
    }
    return count;
}

List<String> small = makeLogs(500);
List<String> big = makeLogs(1_000_000);
System.out.println("500 Zeilen: " + errorsFrom(small, 0) + " Fehler");
try {
    System.out.println("1000000 Zeilen: " + errorsFrom(big, 0) + " Fehler");
} catch (StackOverflowError e) {
    System.out.println("1000000 Zeilen: StackOverflowError");
}
System.out.println("Mit Schleife: " + errors(big) + " Fehler");

500 Zeilen: 5 Fehler
1000000 Zeilen: StackOverflowError
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 Java ist der Stapel eines Threads standardmäßig 1 MB groß und wird mit -Xss geändert (die Prüfung der Seite startet die Programme mit 8 MB, und es reicht trotzdem nicht). StackOverflowError ist ein Error, keine Exception: Hier fangen wir ihn ab, damit du den Namen siehst, und in echtem Code schreibt man die Rekursion als Schleife um.

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:

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

static boolean hasDuplicateSet(int[] orders) {
    Set<Integer> seen = new HashSet<>();
    for (int order : orders) {
        if (!seen.add(order)) {
            return true;
        }
    }
    return false;
}

int[] today = {100512, 100513, 100514, 100512};
System.out.println(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):

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

static long checksSet(int[] orders) {
    Set<Integer> seen = new HashSet<>();
    long count = 0;
    for (int order : orders) {
        count++;
        if (!seen.add(order)) {
            return count;
        }
    }
    return count;
}

for (int n : new int[] {10, 1000}) {
    int[] orders = new int[n];
    for (int i = 0; i < n; i++) {
        orders[i] = 100000 + i;
    }
    System.out.println(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 HashSet<Integer> etwa 40–50 Byte (ein Integer-Objekt und ein Eintrag in der Tabelle). „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:

static boolean hasDuplicateSet(int[] orders) {
    for (int order : orders) {
        Set<Integer> seen = new HashSet<>();
        if (!seen.add(order)) {
            return true;
        }
    }
    return false;
}

int[] today = {100512, 100513, 100514, 100512};
System.out.println(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.

static List<String> lastLines(List<String> logs, int k) {
    ArrayDeque<String> recent = new ArrayDeque<>();
    for (String line : logs) {
        recent.addLast(line);
        if (recent.size() > k) {
            recent.removeFirst();
        }
    }
    return new ArrayList<>(recent);
}

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