Hur mängder fungerar annorlunda

Mängder: Byggda för medlemsfrågor

En mängd lagrar unika objekt med hjälp av en teknik som kallas hashing. När du lägger till ett objekt beräknar datorn en hash (ett numeriskt fingeravtryck) som talar om exakt var objektet ska lagras.

När du kontrollerar medlemskap beräknar datorn samma hash & hoppar direkt till rätt plats. Ingen genomsökning.

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

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

Lägg märke till tre skillnader från listor:

1. Inga dubbletter. "cat" förekom två gånger i inmatningen men mängden behåller bara en kopia.

2. Ingen garanterad ordning. Mängden kan skriva ut objekt i vilken ordning som helst.

3. Ingen indexåtkomst. Du kan inte skriva pets[0] — mängder har inga positioner.

Kompromisspriset: du förlorar ordning & dubbletter. Du får O(1) medlemstestning — att kontrollera om ett objekt finns tar samma tid oavsett om mängden har 5 objekt eller 5 miljoner.

# 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

Mängd vs lista medlemskap

Du har 500 studentnamn lagrade i en mängd istället för en lista.

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

Sida vid sida-jämförelse

Operationer — snabbreferens

Använd en lista när du behöver:

- Objekt i en specifik ordning (en spellista, ett recept, en kö)

- Tillgång genom position (items[3])

- Dubbletter bevarade ("cat" förekommer 3 gånger = 3 katter)

Använd en mängd när du behöver:

- Snabba medlemskapskontrroller ("har jag sett det här förut?")

- Automatisk borttagning av dubbletter

- Ingen omsorg om ordning

Använd båda när du behöver ordning OCH snabb sökning:

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)

Detta "mängd + lista"-mönster ger dig det bästa från båda världarna: ordnade resultat med snabb dubbletkontroll.

Välja rätt struktur

Tre problem. För varje, bestäm: lista, mängd eller båda?

1. Du behöver lagra en spellista över låtar i den ordning användaren lade till dem.

2. Du behöver snabbt kontrollera om ett användarnamn redan har använts.

3. Du behöver ta bort dubbletter från en e-postlista men behålla dem i den ordning de registrerades.

Borttagningsproblem för dubbletter

Problem: Ta bort dubbletter, behålla ordning

Du får en lista med e-postregistreringar. Vissa personer registrerade sig två gånger. Du behöver skicka ett e-postmeddelande per person, i den ordning de först registrerade sig.

Försök 1: bara lista (långsamt)

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²)

Med 100 registreringar gör det ~5 000 kontroller. Med 10 000 registreringar: ~50 000 000 kontroller.

Försök 2: mängd + lista (snabbt)

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)

Samma resultat. Samma ordning. Men: 10 000 registreringar kräver nu ~10 000 kontroller istället för ~50 000 000.

Beräkna snabbheten

Listversionen körs med O(N²). Mängd+lista-versionen körs med O(N).

Du har 10 000 e-postregistreringar att avduplisera.

Hitta gemensamma element

Problem: Hitta objekt i båda listorna

Du har två klasslistor. Du behöver hitta elever registrerade i båda klasserna.

Långsam metod: kapslade loopar 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

Snabb metod: konvertera en lista till mängd 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

Eller ännu enklare med Pythons inbyggda mängdkorsning:

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

&-operatorn hittar alla objekt som förekommer i båda mängderna.

Skriv om för snabbhet

En skola har två klubbar med 200 medlemmar vardera. Den här koden hittar elever i båda klubbarna:

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

Ditt beslutsramverk

Ditt ramverk för datastrukturbeslut

Varje gång du skriver kod som lagrar en samling objekt, fråga:

1. Behöver jag objekt i ordning? → lista

2. Behöver jag snabba medlemskapskontrroller? → mängd

3. Behöver jag både ordning OCH snabba kontroller? → mängd + lista tillsammans

4. Behöver jag dubbletter? → lista (mängder tappar dubbletter)

---

Nyckelinledningen från den här lektionen: samma program, som löser samma problem, kan köra 1 000× till 1 000 000× snabbare bara genom att välja rätt datastruktur. Inga smarta trick. Ingen komplicerad matematik. Bara att fråga: vilka operationer gör min kod oftast? Sedan välja den struktur där de operationerna kostar O(1) istället för O(N).

Den här lektionen täckte listor & mängder. Andra datastrukturer finns (ordböcker, träd, högar) som löser andra problem. Beslutsramverket förblir detsamma: förstå dina operationer, välj sedan den struktur som gör dem billiga.

---

Vill du gå djupare? Vår Big O-lektion täcker tillväxthastigheter & skalningsberäkningar i detalj. Se Big O: Hur snabb är tillräckligt snabb?. Vår unhamming-kurs täcker den verkliga defekten (MOAD-0001) där denna exakta lista-till-mängd-fix producerade en 1 000× snabbhet i produktionsprogramvara. Se The Missing Chapter: Algorithmic Complexity.

Felsöka denna kod

En student skrev denna kod för att räkna hur många unika ord som förekommer i en bok:

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)

Boken har 100 000 ord.