Czytanie Kodu pod kątem Złożoności

Grep znajduje kandydatów. Czytanie potwierdza je. Gdy otwierasz plik kandydata, czytasz z jednym pytaniem: czy koszt tej operacji rośnie z rozmiarem wejścia?

Dla MOAD-0001, protokół potwierdzenia:

1. Znajdź pętlę zewnętrzną. Co ogranicza liczbę jej iteracji?
2. Znajdź operację wewnętrzną (.contains, .indexOf, 'in'). Przeciwko jakiej strukturze danych działa?
3. Czy ta struktura danych rośnie z tym samym wejściem, które prowadzi pętlę zewnętrzną?
4. Jeśli tak: koszt wynosi O(N²) gdzie N = rozmiar wejścia. Potwierdzony defekt.
5. Jeśli nie: struktura wewnętrzna jest ograniczona (config, enum, mała stała). Fałszywy alarm.

Przejście grafu odwiedzające N węzłów, sprawdzające listę visited na każdym kroku: zarówno pętla jak i struktura wewnętrzna rosną z N. Potwierdzone.

Handler żądania sprawdzający listę dozwolonych IP administratora (5 adresów): lista nigdy nie rośnie z wolumenem żądań. Fałszywy alarm.

Ten sam protokół dotyczy każdego MOADa: zidentyfikuj sterownik zewnętrzny, zidentyfikuj strukturę wewnętrzną, zapytaj czy oba się skalują razem.

Wynik Przypływu: Priorytetyzacja Twoich Ustaleń

Nie wszystkie potwierdzone defekty zasługują na natychmiastową naprawę. MOAD w bibliotece z 10 000 zależnościami downstream ma wyższy wynik przypływu niż ten sam MOAD w prywatnym narzędziu wewnętrznym.

Wynik przypływu = przyspieszenie × stopień-wejścia. Przyspieszenie: o ile szybciej działa naprawa przy typowej skali produkcji? Stopień-wejścia: ile pakietów lub usług downstream automatycznie dziedziczyłoby naprawę, gdy upstream ją merge'a?

Potwierdzony MOAD-0001 w resolver'ze zależności Apache Maven, działający na grafach 50 000 węzłów, z 1000+ wtyczkami Maven downstream, które automatycznie dziedziczą zmiany: wynik przypływu jest bardzo wysoki. Ta naprawa należy do przedniej części twojej kolejki.

Potwierdzony MOAD-0001 w narzędziu CLI dla jednego użytkownika bez zależności: wynik przypływu blisko zera. Warte naprawy, ale nie pilne.

Węzły workaholika vs. żarłoka. Węzeł z wysoką betweenness & wysokim przyspieszeniem to workaholic: obsługuje przepływ krytyczny & opróżni kolejki downstream, gdy zostanie odblokowany. Napraw go tylko po potwierdzeniu możliwości downstream. Węzeł z wysokim stopniem zewnętrznym & niskim przyspieszeniem to żarłok: konsumuje wszystko, co mu podano i nie czuje bólu. Naprawienie workaholika bez przygotowania możliwości downstream tworzy MOAD-0005 (stado galopujące) na skalę infrastruktury.

Skan do Merge: Rurociąg MOADa

Potwierdzony defekt z wysokim wynikiem przypływu przechodzi przez rurociąg. Każdy etap produkuje artefakt. Żaden etap nie jest opcjonalny.

skan    → lista kandydatów (wyjście grep, wyniki analizy statycznej)
bilet   → opis defektu (numer MOADa, lokalizacja, analiza złożoności)
patch   → zmiana kodu (swap struktury danych, adopcja prymitywu)
test    → test jednostkowy (dowód O(1): czas naprawy przy N=100 i N=10 000)
UNDF    → post ujawnienia publicznego (undefect.com, domena publiczna)
ujawnienie → referencja CVE lub CWE, jeśli istotna dla bezpieczeństwa
PR      → upstream pull request z patch + test + link UNDF
merge   → akceptacja opiekuna; naprawa propaguje się poprzez bump wersji

