Speicherkomplexität
Kurz gesagt: Die Speicherkomplexität sagt, wie viel zusätzlichen Speicher ein Algorithmus im Verhältnis zur Eingabe braucht: eine Kopie oder eine Änderung an Ort und Stelle, der Rekursionsstapel und das Tauschen von Zeit gegen Speicher.
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:
def export_logs(logs): file = [] checkpoints = [] for line in logs: file.append(line) checkpoints.append(file.copy()) return sum(len(saved) for saved in checkpoints)Wie viele Plätze belegen die Kopien? Das Programm zählt sie:
for n in [5, 1000]: logs = [f"Zeile {i}" for i in range(1, n + 1)] print(f"{n} Zeilen: {export_logs(logs)} Plätze")5 Zeilen: 15 Plätze1000 Zeilen: 500500 PlätzeBei 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 MemoryError 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
file = []checkpoint = 0for line in logs: file.append(line) checkpoint = len(file)file = []checkpoints = []for line in logs: file.append(line) checkpoints.append(file.copy())file = []checkpoint = 0for line in logs: file.append(line) checkpoint = len(file)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:
def export_logs(logs): file = [] checkpoint = 0 for line in logs: file.append(line) checkpoint = len(file) return checkpointfor n in [5, 1000]: logs = [f"Zeile {i}" for i in range(1, n + 1)] print(f"{n} Zeilen, checkpoint: {export_logs(logs)}")5 Zeilen, checkpoint: 51000 Zeilen, checkpoint: 1000Die 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?
def export_logs(logs): file = [] checkpoints = [] for line in logs: file.append(line) checkpoints.append(file.copy()) return sum(len(saved) for saved in checkpoints)
for n in [6]: logs = [f"Zeile {i}" for i in range(1, n + 1)] print(f"{n} Zeilen: {export_logs(logs)} 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.
def newest_first(logs): result = [] for i in range(len(logs) - 1, -1, -1): result.append(logs[i]) return result
def reverse_in_place(logs): left = 0 right = len(logs) - 1 while left < right: logs[left], logs[right] = logs[right], logs[left] left += 1 right -= 1logs = ["09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung"]newest = newest_first(logs)print("Kopie: " + ", ".join(newest))print("Original: " + ", ".join(logs))reverse_in_place(logs)print("Direkt: " + ", ".join(logs))Kopie: 09:07 Zahlung, 09:05 Warenkorb, 09:00 AnmeldungOriginal: 09:00 Anmeldung, 09:05 Warenkorb, 09:07 ZahlungDirekt: 09:07 Zahlung, 09:05 Warenkorb, 09:00 AnmeldungDie 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:
logs = ["09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung"]copy = logs[::-1]logs.reverse()print("Direkt: " + ", ".join(logs))print("Kopie: " + ", ".join(copy))Direkt: 09:07 Zahlung, 09:05 Warenkorb, 09:00 AnmeldungKopie: 09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldunglogs.reverse() kehrt an Ort und Stelle um, und logs[::-1] macht eine Kopie. Jeder Slice logs[a:b] ist eine Kopie: logs[1:] in einer Rekursion kopiert bei jedem Aufruf fast die ganze Liste. reversed(logs) kopiert nicht, es liest nur von hinten.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:
def errors_from(logs, i): if i == len(logs): return 0 here = 1 if logs[i].startswith("ERROR") else 0 return here + errors_from(logs, i + 1)def errors(logs): count = 0 for line in logs: if line.startswith("ERROR"): count += 1 return countsmall = make_logs(500)big = make_logs(1_000_000)print(f"500 Zeilen: {errors_from(small, 0)} Fehler")try: print(f"1000000 Zeilen: {errors_from(big, 0)} Fehler")except RecursionError: print("1000000 Zeilen: RecursionError")print(f"Mit Schleife: {errors(big)} Fehler")500 Zeilen: 5 Fehler1000000 Zeilen: RecursionErrorMit Schleife: 10000 FehlerDie 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).
sys.getrecursionlimit()). Das ist eine Schranke: Der echte Stapel würde für mehr reichen, aber nicht für eine Million.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. Die Grenze wird mit sys.setrecursionlimit angehoben, aber dann kann der echte Stapel des Prozesses ausgehen, und Python stürzt ohne Meldung ab.
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:
def has_duplicate_loops(orders): for i in range(len(orders)): for j in range(i + 1, len(orders)): if orders[i] == orders[j]: return True return Falsedef has_duplicate_set(orders): seen = set() for order in orders: if order in seen: return True seen.add(order) return Falsetoday = [100512, 100513, 100514, 100512]print(has_duplicate_loops(today), has_duplicate_set(today))True TrueBeide 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):
def comparisons_loops(orders): count = 0 for i in range(len(orders)): for j in range(i + 1, len(orders)): count += 1 if orders[i] == orders[j]: return count return count
def checks_set(orders): seen = set() count = 0 for order in orders: count += 1 if order in seen: return count seen.add(order) return countfor n in [10, 1000]: orders = [100000 + i for i in range(n)] print(f"{n} Bestellungen: {comparisons_loops(orders)} Vergleiche mit Schleifen, {checks_set(orders)} Prüfungen mit Set")10 Bestellungen: 45 Vergleiche mit Schleifen, 10 Prüfungen mit Set1000 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 |
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 30–60 Byte (ein Eintrag in der Tabelle und das int-Objekt). „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:
def has_duplicate_set(orders): for order in orders: seen = set() if order in seen: return True seen.add(order) return Falsetoday = [100512, 100513, 100514, 100512]print(has_duplicate_set(today))FalseDie Nummer 100512 kommt zweimal vor, und die Antwort ist „nein“. In welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Das Set wird für jede Bestellung neu angelegt, deshalb ist es beim Prüfen immer leer. Nichts wird gemerkt, und bei jedem Schritt wird Speicher angelegt und weggeworfen. Verschiebe die Zeile vor die Schleife: ein Set für den ganzen Tag.
Ü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 last_lines(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 998Zeile 999Zeile 1000Eine 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.
from collections import deque
def last_lines(logs, k): recent = deque(maxlen=k) for line in logs: recent.append(line) return list(recent)deque(maxlen=k) wirft die älteste Zeile von selbst hinaus, wenn sie voll ist.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