Karmaşıklık için Kod Okuma

Grep adaylar bulur. Okuma onları doğrular. Aday dosyayı açtığınızda, bir soruyla okursunuz: bu işlemin maliyeti giriş boyutu ile büyür mü?

MOAD-0001 için, doğrulama protokolü:

1. Dış döngüyü bulun. Yineleme sayısını ne sınırlandırır?
2. İç işlemi bulun (.contains, .indexOf, 'in'). Hangi veri yapısı üzerinde çalışır?
3. O veri yapısı, dış döngüyü yönlendiren aynı giriş ile büyür mü?
4. Evetse: maliyet O(N²) olur, burada N = giriş boyutu. Doğrulanmış kusur.
5. Hayırsa: iç yapı sınırlıdır (yapılandırma, enum, küçük sabit). Yanlış pozitif.

N düğümü ziyaret eden, her adımda visited listesini kontrol eden bir grafik geçişi: hem döngü hem de iç veri yapısı N ile büyür. Doğrulanmış.

Bir istek işleyicisi 5 yönetici IP'den oluşan bir izin listesi kontrol eder: izin listesi hiçbir zaman istek hacmi ile büyümez. Yanlış pozitif.

Aynı protokol her MOAD'a uygulanır: dış sürücüyü tanımlayın, iç yapıyı tanımlayın, her ikisinin ölçekle birlikte büyüyüp büyümediğini sorun.

Dalgalanma Puanı: Bulgularınızın Önceliklendirilmesi

Tüm doğrulanmış kusurlar hemen tamir gerektirmez. 10.000 alt kademeli bağımlısı olan bir kütüphanedeki MOAD, özel bir dahili aracı olan aynı MOAD'dan daha yüksek dalgalanma puanına sahiptir.

Dalgalanma puanı = hızlanma × giriş derecesi. Hızlanma: tipik üretim ölçeğinde düzeltme ne kadar daha hızlı çalışır? Giriş derecesi: alt kademeli paket veya hizmet kaç tane, yukarı kademeli birleştirildiğinde değişiklikleri otomatik olarak devralır?

Doğrulanmış MOAD-0001 Apache Maven bağımlılık çözücüsü'nde, 50.000 düğümlük grafikler üzerinde çalışan, Maven eklentileri otomatik olarak başarısız değişiklikleri devralacak 1.000+ ile: dalgalanma puanı çok yüksek. Bu düzeltme sıra başında yer alır.

Doğrulanmış MOAD-0001 hiç bağımlısı olmayan tek kullanıcılı CLI aracında: dalgalanma puanı sıfıra yakın. Tamir değer, ancak acil değil.

Çalışkanlık vs. açgözlü düğümler. Yüksek ara geçişlilik & yüksek hızlanma ile düğüm çalışkandır: kritik akışı işler & kilidinin açılması alt kademeli kuyrukları temizler. Bunu ancak alt kademeli kapasite doğrulandıktan sonra tamir edin. Yüksek çıkış derecesi & düşük hızlanma ile düğüm açgözlüdür: kendisine verilen her şeyi tüketir ve acı duymaz. Çalışkan düğümün kilidini açgözlü düğüne hemen tamir etmeden katma MOAD-0005'i (gürültülü sürü) altyapı ölçeğinde yaratır.

Taramadan Birleştirmeye: Bir MOAD Ardışık Düzeni

Doğrulanmış kusur yüksek dalgalanma puanı ile bir ardışık düzenden geçer. Her aşama yapı meydana getirir. Hiçbir aşama isteğe bağlı değildir.

tarama   → aday listesi (grep çıktısı, statik analiz sonuçları)
bileti   → kusur açıklaması (MOAD numarası, konum, karmaşıklık analizi)
yama     → kod değişikliği (veri yapısı değişimi, ilkel benimseme)
test     → birim testi (O(1) kanıtı: N=100 ve N=10.000 düzeltme zamanı)
UNDF     → genel açıklama yazısı (undefect.com, kamu malı)
açıklama → güvenlikle ilgili CVE veya CWE referansı
PR       → yukarı kademeli çekme isteği yama + test + UNDF bağlantısı ile
birleştir → bakıcı kabulü; düzeltme sürüm yükseltmesi yoluyla yayılır

Her yapı sonraki aşamayı besler. Test olmayan yama doğrulanamaz. Açıklama olmayan test aynı deseni başka örneklere yayılamaz. Yukarı kademeli PR olmayan açıklama düzeltmeyi çatallı kalmış bırakır.