Każdy artefakt karmi następny etap. Patch bez testu nie można zweryfikować. Test bez ujawnienia nie może propagować do innych instancji tego samego wzorca. Ujawnienie bez upstream PR strąca naprawę w forku.

Post MOADa (UNDF) to etap, który większość inżynierów pomija. Naprawiają defekt, wysyłają PR, i uważają się za gotowych. Ale naprawa bez nazwanego posta oznacza, że każdy przyszły inżynier, który napotka ten sam wzorzec, musi niezależnie ponownie odkryć zarówno problem jak i naprawę. Post MOADa zamyka pętlę wiedzy: nazwie wzorzec, pokaże metodę detekcji, & linkuje do patcha. Przyszli badacze znajdują naprawę wyszukując nazwę wzorca.

Patching planety na skalę. Pojedyncza naprawa MOAD-0001 w szeroko używanej bibliotece propaguje do każdego projektu, który ją importuje. Post MOADa zapewnia, że inżynierowie w projektach, którzy nigdy nie uaktualnią tę bibliotekę, nadal uczą się naprawy. Oba ścieżki działają równolegle.

Pisanie Biletu Defektu

Dobry bilet defektu odpowiada na pięć pytań:

1. Gdzie: dokładny plik, klasa, funkcja & zakres linii
2. Co: typ struktury danych & operacja wobec niej
3. Dlaczego: analiza złożoności (O(N²) lub gorzej, z N zdefiniowanym)
4. Wpływ: jakie wejścia wyzwalają zachowanie najgorszego przypadku & na jakiej skali
5. Naprawa: struktura danych lub prymityw do substitucji

Bilet, który odpowiada na wszystkie pięć to samodzielny: opiekun, który nigdy nie czytał twojej analizy, może powielić twoje ustalenia i zweryfikować twoją naprawę. Bilety, które pomijają (3) lub (4) wymagają od opiekuna powtórzenia twojej analizy złożoności zanim mogą merge'ować. To tarcie zmniejsza prawdopodobieństwo merge.

Wiarygodność się sumuje. Pierwszy PR, który zawiera jasny bilet, dobrze ukierunkowany patch, & test benchmarkowy się merge'a. Drugi PR od tego samego autora jest przeglądany z mniejszym tarciem. Trzeci PR jest przeglądany przez opiekuna, który merge'a pierwsze dwa. Reputacja w open source to księga artefaktów: każdy zaakceptowany patch zarabia zaufanie na następny.

Czytanie Rzeczywistego Kandydata

Tutaj jest rzeczywisty kandydat MOAD-0001 w Pythonie. Przeczytaj go i wykonaj protokół triażu.

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

Pytania triażu:

1. Jaka struktura danych to `seen`?
2. Jakie operacje działają wobec niej na linii 6?
3. Czy `seen` rośnie z rozmiarem wejścia?
4. Czy pętla, która prowadzi wywołania rekurencyjne, również rośnie z rozmiarem wejścia?
5. Czy to potwierdzony MOAD-0001 czy fałszywy alarm?

Twoja Naprawa

Potwierdzony defekt z wysokim wynikiem przypływu potrzebuje kompletnej naprawy: patch kodu, test, który udowadnia poprawę, & zarys posta MOADa.

Test musi być testem wydajności, nie testem poprawności. Test poprawności przechodzi przed i po naprawie – to jest punkt; wyjście się nie zmienia. Test wydajności przy dwóch rozmiarach wejścia udowadnia poprawę:

import time

def build_graph(n):
    # n packages, each depending on the previous one
    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')

Przed naprawą, czas upłynięcia rośnie kwadratowo z n. Po naprawie, rośnie liniowo. Wydrukuj obie i załącz liczby w opisie PR.

Zarys posta MOADa obejmuje: nazwę wzorca, substrat (Python dependency resolver), metodę detekcji (grep dla in seen gdzie seen zaczyna się od []), naprawę, & link do twojego PR. Post idzie do undefect.com jako domena publiczna. Przyszli inżynierowie szukający 'Python list membership in loop slow' go znajdą.