Code lezen voor groeisnelheden
Codebeoordeling voor correctheid vs codebeoordeling voor complexiteit
Codebeoordeling op correctheid vangt logische fouten op: verkeerde voorwaarden, off-by-one-indices, ontbrekende null-controles. Complexiteitsbewuste codebeoordeling vangt een ander soort defect op: code die correct werkt bij N = 100 maar catastrofaal groeit bij N = 100.000.
Deze les verbindt zich met een dieper onderzoek in de unhamming-cursus: Het ontbrekende hoofdstuk: Algoritmische complexiteit behandelt Big O in de context van productiefouten, & MOAD-0001: Het sedimentaire defect brengt het patroon in kaart over 60+ softwareecosystemen.
Twee controleheuristieken
Geneste lussen vermenigvuldigen complexiteit. Twee geneste lussen over N items produceren O(N²). Drie produceren O(N³). Bij beoordeling: tel eerst de diepte van lusgenesting.
Sequentiële container in een hete lus. Elke .contains(), .includes(), .find(), of in list-controle in een lus kost O(N) per controle. Over N iteraties: O(N²) totaal. Dit patroon verschijnt in productiecode in tientallen ecosystemen — de GHC Haskell-compiler, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Dezelfde fout, verschillende codebasissen.
Beoordeling: find_duplicates
Beoordeel de volgende Python-functie op complexiteit:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: Het sedimentaire defect
Dezelfde fout, zestig ecosystemen
Het patroon if x not in list: list.append(x) in een lus verschijnt — is verschenen — in productiecode over tientallen softwareecosystemen:
- GHC (Haskell compiler): afhankelijkheidsresolver, O(N²) bij N = 50.000 pakketten, 17-minuten builds
- Python pip: conflictresolutie afhankelijkheid
- Apache Maven: classpath-deduplicatie
- Rust Cargo: functie-unificatie
- TypeScript compiler: module-resolutie
- Godot / Redot game engine: node-graaftraversal
Geen van deze teams maakte een fout. Ze schreven correct code bij kleine N. N groeide. De code calcificeerde. Het patroon heeft een naam: MOAD-0001, Het sedimentaire defect. Sediment: correct, onschadelijk in dunne lagen. Na verloop van tijd accumuleert de lagen en verharden.
De fix
In elk geval: vervang de sequentiële container met een hash-container. Eén regel. Nul gedragsverandering bij juiste invoer. 100–1.000× versnelling bij real-world N.
De fix werkt omdat twee bewerkingen snel moeten blijven:
1. Lidmaatschapscontrole: is dit element eerder gezien?
2. Georderde uitvoer: retourneer elementen in de volgorde waarin ze verschenen (soms vereist, soms niet).
Een set handelt (1) af in O(1). Als (2) ook belangrijk is, bewaar een aparte lijst voor georderde uitvoer en een set voor de lidmaatschapscontrole. Twee gegevensstructuren, elk doet één taak.
Reageren op een beoordelaar
Een pull request repareert MOAD-0001 in de graftraversal functie van een project. Een beoordelaar merkt op:
> "Sets behouden geen invoegvolgorde — dit verandert gedrag."
Het interview-analysepatroon
De verwachte opmaak
Algoritmische complexiteitsanalyse verschijnt in softwareengineer-interviews. Een sterk antwoord volgt een vierdelig patroon:
1. Geef de huidige complexiteit op — O(?) voor tijd, O(?) voor ruimte.
2. Leg uit waarom — identificeer de specifieke verantwoordelijke constructie (geneste lus, lineaire scan in lus, recursieve vertakking).
3. Stel een optimalisatie voor — noem de verandering en de gegevensstructuur of algoritme die het introduceert.
4. Geef de nieuwe complexiteit op — na de fix, wat is de tijd- & ruimtecomplexiteit?
Voorbeeld:
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)Deze vaardigheid strekt zich uit buiten interviews: complexiteitsbewuste codebeoordeling, architectuurontwerp, prestatiedebugging, beveiligingsaudits. Elk systeem dat invoer van variabele grootte verwerkt, profiteert ervan.
Deze les verbindt zich vooruit naar de unhamming-cursus, die dit exacte patroon toepast op onderzoek naar productiefouten over 60+ open-sourceprojecten.
Interview: analyseer has_common_element
Pas het vierdeelige interview-format toe op deze functie:
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