un

guest
1 / ?
back to lessons

Czytanie Kodu dla Stopy Rozwoju

Przegląd Kodu dla Poprawności vs Przegląd Kodu dla Złożoności

Przegląd kodu dla poprawności wykrywa błędy logiki: błędne warunki, błędy indeksów o jeden za mało, brakujące sprawdzanie null. Przegląd kodu uwzględniający złożoność wykrywa inny rodzaj defektów: kod, który działa poprawnie dla N = 100, ale rośnie katastrofalnie dla N = 100,000.

Wzór MOAD-0001: lista zobowiązań O(N²) vs zestaw O(N) — jedno-wierszowa poprawka


Ta lekcja łączy się z głębszą investigacją w kursie unhamming: [Odkryty Rozdział: Złożoność Algorytmiczna](/en/un/unhamming_algorithmic_complexity) przedstawia Big O w kontekście defektów produkcyjnych, a [MOAD-0001: Sedimentary Defect](/en/un/unhamming_moad_sedimentary) przedstawia wzór w 60+ ekosystemach oprogramowania.


Dwa Heurystyki Przeglądu


Pętle zagnieżdżone mnożą złożoność. Dwie pętli zagnieżdżone nad N elementami wykonywują O(N²). Trzy wykonywają O(N³). Podczas przeglądu: najpierw policz głębokość zagnieżdżenia pętli.


Sequencyjny kontener wewnętrzny w gorącej pętli. Każde .contains(), .includes(), .find() lub w liście sprawdzenie wewnętrzne w pętli kosztuje O(N). W N iteracjach: O(N²) łącznie. Ten wzór pojawia się w kodzie produkcyjnym w dziesiątkach ekosystemów — kompilatora GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Ten sam błąd, różne kodów.

Przegląd: znalezienie powtórzeń

Przeglądaj 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 duplicates
Wykonaj przegląd kodu uwzględniający złożoność: (a) Jak jest złożoność czasowa tej funkcji? (b) Dlaczego? Zidentyfikuj dokładną linię odpowiedzialną. (c) Napraw ją, aby była O(N).

MOAD-0001: Wada Sedimentary

Ta sama wada, sześćdziesiąt ekosystemów

Wzorzec if x not in list: list.append(x) wewnętrzny w pętli pojawia się — pojawił się — w kodzie produkcyjnym w dziesiątkach ekosystemów oprogramowania:


- GHC (kompilator Haskell): rozstrzygacz zależności, O(N²) przy N = 50 000 pakietów, 17-minutowe kompilacje

- Python pip: rozwiązywanie konfliktów zależności

- Apache Maven: deduplikacja ścieżki klas

- Rust Cargo: łączenie cech

- Kompilator TypeScript: rozwiązywanie modułów

- Silnik gier Godot / Redot: przetwarzanie grafu węzłów


Nie wyrzucili żadnego błędu. Pisać poprawny kod na małych N. N wzrosło. Kod zwapniał. Wzorzec ma nazwę: MOAD-0001, The Sedimentary Defect. Sedyment: poprawny, bezpieczny w cienkich warstwach. Z czasem warstwy nagrzewają się i twardnieją.


Naprawa

W każdym przypadku: zastąp sekwencyjny kontener kontenerem haszującym. Jedna linia. Zero zmian zachowania na poprawnych wejściach. 100-1,000× przyspieszenie na rzeczywistych N.


Naprawa działa, ponieważ dwie operacje muszą być szybkie:

1. Sprawdzanie przynależności: czy ten element był już widziany?

2. Wydrukowane w kolejności: zwróć elementy w kolejności, w jakiej pojawiły się (czasami wymagane, czasami nie).


Zbiór obsługuje (1) w O(1). Jeśli (2) również ma znaczenie, zachowaj osobny listę dla wydruku w kolejności oraz zbiór dla sprawdzania przynależności. Dwa struktury danych, każda wykonując jedno zadanie.

Odpowiedź na Przykład Recenzenta

Pull request naprawia MOAD-0001 w funkcji przetwarzania grafu projektu. Recenzent komentuje:


> "Ustawy nie zachowują kolejności wprowadzenia - to zmienia zachowanie."

Jak odpowiadać? Wyjaśnij, kiedy obawa recenzenta ma zastosowanie, a kiedy nie. Zaproponuj rozwiązanie, które spełnia obie obawy, gdy się konkurują.

Modyfikacja wywiadu: analiza

Oczekiwany format

Analiza złożoności algorytmicznej pojawia się w wywiadach z inżynierami oprogramowania. Silna odpowiedź przestrzega czterech etapów:


1. Stanąć na bieżącej złożoności - O(?) dla czasu, O(?) dla przestrzeni.

2. Wyjaśnij, dlaczego - zidentyfikuj konkretny konstrukcję odpowiedzialną (zagnieżdżony pętla, liniowe przeskanowanie w pętli, rozgałęzienia rekursywne).

3. Zaproponuj optymalizację - nazwij zmianę i wprowadzenie struktury danych lub algorytmu.

4. Stanąć na nowej złożoności - co po poprawce, jakie są złożoności czasu i przestrzeni?


Przykład:

Kod: [funkcja sprawdzająca przynależność do listy wewnętrznej pętli]
Obecnie: O(N²) - `item in seen_list` jest O(N) na sprawdzenie × N iteracji
Optymalizacja: zastąpić seen_list seen_set (zbior hash)
Po tym: O(N) - sprawdzanie przynależności do zbioru jest O(1)

Umiejętność ta przenosi się poza wywiady: przeglądanie optymalizacji złożoności, projektowanie architektury, debugowanie wydajności, przeglądy bezpieczeństwa. Każde system, który przetwarza wejścia o różnej długości korzysta z tego.


Ten lekcja łączy się z przyszłym kursem unhamming, który stosuje ten sam wzorzec do śledzenia wad w produkcji w 60+ projektów open-source.

Wywiad: Analizuj has_common_element

Zastosuj czterechetapowy wzorzec wywiadu 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
Stanąć na bieżącej złożoności, wyjaśnić, dlaczego, zaproponować optymalizację, stanąć na nowej złożoności.