Membaca Kode untuk Laju Pertumbuhan
Peninjauan Kode untuk Kebenaran versus Peninjauan Kode untuk Kompleksitas
Peninjauan kode untuk kebenaran menangkap kesalahan logika: kondisi salah, indeks off-by-one, pemeriksaan null yang hilang. Peninjauan kode yang sadar kompleksitas menangkap kelas cacat berbeda: kode yang berfungsi dengan benar pada N = 100 tetapi tumbuh secara katastrofal pada N = 100.000.
Pelajaran ini terhubung ke investigasi yang lebih dalam dalam kursus unhamming: Bab yang Hilang: Kompleksitas Algoritmik mencakup Big O dalam konteks cacat produksi, & MOAD-0001: Cacat Sedimen memetakan pola di seluruh 60+ ekosistem perangkat lunak.
Dua Heuristik Peninjauan
Loop bersarang mengalikan kompleksitas. Dua loop bersarang atas N item menghasilkan O(N²). Tiga menghasilkan O(N³). Saat meninjau: hitung kedalaman bersarang loop terlebih dahulu.
Kontainer sekuensial di dalam loop panas. Pemeriksaan .contains(), .includes(), .find(), atau in list apa pun di dalam loop mengorbankan O(N) per pemeriksaan. Selama N iterasi: O(N²) total. Pola ini muncul dalam kode produksi di seluruh puluhan ekosistem — kompiler GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Kesalahan yang sama, basis kode berbeda.
Tinjauan: find_duplicates
Tinjau fungsi Python berikut untuk kompleksitas:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: Cacat Sedimen
Cacat yang Sama, Enam Puluh Ekosistem
Pola if x not in list: list.append(x) di dalam loop muncul — telah muncul — dalam kode produksi di seluruh puluhan ekosistem perangkat lunak:
- GHC (kompiler Haskell): resolver ketergantungan, O(N²) pada N = 50.000 paket, build 17 menit
- Python pip: resolusi konflik ketergantungan
- Apache Maven: deduplikasi classpath
- Rust Cargo: unifikasi fitur
- Kompiler TypeScript: resolusi modul
- Mesin game Godot / Redot: traversal graf node
Tidak ada tim yang membuat kesalahan. Mereka menulis kode yang benar pada N kecil. N tumbuh. Kode mengeras. Pola memiliki nama: MOAD-0001, Cacat Sedimen. Sedimen: benar, tidak berbahaya dalam lapisan tipis. Seiring waktu, lapisan terakumulasi & mengeras.
Perbaikan
Dalam setiap kasus: ganti kontainer sekuensial dengan kontainer hash. Satu baris. Perubahan perilaku nol pada input yang benar. Kecepatan 100–1.000× pada N dunia nyata.
Perbaikan berfungsi karena dua operasi perlu tetap cepat:
1. Pemeriksaan keanggotaan: apakah elemen ini telah terlihat sebelumnya?
2. Output terurut: kembalikan elemen dalam urutan kemunculannya (kadang-kadang diperlukan, kadang-kadang tidak).
Set menangani (1) dalam O(1). Jika (2) juga penting, pertahankan list terpisah untuk output terurut & set untuk pemeriksaan keanggotaan. Dua struktur data, masing-masing melakukan satu pekerjaan.
Merespons Peninjau
Pull request memperbaiki MOAD-0001 dalam fungsi traversal graf proyek. Seorang peninjau berkomentar:
> "Set tidak mempertahankan urutan penyisipan — ini mengubah perilaku."
Pola Analisis Wawancara
Format yang Diharapkan
Analisis kompleksitas algoritmik muncul dalam wawancara rekayasa perangkat lunak. Jawaban yang kuat mengikuti pola empat bagian:
1. Nyatakan kompleksitas saat ini — O(?) untuk waktu, O(?) untuk ruang.
2. Jelaskan mengapa — identifikasi konstruk spesifik yang bertanggung jawab (loop bersarang, pemindaian linear dalam loop, percabangan rekursif).
3. Usulkan optimasi — namai perubahan & struktur data atau algoritma yang diperkenalkannya.
4. Nyatakan kompleksitas baru — setelah perbaikan, berapa kompleksitas waktu & ruang?
Contoh:
Kode: [fungsi yang memeriksa keanggotaan dalam list di dalam loop]
Saat ini: O(N²) — `item in seen_list` adalah O(N) per pemeriksaan × N iterasi
Optimasi: ganti seen_list dengan seen_set (set hash)
Setelah: O(N) — pemeriksaan keanggotaan set adalah O(1)Keterampilan ini ditransfer di luar wawancara: peninjauan kode yang sadar kompleksitas, desain arsitektur, debugging kinerja, audit keamanan. Sistem apa pun yang memproses input ukuran variabel mendapat manfaat darinya.
Pelajaran ini terhubung ke kursus unhamming, yang menerapkan pola yang tepat ini untuk investigasi cacat produksi di seluruh 60+ proyek sumber terbuka.
Wawancara: Analisis has_common_element
Terapkan format wawancara empat bagian ke fungsi ini:
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