un

guest
1 / ?
back to lessons

Code lesen für Wachstumsraten

Code-Review für Korrektheit vs Code-Review für Komplexität

Code-Review für Korrektheit fängt Logikfehler ein: falsche Bedingungen, off-by-one-Indizes, fehlende Null-Prüfungen. Komplexitätsbewusste Code-Review fängt eine andere Klasse von Fehlern ein: Code, der bei N = 100 richtig funktioniert, aber katastrophisch wächst, wenn N = 100.000 beträgt.

MOAD-0001-Muster: Liste gesehen O(N²) vs. Menge gesehen O(N) - einenzeilige Korrektur


Diese Lektion verbindet eine tiefergehende Untersuchung im unhamming-Kurs: [Das fehlende Kapitel: Algorithmische Komplexität](/en/un/unhamming_algorithmic_complexity) behandelt Big O im Kontext von Produktionsfehlern und [MOAD-0001: Der sedimentäre Defekt](/en/un/unhamming_moad_sedimentary) zeigt das Muster in über 60 Software-Ökosystemen ab.


Zwei Rezensionsheuristiken


Verworfene Schleifen multiplizieren die Komplexität. Zwei in einer Schleife übersertzte Schleifen über N Elemente ergeben O(N²). Drei ergeben O(N³). Wenn man rezensiert: Zähle die Ebenen der Schleifenverwaltung zuerst.


Sequenzieller Container in einer heißen Schleife. Jede .contains(), .includes(), .find() oder in list Prüfung in einer Schleife kostet O(N) pro Prüfung. Über N Iterationen: O(N²) insgesamt. Dieses Muster ist in Produktionscode in Dutzenden von Ökosystemen zu finden - der GHC-Haskell-Kompilierer, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Das gleiche Fehler, verschiedene Codebasen.

Rezension: find_duplicates

Rezension des folgenden Python-Code-Beispiels für Komplexität:


def find_duplicates(items):
    seen = []
    duplicates = []
    for item in items:
        if item in seen:
            duplicates.append(item)
        else:
            seen.append(item)
    return duplicates
Durchführen einer komplexitätsbewussten Code-Review: (a) Was ist die Zeitkomplexität dieser Funktion? (b) Warum? Identifiziere die genaue Zeile, die verantwortlich ist. (c) Erstelle sie in O(N).

MOAD-0001: Der sedimentäre Defekt

Das gleiche Defizit, sechzig Ökosysteme

Das Muster if x not in list: list.append(x) innerhalb einer Schleife ist - hat es auch - in der Produktionscode in Dutzenden Software-Ökosystemen aufgetreten:


- GHC (Haskell-Compiler): Abhängigkeitsausgleich, O(N²) bei N = 50.000 Paketen, 17-minütige Builds

- Python pip: Konfliktlösung bei Abhängigkeiten

- Apache Maven: Entfernung von Klassenpfaden

- Rust Cargo: Vereinigung von Funktionen

- TypeScript-Compiler: Modulauflösung

- Godot / Redot-Spielenginge: Durchsuchung der Knotengraphen


Niemand dieser Teams hat einen Fehler gemacht. Sie haben korrekten Code für kleines N geschrieben. N wuchs. Der Code verfestigte sich. Das Muster hat einen Namen: MOAD-0001, Der sedimentäre Defekt. Sediment: korrekt, schädlich in dünnen Schichten. Mit der Zeit lagern sich die Schichten auf und verfestigen sich.


Die Lösung

In jedem Fall: Ersetzen Sie den sequenziellen Container durch einen Hash-Container. Eine Zeile. Null Verhaltensänderung bei korrekten Eingaben. 100-1.000× Beschleunigung bei realen N.


Die Lösung funktioniert, weil zwei Operationen schnell bleiben müssen:

1. Mitgliedschaftsprüfung: Ist dieses Element bereits gesehen worden?

2. Geordnete Ausgabe: Elemente in der Reihenfolge ihrer Eingabe zurückgeben (manchmal erforderlich, manchmal nicht).


Ein Set handhabt (1) in O(1). Wenn (2) auch wichtig ist, halten Sie einen separaten Liste für geordnete Ausgabe und ein Set für die Mitgliedschaftsprüfung bereit. Zwei Datensätze, jeder mit einer Aufgabe.

Reaktion auf einen Rezensenten

Ein Pull-Request behebt MOAD-0001 in einer Funktion für die Durchsuchung des Graphen in einem Projekt. Ein Rezensent kommentiert:


> "Sets don't preserve insertion order — this changes behavior."

Wie reagieren Sie? Erklären Sie, wann die Bedenken des Rezensenten zutreffen und wann nicht. Vorschlag einer Lösung, die beide Bedenken berücksichtigt, wenn sie sich widersprechen.

Das Interviewanalysemuster

Die erwartete Formatierung

Algorithmische Komplexitätsanalyse tritt in Softwareentwicklungsinterviews auf. Eine starke Antwort folgt einem vierstufigen Muster:


1. Aktuelle Komplexität angeben - O(?) für Zeit, O(?) für Speicherplatz.

2. Erklärung - identifiziere den spezifischen Konstrukt, verantwortlich (eingebettete Schleife, lineare Scan in der Schleife, rekursive Verzweigung).

3. Optimierung vorschlagen - nenne den geänderten Teil und die Datenstruktur oder das Algorithmus, das es einführt.

4. Neue Komplexität angeben - nach der Korrektur, was ist die Zeit- und Speicherplatzkomplexität?


Beispiel:

Code: [Funktion, die die Mitgliedschaft in einer Liste innerhalb einer Schleife prüft]
Aktuell: O(N²) - "item in seen_list" ist O(N) pro Prüfung x N Iterationen
Optimierung: Ersetzen von seen_list durch seen_set (Hashmengen)
Nachher: O(N) - die Abfrage der Mitgliedschaft in einer Menge ist O(1)

Diese Fähigkeit überträgt sich hinaus aus Interviews: Komplexitätsbewusste Code-Übersicht, Architektur-Design, Leistungsdebugging, Sicherheitsaudits. Jedes System, das Eingaben von variabler Größe verarbeitet, profitiert davon.


Dieses Kapitel verbindet sich weiter zum unhamming-Kurs, der dieses exakte Muster auf Produktionsfehlersicherung bei 60+ Open-Source-Projekten anwendet.

Interview: Analyse von has_common_element

Wende das vierstufige Interviewformat 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
Aktuelle Komplexität angeben, erklären, warum, Optimierung vorschlagen, neue Komplexität angeben.