Büyüme Oranları için Kod Okuma
Doğruluk için Kod İncelemesi vs Karmaşıklık için Kod İncelemesi
Doğruluk için kod incelemesi mantık hatalarını yakalar: yanlış koşullar, kapalı-bir indeks dizinler, eksik null kontrolleri. Karmaşıklık-bilincli kod incelemesi farklı bir kusur sınıfını yakalar: N = 100'de doğru çalışan ancak N = 100.000'de felaket ölçüde büyüyen kod.
Bu ders, unhamming kursunda daha derin bir araştırmaya bağlanır: Eksik Bölüm: Algoritmik Karmaşıklık karmaşıklığı üretim kusurları bağlamında kapsar ve MOAD-0001: Sedimanter Kusur deseni 60+ yazılım ekosistemi arasında eşler.
İki İnceleme Buluşsal Yöntemi
İç içe döngüler karmaşıklığı çarpar. N öğe üzerinde iki iç içe döngü O(N²) üretir. Üç O(N³) üretir. İncelemede: önce döngü iç içe geçme derinliğini sayın.
Sıcak döngü içinde sıralı kapsayıcı. Bir döngü içinde herhangi bir .contains(), .includes(), .find() veya in list kontrolü kontrol başına O(N) maliyeti vardır. N yineleme üzerinden: toplam O(N²). Bu desen düzinelerce ekosistem arasında üretim kodunda görünür — GHC Haskell derleyicisi, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Aynı hata, farklı kod tabanları.
İnceleme: find_duplicates
Aşağıdaki Python işlevini karmaşıklık açısından gözden geçirin:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: Sedimanter Kusur
Aynı Kusur, Altmış Ekosistem
Desen if x not in list: list.append(x) bir döngü içinde üretim kodu arasında görünür — görünmüştür — düzinelerce yazılım ekosistemi arasında:
- GHC (Haskell derleyicisi): bağımlılık çözücüsü, O(N²) N = 50.000 paket'te, 17 dakikalık derleme
- Python pip: bağımlılık çatışması çözümü
- Apache Maven: sınıf yolu çoğaltması kaldırma
- Rust Cargo: özellik birleştirme
- TypeScript derleyicisi: modül çözümü
- Godot / Redot oyun motoru: düğüm grafiği geçişi
Bu ekiplerin hiçbiri hata yapmadı. Küçük N'de doğru kod yazdılar. N büyüdü. Kod katılaştı. Desen bir ada sahiptir: MOAD-0001, Sedimanter Kusur. Kum taşı: ince tabakalarda doğru, zararsız. Zaman içinde tabakaların birikimi ve sertleşmesi.
Düzeltme
Her durumda: sıralı kapsayıcıyı hash kapsayıcısı ile değiştirin. Bir satır. Doğru girdilerde sıfır davranış değişikliği. Gerçek dünya N'de 100–1.000× hızlanma.
Düzeltme işe yarar çünkü iki işlem hızlı kalmak zorundadır:
1. Üyelik kontrolü: bu öğe daha önce görüldü mü?
2. Sıralı çıktı: öğeleri göründükleri sırada döndür (bazen gerekli, bazen değil).
Bir küme (1)'i O(1)'de ele alır. (2) de önemliyse, sıralı çıktı için ayrı bir liste ve üyelik kontrolü için ayrı bir küme tutun. İki veri yapısı, her biri bir işi yapıyor.
Gözden Geçirene Yanıt Verme
Bir pull request bir projenin grafik geçişi işlevinde MOAD-0001'i düzeltir. Bir gözden geçiren şunları yorum yapar:
> "Kümeler ekleme sırasını korumaz — bu davranışı değiştirir."
Mülakat Analiz Deseni
Beklenen Format
Algoritmik karmaşıklık analizi yazılım mühendisliği mülakatlarında görünür. Güçlü bir yanıt dört kısımlı deseni takip eder:
1. Geçerli karmaşıklığı belirtin — zaman için O(?), alan için O(?).
2. Neden açıklayınız — sorumlu olan belirli yapıyı belirleyin (iç içe döngü, döngü içinde doğrusal tarama, özyinelemeli dallanma).
3. Optimizasyon öneriniz — değişikliği adlandırın ve getirdiği veri yapısını veya algoritmayı adlandırın.
4. Yeni karmaşıklığı belirtin — düzeltmeden sonra, zaman ve alan karmaşıklığı nedir?
Örnek:
Kod: [döngü içinde bir listede üyeliği kontrol eden işlev]
Geçerli: O(N²) — `item in seen_list` kontrol başına O(N) × N yineleme
Optimizasyon: seen_list'i seen_set (hash kümesi) ile değiştirin
Sonra: O(N) — kümede üyelik kontrolü O(1)'dirBu beceri mülakatların ötesine aktarılır: karmaşıklık-bilincli kod incelemesi, mimari tasarımı, performans hata ayıklaması, güvenlik denetimi. Değişken boyutlu girdileri işleyen herhangi bir sistem bundan yararlanır.
Bu ders unhamming kursuna doğru aktarılır ve bu tam deseni 60+ açık kaynak projesi arasında üretim kusuru araştırmasına uygular.
Mülakat: has_common_element'i Analiz Edin
Dört kısımlı mülakat biçimini bu işleve uygulayın:
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