un

guest
1 / ?
back to lessons

Membaca Kode untuk Tingkat Pertumbuhan

Ulasan Kode untuk Kebenaran vs Ulasan Kode untuk Kompleksitas

Ulasan kode untuk kebenaran menangkap kesalahan logika: kondisi yang salah, indeks off-by-one, pengecekan null yang hilang. Ulasan kode dengan kesadaran kompleks menangkap kelas kecacatan yang berbeda: kode yang bekerja dengan benar pada N = 100 tetapi tumbuh kacau total pada N = 100.000.

Polanya MOAD-0001: daftar dilihat O(N²) vs set dilihat O(N) — perbaikan satu baris


Les ini terhubung ke investigasi yang lebih dalam dalam kursus unhamming: [Bab yang Hilang: Kompleksitas Algoritma](/en/un/unhamming_algorithmic_complexity) membahas Big O dalam konteks kerusakan produksi, & [MOAD-0001: Kerusakan Sedimen](/en/un/unhamming_moad_sedimentary) menyebar pola di atas 60+ ekosistem perangkat lunak.


Dua Heuristik Ulasan


Loop bergandengan meningkatkan kompleksitas. Dua loop bergandengan di atas N item menghasilkan O(N²). Tiga menghasilkan O(N³). Ketika mengulas: hitung kedalaman loop bergandengan terlebih dahulu.


Kontainer sekuen di dalam loop panas. Setiap pengecekan .contains(), .includes(), .find(), atau dalam daftar di dalam loop menghabiskan O(N) per pengecekan. Dalam N iterasi: O(N²) total. Pola ini muncul dalam kode produksi di atas puluhan ekosistem — kompiler Haskell GHC, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Kesalahan yang sama, kode basis yang berbeda.

Ulas: cari_duplikat

Ulaslah 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 duplicates
Lakukan ulasan kode dengan kesadaran kompleks: (a) Apa tingkat kompleksitas dari fungsi ini? (b) Mengapa? Identifikasi baris yang tepat bertanggung jawab. (c) Tulis ulangnya menjadi O(N).

MOAD-0001: Defek Sedimen

Defek yang Sama, Enam Pulau Ekosistem

Polanya if x not in list: list.append(x) di dalam loop muncul — telah muncul — di kode produksi di beberapa ekosistem perangkat lunak:


- GHC (kompiler Haskell): resolver ketergantungan, O(N²) di N = 50.000 paket, build 17 menit

- Python pip: penyelesaian konflik ketergantungan

- Apache Maven: deduplikasi classpath

- Rust Cargo: unifikasi fitur

- TypeScript compiler: resolusi modul

- Godot / Redot game engine: perambatan grafik node


Tidak ada tim yang melakukan kesalahan. Mereka menulis kode yang benar di N kecil. N tumbuh. Kode mengeras. Pola memiliki nama: MOAD-0001, The Sedimentary Defect. Sedimen: benar, tidak berbahaya dalam lapisan tipis. Selama waktu, lapisan menumpuk dan mengeras.


Solusi

Dalam setiap kasus: gantilah kontainer sekvensial dengan kontainer hash. Satu baris. Nol perubahan perilaku di input yang benar. 100-1.000× percepatan di N nyata.


Solusi berfungsi karena dua operasi yang harus tetap cepat:

1. Pengecekan anggota: apakah elemen ini telah dilihat sebelumnya?

2. Keluaran terurut: kembalikan elemen-elemen dalam urutan mereka muncul (kadang-kadang diperlukan, kadang-kadang tidak).


Set memperbaiki (1) dalam O(1). Jika (2) juga penting, pertahankan daftar terpisah untuk keluaran terurut dan set untuk pengecekan anggota. Dua struktur data, masing-masing melakukan satu pekerjaan.

Menggunakan Komentar Pengulas

Pull request memperbaiki MOAD-0001 di fungsi perambatan grafik proyek. Seorang pengulas berkomentar:


> "Set tidak mempertahankan urutan pengaturan — ini mengubah perilaku."

Apa yang Anda lakukan? Jelaskan saat kekhawatiran pengulas berlaku, dan saat tidak. Usulkan solusi yang memuaskan kedua kekhawatiran saat mereka saling konflik.

Polanya Wawancara Analisis

Format yang Diharapkan

Analisis kompleksitas algoritma muncul dalam wawancara rekayasa perangkat lunak. Jawaban yang kuat mengikuti pola empat bagian:


1. Satakan kompleksitas saat ini — O(?) untuk waktu, O(?) untuk ruang.

2. Jelaskan mengapa — identifikasi konstruksi khusus yang bertanggung jawab (loop bersarang, skan linear dalam loop, cabang rekursif).

3. Usulkan optimalisasi — namai perubahan dan struktur data atau algoritma yang diperkenalkan.

4. Satakan kompleksitas baru — setelah perbaikan, apa kompleksitas waktu & ruang?


Contoh:

Kode: [fungsi yang memeriksa keanggotaan dalam daftar di dalam loop]
Saat ini: O(N²) — `item in seen_list` adalah O(N) per cek × N iterasi
Optimalisasi: gantikan seen_list dengan seen_set (set hash)
Setelah: O(N) — periksa keanggotaan set adalah O(1)

Keterampilan ini dapat diterapkan di luar wawancara: ulasan kompleksitas kode, desain arsitektur, debug performa, audit keamanan. Setiap sistem yang memproses input variabel ukuran akan menguntungkan dari itu.


Les ini terhubung ke depan ke kursus unhamming, yang menerapkan pola ini pada investigasi kebobolan produksi di atas 60 proyek sumber terbuka.

Wawancara: Analisis has_common_element

Terapkan format wawancara empat bagian ini pada fungsi:


def has_common_element(list_a, list_b):
    for item in list_a:
        for other in list_b:
            jika item == lain:
                kembalikan Benar
    kembalikan Palsu
Satakan kompleksitas saat ini, jelaskan mengapa, usulkan optimalisasi, satakan kompleksitas baru.