Code Lesen für Wachstumsfunktionen
Code Review auf Korrektheit vs. Code Review auf Komplexität
Code Review auf Korrektheit findet Logikfehler: falsche Bedingungen, Off-by-One-Fehler, fehlende Null-Checks. Komplexitätsbewusste Code Review findet eine andere Art von Mangel: Code, der bei N = 100 korrekt funktioniert, aber bei N = 100.000 katastrophal wächst.
Diese Lektion verbindet sich mit einer tieferen Untersuchung im unhamming-Kurs: Das fehlende Kapitel: Algorithmic Complexity behandelt Big O im Kontext von Produktionsmängeln, & MOAD-0001: The Sedimentary Defect zeigt das Muster über 60+ Softwareökosysteme.
Zwei Review-Heuristiken
Verschachtelte Schleifen multiplizieren die Komplexität. Zwei verschachtelte Schleifen über N Elemente ergeben O(N²). Drei ergeben O(N³). Bei der Überprüfung: Zählen Sie zunächst die Verschachtelungstiefe der Schleife.
Sequenzieller Container in der inneren Schleife. Jedes .contains(), .includes(), .find() oder in list innerhalb einer Schleife kostet O(N) pro Überprüfung. Über N Iterationen: O(N²) insgesamt. Dieses Muster erscheint in Produktionscode über Dutzende von Ökosystemen — der GHC Haskell-Compiler, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Gleicher Fehler, verschiedene Codebasen.
Überprüfung: find_duplicates
Überprüfen Sie die folgende Python-Funktion auf Komplexität:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: The Sedimentary Defect
Der gleiche Mangel, sechzig Ökosysteme
Das Muster if x not in list: list.append(x) innerhalb einer Schleife erscheint — ist erschienen — in Produktionscode über Dutzende von Softwareökosystemen:
- GHC (Haskell-Compiler): Dependency Resolver, O(N²) bei N = 50.000 Paketen, 17-minütige Builds
- Python pip: Dependency-Konfliktauflösung
- Apache Maven: Classpath-Deduplizierung
- Rust Cargo: Feature-Vereinigung
- TypeScript-Compiler: Modulauflösung
- Godot / Redot Game Engine: Node-Graph-Traversierung
Keines dieser Teams hat einen Fehler gemacht. Sie schrieben korrekten Code bei kleinem N. N wuchs. Der Code verfestigte sich. Das Muster hat einen Namen: MOAD-0001, The Sedimentary Defect. Sediment: korrekt, harmlos in dünnen Schichten. Im Laufe der Zeit sammeln sich die Schichten an und verhärten.
Die Korrektur
In jedem Fall: Ersetzen Sie den sequenziellen Container mit einem Hash-Container. Eine Zeile. Keine Verhaltensänderung bei korrekten Eingaben. 100–1.000× Speedup bei echtem N.
Die Korrektur funktioniert, weil zwei Operationen schnell bleiben müssen:
1. Zugehörigkeitsprüfung: Wurde dieses Element bereits gesehen?
2. Geordnete Ausgabe: Rückgabe von Elementen in der Reihenfolge, in der sie erschienen sind (manchmal erforderlich, manchmal nicht).
Ein Set verarbeitet (1) in O(1). Wenn (2) auch wichtig ist, führen Sie eine separate Liste für geordnete Ausgabe & ein Set für die Zugehörigkeitsprüfung. Zwei Datenstrukturen, jede mit einer Aufgabe.
Antwort an einen Reviewer
Ein Pull Request behebt MOAD-0001 in einer Graph-Traversierungsfunktion des Projekts. Ein Reviewer kommentiert:
> "Sets bewahren keine Einfügungsreihenfolge — dies ändert das Verhalten."
Das Interview-Analysemuster
Das erwartete Format
Analysen zur algorithmischen Komplexität erscheinen in Software-Engineering-Interviews. Eine starke Antwort folgt einem vierteiligen Muster:
1. Geben Sie die aktuelle Komplexität an — O(?) für Zeit, O(?) für Raum.
2. Erklären Sie warum — identifizieren Sie das spezifische Konstrukt, das dafür verantwortlich ist (verschachtelte Schleife, linearer Scan in Schleife, rekursive Verzweigung).
3. Schlagen Sie eine Optimierung vor — nennen Sie die Änderung & die Datenstruktur oder den Algorithmus, den sie einführt.
4. Geben Sie die neue Komplexität an — nach der Korrektur, wie ist die Zeit- & Raumkomplexität?
Beispiel:
Code: [function that checks membership in a list inside a loop]
Current: O(N²) — `item in seen_list` is O(N) per check × N iterations
Optimization: replace seen_list with seen_set (hash set)
After: O(N) — set membership check is O(1)Diese Fähigkeit überträgt sich über Interviews hinaus: komplexitätsbewusste Code Review, Architektur-Design, Performance-Debugging, Sicherheitsprüfungen. Jedes System, das Eingaben variabler Größe verarbeitet, profitiert davon.
Diese Lektion verbindet sich vorwärts mit dem unhamming-Kurs, der dieses exakte Muster auf Produktionsmangel-Untersuchungen über 60+ Open-Source-Projekte anwendet.
Interview: Analysieren von has_common_element
Wenden Sie das vierteilige Interview-Format auf diese Funktion an:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False