un

guest
1 / ?
back to lessons

Okuma için Büyüme Oranları

Kod İncelemesi için Doğruluk vs. Karmaşıklık için Kod İncelemesi

Doğruluk için kod incelemesi: yanlış koşullar, off-by-one dizeler, eksik null kontrolleri yakalar. Karmaşıklık bilincli kod incelemesi, N = 100'de doğru çalışmasına rağmen, N = 100.000'de katasstrofik olarak büyüyen bir kusur sınıfı yakalar.

MOAD-0001 Kalıpla: list seen O(N²) vs set seen O(N) - tek satırlık düzelme


Bu ders, daha derli bir araştırma olan unhamming kursunda bağlanır: [Algoritmik Karmaşıklık: Kayıp Bölüm](/en/un/unhamming_algorithmic_complexity) Big O'yu üretim kusurları bağlamında sunar ve [MOAD-0001: Sedimanter Kusur](/en/un/unhamming_moad_sedimentary) kalıntıyı 60'dan fazla yazılım ekosistemini üzerinden haritalar.


İki İnceleme Heuristik


Yan yana döngüler karmaşıklığı katlar. İki yan yana döngü N öğe üzerinde O(N²) üretir. Üçü O(N³) üretir. İnceleme yaparken: döngü katman derinliğini öncelikle sayın.


Sıcı döngü içinde dizi eleman. Bir döngü içinde .contains(), .includes(), .find() veya list içinde kontrol etmezse, N kontrolü için O(N) maliyeti vardır. N iterasyonu üzerinde: O(N²) toplam. Bu kalıp, GHC Haskell derleyici, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot gibi onlarca ekosistemde üretim kodunda görülür - aynı hata, farklı kodbase'ler.

İnceleme: find_duplicates

Karmaşıklık açısından şu Python fonksiyonunu inceleyin:


def find_duplicates(items):
    seen = []
    duplicates = []
    for item in items:
        if item in seen:
            duplicates.append(item)
        else:
            seen.append(item)
    return duplicates
Karmaşıklık bilincli kod incelemesi gerçekleştirin: (a) Bu fonksiyonun zaman karmaşıklığı nedir? (b) Neden? Düzenli hattı tam olarak belirleyin. (c) O(N) yapısına getirin.

MOAD-0001: Katı Hareket Defect

Aynı Hata, Altmış Ekosistem

Döngü içinde if x not in list: list.append(x) kalıbı — olmuş — gerçek kodda birçok yazılım ekosistemlerinde görünüyor:


- GHC (Haskell derleyicisi): bağımlılık çözücüsü, O(N²) N = 50.000 pakette, 17 dakikalık build süreleri

- Python pip: bağımlılık çelişkisel çözme

- Apache Maven: classpath tekrarsızlaştırma

- Rust Cargo: özellik birleştirme

- TypeScript derleyici: modül çözümü

- Godot / Redot oyun motoru: düğüm grafiği gezintisi


Bu ekiblerin hiçbiri hata yapmadı. Küçük N'de doğru kod yazdılar. N büyüdü. Kod kalsiyifleşti. Kalıp bir adı var: MOAD-0001, Katı Hareket Defect. Katı: doğru, küçük katlar halinde zararsız. Zamanla katlar birikerek sertleşir.


Çözüm

Her durumda: dizi yerine bir hash konteynını kullanın. Bir satır. Doğru girişlerde davranış değişikliği. Gerçek-world N'de 100-1000 kat hızlanma.


Çözüm, iki işlemi hızlı tutmak zorunda olan iki işlemden dolayı çalışır:

1. Üyelik kontrolü: Bu öğe daha önce görüldü mü?

2. Sıralı çıktı: öğeleri görünüş sırasına göre döndürün (bazen gerekebilir, bazen değil).


Bir set, (1)i O(1) sürede gerçekleştirir. (2) de önemliyse, sıralı çıktıya yönelik ayrı bir liste tutun ve üyelik kontrolü için bir set kullanın. Herhangi bir işlemdir, her biri bir görevi yerine getirir.

Bir İnceleyicinin Yanıtlanması

Bir pull request, MOAD-0001'i bir proje grafik gezinti fonksiyonunda düzeltir. İnceleyici yorum yapar:


> "Setler sıralamayı koruma — bu, davranış değiştirir."

Ne tür bir yanıt verirdiniz? Küçük N'de geçerli olduğu ve olmadığı zaman inceleyicinin endişesini açıklayın. Çatıştığında hem endişeleri karşılayacak bir çözüm önerin.

Röportaj Analiz Deseni

Beklenen Format

Algoritmik karmaşıklık analiz, yazılım mühendisliği röportajlarında görülür. Güçlü bir yanıt, dört bölümden oluşan bir desene uymalıdır:


1. Güncel karmaşıklığı belirtin - Süre için O(?) zaman, alan için O(?) zaman.

2. Nedeni açıklayın - Belirli bir yapıyı (dahili döngü, döngü içinde lineer tarama, geri dönük dallanma) sorumlu olarak tanımlayın.

3. Optimizasyonu önerin - Değişikliği ve onu tanıtan veri yapısı veya algoritma adını belirtin.

4. Yeni karmaşıklığı belirtin - Düzeltilmiş haliyle zaman ve alan karmaşıklığı nedir?


Örnek:

Kod: [listede döngü içinde üyeyi kontrol eden fonksiyon]
Şu an: O(N²) - `item in seen_list` O(N) her kontrol için × N döngü
Optimizasyon: seen_list'yi seen_set (hash set) ile değiştirin
Sonrasında: O(N) - set üyelik kontrolü O(1)

Bu beceri, karmaşıklık bilincli kod incelemesi, mimari tasarım, performans hatalarını bulma, güvenlik denetimi vb. dışında da geçerlidir. Girdi boyutu değişken olan herhangi bir sistem bu faydadan yararlanır.


Bu ders, bu exact deseni 60+ açık kaynak proje üzerinde üretim arıza araştırmasına uygular ve ileriye doğru Unhamming kursu ile bağlantılıdır.

Röportaj: has_common_element Analiz

Bu fonksiyona da dört bölümden oluşan röportaj formatını 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
Güncel karmaşıklığı belirtin, nedenini açıklayın, optimizasyonu önerin, yeni karmaşıklığı belirtin.