Jak Zbiory Działają Inaczej

Zbiory: Zbudowane dla Pytań o Przynależność

Zbiór przechowuje unikalne elementy przy użyciu techniki zwanej haszowaniem. Gdy dodajesz element, komputer oblicza hasz (numerowy odcisk palca), który mówi mu dokładnie, gdzie przechowywać ten element.

Gdy sprawdzasz przynależność, komputer oblicza ten sam hasz & przeskakuje bezpośrednio do właściwego miejsca. Brak skanowania.

# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique items

Zwróć uwagę na trzy różnice od list:

1. Brak duplikatów. "cat" pojawił się dwa razy na wejściu, ale zbiór zachowuje tylko jedną kopię.

2. Brak gwarantowanego porządku. Zbiór może wydrukować elementy w dowolnym układzie.

3. Brak dostępu do indeksu. Nie możesz napisać pets[0] — zbiory nie mają pozycji.

Kompromis: tracisz porządek & duplikaty. Zyskujesz O(1) testowanie przynależności — sprawdzenie, czy element istnieje, zajmuje tyle samo czasu, czy zbiór ma 5 elementów, czy 5 milionów.

# Membership check — is "fish" in the set?
if "fish" in pets:    # hash("fish") → jump to bucket → found
    print("found!")   # checked exactly 1 spot, not 4

Porównanie Zbioru i Listy

Masz 500 nazwisk uczniów przechowywanych w zbiorze zamiast listy.

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 names
if "Zara" in students:
    print("enrolled")

Porównanie Obok Siebie

Arkusz Ściągania Operacji

Używaj listy, gdy potrzebujesz:

- Elementy w określonym porządku (lista odtwarzająca, przepis, kolejka)

- Dostęp po pozycji (items[3])

- Duplikaty zachowane ("cat" pojawia się 3 razy = 3 koty)

Używaj zbioru, gdy potrzebujesz:

- Szybkie sprawdzenia przynależności ("czy już to widziałem?")

- Automatyczne usuwanie duplikatów

- Brak trosk o porządek

Używaj obu, gdy potrzebujesz porządku I szybkiego wyszukiwania:

seen = set()     # O(1) membership checks
result = []      # preserves insertion order
for item in data:
    if item not in seen:  # O(1) check
        seen.add(item)    # O(1) add
        result.append(item)  # O(1) append
# Total: O(N) — one pass, each step O(1)

Ten wzorzec "zbiór + lista" daje Ci najlepsze z obu: uporządkowane wyniki z szybkim wykrywaniem duplikatów.

Wybierz Właściwą Strukturę

Trzy problemy. Dla każdego, zdecyduj: lista, zbiór, czy oba?

1. Musisz przechowywać playlistę piosenek w porządku, w którym użytkownik je dodał.

2. Musisz szybko sprawdzić, czy nazwa użytkownika została już zajęta.

3. Musisz usunąć duplikaty wiadomości e-mail z listy mailingowej, ale zachować je w porządku rejestracji.

Problem Deduplikacji

Problem: Usuń Duplikaty, Zachowaj Porządek

Otrzymujesz listę rejestracji wiadomości e-mail. Niektóre osoby zarejestrowały się dwa razy. Musisz wysłać jedną wiadomość e-mail na osobę w porządku, w którym najpierw się zarejestrowali.

Próba 1: tylko lista (powolne)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
    if email not in unique:  # O(N) scan of unique list
        unique.append(email)
# Works! But: O(N) check × N items = O(N²)

Ze 100 rejestracjami to robi ~5000 sprawdzeń. Z 10 000 rejestracjami: ~50 000 000 sprawdzeń.

Próba 2: zbiór + lista (szybko)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
    if email not in seen:   # O(1) hash lookup
        seen.add(email)     # O(1) add to set
        unique.append(email) # O(1) append to list
# O(1) check × N items = O(N)

Ten sam wynik. Ten sam porządek. Ale: 10 000 rejestracji teraz wymaga ~10 000 sprawdzeń zamiast ~50 000 000.

Oblicz Przyspieszenie

Wersja tylko dla list działa przy O(N²). Wersja zbiór+lista działa przy O(N).

Masz 10 000 rejestracji wiadomości e-mail do deduplikacji.

Znalezienie Wspólnych Elementów

Problem: Znajdź Elementy na Obu Listach

Masz dwie listy uczniów klas. Musisz znaleźć uczniów zapisanych na obie zajęcia.

Wolne podejście: zagnieżdżone pętle O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iterations
    if student in class_b:     # M scans each time
        both.append(student)
# O(N × M) — each student scanned against all of class_b

Szybkie podejście: konwertuj jedną listę na zbiór O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) to build
both = []
for student in class_a:        # N iterations
    if student in class_b_set: # O(1) each time
        both.append(student)
# O(N + M) — build the set once, check N times at O(1) each

Lub jeszcze prościej używając wbudowanego przecięcia zbiorów Pythona:

both = set(class_a) & set(class_b)  # O(N + M)

Operator & znajduje wszystkie elementy, które pojawiają się w obu zbiorach.

Przepisz na Szybciej

Szkoła ma dwa koła zainteresowań po 200 członków każde. Ten kod znajduje uczniów będących w obu kołach:

chess_club = [...]   # 200 names
art_club = [...]     # 200 names
both_clubs = []
for student in chess_club:
    if student in art_club:
        both_clubs.append(student)

Twoja Rama Decyzyjna

Twoja Rama Decyzyjna do Struktury Danych

Za każdym razem, gdy piszesz kod, który przechowuje kolekcję elementów, zadaj:

1. Czy potrzebuję elementów w porządku? → lista

2. Czy potrzebuję szybkich sprawdzeń przynależności? → zbiór

3. Czy potrzebuję zarówno porządku, jak i szybkich sprawdzeń? → zbiór + lista razem

4. Czy potrzebuję duplikatów? → lista (zbiory usuwają duplikaty)

---

Kluczowy wgląd z tej lekcji: ten sam program, rozwiązujący ten sam problem, może działać 1 000× do 1 000 000× szybciej tylko poprzez wybór właściwej struktury danych. Bez sprytnych sztuczek. Bez skomplikowanej matematyki. Po prostu pytając: jakie operacje wykonuje mój kod najczęściej? Następnie wybierając strukturę, w której te operacje kosztują O(1) zamiast O(N).

Ta lekcja obejmowała listy & zbiory. Istnieją inne struktury danych (słowniki, drzewa, kopce), które rozwiązują inne problemy. Rama decyzyjna pozostaje taka sama: zrozumiej swoje operacje, potem wybierz strukturę, która je robi tanio.

---

Chcesz pójść głębiej? Nasza lekcja Big O obejmuje tempa wzrostu & obliczenia skalowania szczegółowo. Czytaj Big O: Jak Szybko Jest Wystarczająco Szybko?. Nasz kurs unhamming obejmuje rzeczywisty defekt (MOAD-0001), gdzie dokładnie ta naprawa listy-na-zbiór wyprodukowała przyspieszenie 1 000× w oprogramowaniu produkcyjnym. Czytaj Brakujący Rozdział: Złożoność Algorytmiczna.

Debuguj Ten Kod

Uczeń napisał ten kod do zliczania, ile unikalnych słów pojawia się w książce:

words = book.split()           # list of all words
unique_count = 0
checked = []
for word in words:             # N words
    if word not in checked:    # scans checked list
        checked.append(word)
        unique_count += 1
print(unique_count)

Książka ma 100 000 słów.