Lettura del Codice per i Tassi di Crescita
Revisione del Codice per la Correttezza vs Revisione del Codice per la Complessità
La revisione del codice per la correttezza cattura gli errori di logica: condizioni errate, indici off-by-one, controlli null mancanti. La revisione del codice consapevole della complessità cattura una classe diversa di difetto: codice che funziona correttamente con N = 100 ma cresce catastroficamente con N = 100.000.
Questa lezione si connette a un'indagine più profonda nel corso unhamming: Il Capitolo Mancante: Complessità Algoritmica copre Big O nel contesto dei difetti di produzione, & MOAD-0001: Il Difetto Sedimentario mappa lo schema in 60+ ecosistemi software.
Due Euristiche di Revisione
I cicli annidati moltiplicano la complessità. Due cicli annidati su N elementi producono O(N²). Tre producono O(N³). Quando revisioni: conta prima la profondità di annidamento dei cicli.
Un contenitore sequenziale dentro un ciclo critico. Qualsiasi controllo .contains(), .includes(), .find(), o in list dentro un ciclo costa O(N) per ogni controllo. Su N iterazioni: O(N²) totale. Questo schema appare nel codice di produzione in dozzine di ecosistemi — il compilatore GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Stesso errore, codebases diversi.
Revisione: find_duplicates
Revisiona la seguente funzione Python per la complessità:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: Il Difetto Sedimentario
Lo Stesso Difetto, Sessanta Ecosistemi
Lo schema if x not in list: list.append(x) dentro un ciclo appare — è apparso — nel codice di produzione in dozzine di ecosistemi software:
- GHC (compilatore Haskell): risolutore di dipendenze, O(N²) con N = 50.000 pacchetti, compilazioni di 17 minuti
- Python pip: risoluzione dei conflitti di dipendenza
- Apache Maven: deduplica del classpath
- Rust Cargo: unificazione delle features
- Compilatore TypeScript: risoluzione dei moduli
- Motore di gioco Godot / Redot: attraversamento del grafo dei nodi
Nessuno di questi team ha fatto un errore. Hanno scritto codice corretto con N piccolo. N è cresciuto. Il codice si è calcificato. Lo schema ha un nome: MOAD-0001, Il Difetto Sedimentario. Sedimento: corretto, innocuo in strati sottili. Nel tempo, gli strati si accumulano e si induriscono.
La Correzione
In ogni caso: sostituisci il contenitore sequenziale con un contenitore hash. Una riga. Zero cambio di comportamento su input corretti. Accelerazione di 100–1.000× con N nel mondo reale.
La correzione funziona perché due operazioni devono rimanere veloci:
1. Controllo di appartenenza: questo elemento è stato visto prima?
2. Output ordinato: restituisci gli elementi nell'ordine in cui sono apparsi (a volte richiesto, a volte no).
Un set gestisce (1) in O(1). Se (2) è importante, mantieni una lista separata per l'output ordinato e un set per il controllo di appartenenza. Due strutture dati, ciascuna che fa un lavoro.
Rispondere a un Revisore
Una pull request corregge MOAD-0001 nella funzione di attraversamento del grafo di un progetto. Un revisore commenta:
> "I set non preservano l'ordine di inserimento — questo cambia il comportamento."
Il Modello di Analisi nel Colloquio
Il Formato Atteso
L'analisi della complessità algoritmica appare nei colloqui di ingegneria del software. Una risposta forte segue un modello in quattro parti:
1. Dichiara la complessità attuale — O(?) per il tempo, O(?) per lo spazio.
2. Spiega il perché — identifica il costrutto specifico responsabile (ciclo annidato, scansione lineare nel ciclo, branching ricorsivo).
3. Proponi un'ottimizzazione — nomina il cambiamento e la struttura dati o l'algoritmo che introduce.
4. Dichiara la nuova complessità — dopo la correzione, qual è la complessità di tempo e spazio?
Esempio:
Codice: [funzione che controlla l'appartenenza in una lista dentro un ciclo]
Attuale: O(N²) — `item in seen_list` è O(N) per controllo × N iterazioni
Ottimizzazione: sostituisci seen_list con seen_set (set hash)
Dopo: O(N) — il controllo di appartenenza del set è O(1)Questa abilità si trasferisce oltre i colloqui: revisione del codice consapevole della complessità, progettazione dell'architettura, debugging della performance, audit di sicurezza. Qualsiasi sistema che elabora input di dimensione variabile ne beneficia.
Questa lezione si connette in avanti al corso unhamming, che applica questo esatto modello all'indagine dei difetti di produzione in 60+ progetti open-source.
Colloquio: Analizza has_common_element
Applica il formato colloquio in quattro parti a questa funzione:
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