Läsa kod för tillväxthastigheter
Kodgranskning för korrekthet kontra kodgranskning för komplexitet
Kodgranskning för korrekthet fångar logikfel: felaktiga villkor, off-by-one-index, saknade nollkontroller. Komplexitetsmedveten kodgranskning fångar en annan klass av defekt: kod som fungerar korrekt vid N = 100 men växer katastrofalt vid N = 100 000.
Den här lektionen ansluter till en djupare utredning i unhamming-kursen: The Missing Chapter: Algorithmic Complexity täcker Big O i sammanhanget med produktionsdefekter, & MOAD-0001: The Sedimentary Defect kartlägger mönstret över 60+ mjukvaruekosystem.
Två granskningsheuristiker
Kapslade loopar multiplicerar komplexitet. Två kapslade loopar över N objekt producerar O(N²). Tre producerar O(N³). Vid granskning: räkna först kapslingsdjupet för loopar.
Sekventiell behållare inuti en het loop. Någon .contains()-, .includes()-, .find()- eller in list-kontroll inuti en loop kostar O(N) per kontroll. Över N iterationer: O(N²) totalt. Detta mönster visas i produktionskod på många ekosystem — GHC Haskell-kompilatorn, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Samma misstag, olika kodbasor.
Granskning: find_duplicates
Granska följande Python-funktion för komplexitet:
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
Samma defekt, sextio ekosystem
Mönstret if x not in list: list.append(x) inuti en loop visas — har visats — i produktionskod över många mjukvaruekosystem:
- GHC (Haskell-kompilator): beroendelösare, O(N²) vid N = 50 000 paket, 17-minuters byggen
- Python pip: konfliktlösning för beroenden
- Apache Maven: deduplering av klasssökväg
- Rust Cargo: funktionsförenande
- TypeScript-kompilator: modulupplösning
- Godot / Redot-spelmotorn: nodgraftravers
Inget av dessa team gjorde ett misstag. De skrev korrekt kod vid små N. N växte. Koden härdat. Mönstret har ett namn: MOAD-0001, The Sedimentary Defect. Sediment: korrekt, harmlöst i tunna lager. Med tiden ackumuleras lagren och härdar.
Fixningen
I varje fall: byt den sekventiella behållaren mot en hashbehållare. En rad. Noll beteendeförändring på korrekta inmatningar. 100–1 000 × snabbare vid verklig-världen N.
Fixningen fungerar för att två operationer måste förbli snabba:
1. Medlemskapskontroll: har detta element setts tidigare?
2. Ordnad utgång: returnera element i den ordning de visades (ibland krävs, ibland inte).
En uppsättning hanterar (1) i O(1). Om (2) också är viktigt, behåll en separat lista för ordnad utgång och en uppsättning för medlemskapskontrollen. Två datastrukturer, var och en gör ett jobb.
Svar på en granskare
En pull request fixar MOAD-0001 i ett projekts graftraveringsfunktion. En granskare kommenterar:
> "Uppsättningar bevarar inte insättningsordningen — detta ändrar beteendet."
Intervjuanalysmönstret
Det förväntade formatet
Algoritmisk komplexitetsanalys visas i programvaruteknikintervjuer. Ett starkt svar följer ett fyrdelat mönster:
1. Ange den aktuella komplexiteten — O(?) för tid, O(?) för utrymme.
2. Förklara varför — identifiera den specifika konstruktionen ansvarig (kapslad loop, linjär skanning i loop, rekursiv förgrening).
3. Föreslå en optimering — namnge ändringen och datastrukturen eller algoritmen den introducerar.
4. Ange den nya komplexiteten — efter fixningen, vad är tid & rumslig komplexitet?
Exempel:
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)Den här skickligheten överförs bortom intervjuer: komplexitetsmedveten kodgranskning, arkitekturdesign, prestandafelsökning, säkerhetskontroller. Alla system som behandlar inmatningar av varierande storlek drar nytta av det.
Den här lektionen ansluter framåt till unhamming-kursen, som tillämpar detta exakta mönster på produktionsdefektutredning över 60+ öppen källkodsprojekt.
Intervju: Analysera has_common_element
Tillämpa det fyrdelade intervjuformatet på denna funktion:
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