Bir MOAD yazısı (UNDF) çoğu mühendisinin atlayacağı aşamadır. Kusuru tamir ederler, PR gönderirler ve kendilerini bitmiş sayarlar. Ancak adlandırılmış yazı olmayan bir düzeltme, gelecek mühendisinin aynı deseni karşılaştığında sorunu hem de düzeltmeyi bağımsız olarak yeniden keşfetmesi anlamına gelir. Bir MOAD yazısı bilgi döngüsünü kapatır: deseni adlandırır, algılama yöntemini gösterir, & yamaya bağlanır. Gelecek araştırmacılar desenin adı için arama yaparak düzeltmeyi bulurlar.

Gezegen tamiratı ölçekte. Yaygın olarak kullanılan bir kütüphanedeki tek bir MOAD-0001 düzeltmesi, onu yapan her projeye yayılır. Bir MOAD yazısı, o kütüphaneyi asla yükseltmeyecek projeler içindeki mühendislerin de düzeltmeyi öğrenmesini sağlar. Her iki yol paralel olarak çalışır.

Kusur Bileti Yazma

İyi bir kusur bileti beş soruyu yanıtlar:

1. Nerede: kesin dosya, sınıf, işlev ve satır aralığı
2. Ne: veri yapısı türü ve buna karşı işlem
3. Neden: karmaşıklık analizi (O(N²) veya daha kötü, N tanımlı)
4. Etki: en kötü durumu tetikleyen girdiler, hangi ölçekte
5. Düzeltme: ikame edilecek veri yapısı veya ilkel

Tüm beşi yanıtlayan bileti bağımsızdır: hiç analizinizi okumamış bir bakıcı bulguyu yeniden üretip düzeltmeyi doğrulayabilir. (3) veya (4) atlayan biletler bakıcıdan birleştirmeden önce karmaşıklık analizinizi tekrar yapmasını gerektirir. Bu sürtünme birleştirme olasılığını azaltır.

İtibarların bileşimi. İyi bileti, hedeflenmiş yamayı ve benchmark testini içeren ilk PR birleştirilir. İkinci PR aynı yazardan daha az sürtünme ile incelenir. Üçüncü PR, ilk ikisini birleştiren bakıcı tarafından incelenir. Açık kaynakta itibar yapı-yapı ledgeridir: kabul edilen her yama sonraki için güven kazanır.

Gerçek Bir Adayı Okuma

Python'da gerçek MOAD-0001 adayı aşağıda. Okuyun ve triaj protokolünü tamamlayın.

class DependencyResolver:
    def resolve(self, package, resolved=None, seen=None):
        if resolved is None:
            resolved = []
        if seen is None:
            seen = []
        if package in seen:
            return
        seen.append(package)
        for dep in self.registry.get_dependencies(package):
            self.resolve(dep, resolved, seen)
        resolved.append(package)
        return resolved

Triaj soruları:

1. `seen` veri yapısı nedir?
2. 6. satırda hangi işlem buna karşı çalışır?
3. `seen` giriş boyutu ile büyür mü?
4. Özyinelemeli çağrıları yönlendiren döngü giriş boyutu ile büyür mü?
5. Bu doğrulanmış MOAD-0001 veya yanlış pozitif mi?

Sizin Yamınız

Yüksek dalgalanma puanı ile doğrulanmış kusur tam yama gerektirir: kod düzeltmesi, iyileştirmeyi kanıtlayan test, & MOAD yazısı taslağı.

Test doğruluk testi değil, performans testi olmalıdır. Doğruluk testi düzeltmeden önce ve sonra geçer — bu noktadır; çıktı değişmez. İki giriş boyutunda performans testi iyileştirmeyi kanıtlar:

import time

def build_graph(n):
    # n paket, her biri önceki olana bağlı
    return {f'pkg{i}': [f'pkg{i-1}'] if i > 0 else [] for i in range(n)}

for n in [100, 1000, 5000]:
    registry = build_graph(n)
    resolver = DependencyResolver(registry)
    start = time.perf_counter()
    resolver.resolve(f'pkg{n-1}')
    elapsed = time.perf_counter() - start
    print(f'n={n}: {elapsed:.4f}s')

Düzeltmeden önce, geçen zaman n ile ikinci dereceden büyür. Düzeltmeden sonra, doğrusal olarak büyür. Her ikisini yazdırın ve sayıları PR açıklamanıza dahil edin.

MOAD yazı taslağı şunları kapsar: desen adı, alt katman (Python bağımlılık çözücüsü), algılama yöntemi (grep in seen burada seen [] olarak başlar), düzeltme, & PR bağlantısı. Yazı undefect.com'a kamu malı olarak gider. 'Python listesi döngüde üyelik yavaş' arayan gelecek mühendisleri bulurlar.