Czytanie kodu pod kątem tempa wzrostu
Przegląd kodu dla poprawności kontra Przegląd kodu dla złożoności
Przegląd kodu dla poprawności wyłapuje błędy logiczne: złe warunki, błędy off-by-one, brakujące sprawdzenia null. Świadomy złożoności przegląd kodu wyłapuje inną klasę defektów: kod, który działa poprawnie przy N = 100, ale rośnie katastrofalnie przy N = 100 000.
Ta lekcja łączy się z głębszym dochodzeniem w kursie unhamming: The Missing Chapter: Algorithmic Complexity obejmuje Big O w kontekście defektów produkcyjnych, & MOAD-0001: The Sedimentary Defect mapuje wzorzec w 60+ ekosystemach oprogramowania.
Dwie heurystyki przeglądu
Zagnieżdżone pętle mnożą złożoność. Dwie zagnieżdżone pętle nad N elementami tworzą O(N²). Trzy tworzą O(N³). Podczas przeglądu: najpierw policz głębokość zagnieżdżenia pętli.
Sekwencyjny kontener wewnątrz gorącej pętli. Każde sprawdzenie .contains(), .includes(), .find(), lub in list wewnątrz pętli kosztuje O(N) na sprawdzenie. W N iteracjach: O(N²) w sumie. Ten wzorzec pojawia się w kodzie produkcyjnym w dziesiątkach ekosystemów — kompilator Haskell GHC, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Ten sam błąd, różne bazy kodów.
Przegląd: find_duplicates
Przejrzyj następującą funkcję Pythona pod kątem złożoności:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: Defekt osadowy
Ten sam defekt, sześćdziesiąt ekosystemów
Wzorzec if x not in list: list.append(x) wewnątrz pętli pojawia się — pojawił się — w kodzie produkcyjnym w dziesiątkach ekosystemów oprogramowania:
- GHC (kompilator Haskell): rozwiązywacz zależności, O(N²) przy N = 50 000 pakietów, budowanie 17 minut
- Python pip: rozwiązywanie konfliktów zależności
- Apache Maven: deduplikacja ścieżki klas
- Rust Cargo: ujednolicenie funkcji
- Kompilator TypeScript: rozwiązywanie modułów
- Godot / silnik gier Redot: przechodzenie grafu węzłów
Żaden z tych zespołów nie popełnił błędu. Pisali poprawny kod przy małych N. N rosnęło. Kod się skrzepł. Wzorzec ma nazwę: MOAD-0001, Defekt osadowy. Osad: poprawny, nieszkodliwy w cienkich warstwach. Z czasem warstwy się gromadzą i twardnieją.
Naprawa
W każdym przypadku: zamień sekwencyjny kontener na kontener mieszający. Jeden wiersz. Zerowa zmiana zachowania przy poprawnych wejściach. Przyspieszenie 100–1000× przy rzeczywistym N.
Naprawa działa, ponieważ dwie operacje muszą pozostać szybkie:
1. Sprawdzenie przynależności: czy ten element był widzany wcześniej?
2. Posortowane wyjście: zwróć elementy w kolejności, w jakiej się pojawiły (czasem wymagane, czasem nie).
Zbiór obsługuje (1) w O(1). Jeśli (2) również ma znaczenie, przechowuj oddzielną listę na wyjście posortowane i zbiór na sprawdzenie przynależności. Dwie struktury danych, każda wykonująca jedno zadanie.
Odpowiadanie recenzentowi
Żądanie ściągnięcia naprawia MOAD-0001 w funkcji przechodzenia grafu projektu. Recenzent komentuje:
> "Zbiory nie zachowują kolejności wstawienia — to zmienia zachowanie."
Wzorzec analizy rozmowy kwalifikacyjnej
Oczekiwany format
Analiza złożoności algorytmicznej pojawia się na rozmowach kwalifikacyjnych w inżynierii oprogramowania. Silna odpowiedź następuje czteroczęściowy wzorzec:
1. Określ bieżącą złożoność — O(?) na czas, O(?) na miejsce.
2. Wyjaśnij dlaczego — zidentyfikuj konkretną konstrukcję odpowiadającą (zagnieżdżona pętla, skan liniowy w pętli, gałęziowanie rekurencyjne).
3. Zaproponuj optymalizację — nazwij zmianę i strukturę danych lub algorytm, który wprowadza.
4. Określ nową złożoność — po naprawie, jaka jest złożoność czasu i miejsca?
Przykład:
Kod: [funkcja, która sprawdza przynależność na liście wewnątrz pętli]
Bieżąca: O(N²) — `item in seen_list` to O(N) na sprawdzenie × N iteracji
Optymalizacja: zamień seen_list na seen_set (zbiór mieszający)
Po: O(N) — sprawdzenie przynależności do zbioru to O(1)Ta umiejętność przenosi się poza rozmowy: świadomy złożoności przegląd kodu, projektowanie architektury, debugowanie wydajności, audyty bezpieczeństwa. Każdy system, który przetwarza dane wejściowe o zmiennym rozmiarze, na tym korzysta.
Ta lekcja łączy się dalej z kursem unhamming, który stosuje ten dokładny wzorzec do dochodzenia defektów produkcyjnych w 60+ projektach open-source.
Rozmowa kwalifikacyjna: analiza has_common_element
Zastosuj czteroczęściowy format rozmowy do tej funkcji:
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