Hoe Sets Anders Werken

Sets: Gebouwd voor Lidmaatschapsvragen

Een set slaat unieke items op met een techniek genaamd hashing. Wanneer je een item toevoegt, berekent de computer een hash (een numerieke vingerafdruk) die precies vertelt waar het item moet worden opgeslagen.

Wanneer je lidmaatschap controleert, berekent de computer dezelfde hash & springt rechtstreeks naar de juiste plek. Geen scans.

# Een set van huisdieren
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — duplicaten verwijderd
print(len(pets)) # 3 — alleen unieke items

Merk drie verschillen op met lijsten:

1. Geen duplicaten. "cat" verscheen twee keer in de invoer, maar de set behoudt slechts één kopie.

2. Geen gegarandeerde volgorde. De set kan items in willekeurige volgorde afdrukken.

3. Geen index access. Je kunt niet pets[0] schrijven — sets hebben geen posities.

De tradeoff: je verliest volgorde & duplicaten. Je wint O(1) lidmaatschapstesting — controleren of een item bestaat kost dezelfde tijd of de set 5 items of 5 miljoen items heeft.

# Lidmaatschapscontrole — is "fish" in de set?
if "fish" in pets:    # hash("fish") → spring naar bucket → gevonden
    print("found!")   # controleerde precies 1 plek, niet 4

Set vs List Lidmaatschap

Je hebt 500 studentennamen opgeslagen in een set in plaats van een lijst.

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

Zij-aan-zij Vergelijking

Operaties Cheatsheet

Gebruik een lijst als je nodig hebt:

- Items in een specifieke volgorde (een afspeellijst, een recept, een wachtrij)

- Access per positie (items[3])

- Duplicaten behouden ("cat" verschijnt 3 keer = 3 katten)

Gebruik een set als je nodig hebt:

- Snelle lidmaatschapscontroles ("heb ik dit eerder gezien?")

- Automatische verwijdering van duplicaten

- Geen bezorgdheid over volgorde

Gebruik beide als je volgorde EN snelle lookup nodig hebt:

seen = set()     # O(1) lidmaatschapscontroles
result = []      # bewaart invoegvolgorde
for item in data:
    if item not in seen:  # O(1) controle
        seen.add(item)    # O(1) toevoegen
        result.append(item)  # O(1) toevoegen
# Totaal: O(N) — één pass, elke stap O(1)

Dit "set + list" patroon geeft je het beste van beide: geordende resultaten met snelle duplicaatdetectie.

Kies het Juiste Hulpmiddel

Drie problemen. Voor elk, besluit: lijst, set, of beide?

1. Je moet nummers van liedjes opslaan in de volgorde waarin de gebruiker ze toevoegde.

2. Je moet snel controleren of een gebruikersnaam al is gebruikt.

3. Je moet dubbele e-mailadressen uit een mailinglijst verwijderen, maar ze in de volgorde waarin ze zich aanmeldden behouden.

Het Deduplicatieprobleem

Probleem: Verwijder Duplicaten, Behoud Volgorde

Je ontvangt een lijst met e-mailaanmeldingen. Sommige mensen meldden zich twee keer aan. Je moet één e-mail per persoon sturen, in de volgorde waarin ze zich eerst aanmeldden.

Poging 1: alleen lijst (traag)

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 van unieke lijst
        unique.append(email)
# Werkt! Maar: O(N) controle × N items = O(N²)

Met 100 aanmeldingen doet dit ~5.000 controles. Met 10.000 aanmeldingen: ~50.000.000 controles.

Poging 2: set + lijst (snel)

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) toevoegen aan set
        unique.append(email) # O(1) toevoegen aan lijst
# O(1) controle × N items = O(N)

Hetzelfde resultaat. Dezelfde volgorde. Maar: 10.000 aanmeldingen vereisen nu ~10.000 controles in plaats van ~50.000.000.

Bereken de Versnelling

De lijstversie loopt op O(N²). De set+list versie loopt op O(N).

Je hebt 10.000 e-mailaanmeldingen om te dedupliceren.

Gemeenschappelijke Elementen Vinden

Probleem: Vind Items in Beide Lijsten

Je hebt twee klassenlijsten. Je moet studenten vinden die in beide klassen zijn ingeschreven.

Trage aanpak: geneste loops O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iteraties
    if student in class_b:     # M scans elke keer
        both.append(student)
# O(N × M) — elke student wordt gescand tegen alle van class_b

Snelle aanpak: converteer één lijst naar set O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) om te bouwen
both = []
for student in class_a:        # N iteraties
    if student in class_b_set: # O(1) elke keer
        both.append(student)
# O(N + M) — bouw de set eenmaal, controleer N keer op O(1) elk

Of nog eenvoudiger met behulp van Pythons ingebouwde set intersectie:

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

De & operator vindt alle items die in beide sets voorkomen.

Herschrijf voor Snelheid

Een school heeft twee clubs met elk 200 leden. Deze code vindt studenten in beide clubs:

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

Je Besluitvormingsraamwerk

Je Datastructuur Besluitvormingsraamwerk

Elke keer dat je code schrijft die een verzameling items opslaat, vraag jezelf af:

1. Heb ik items in volgorde nodig? → lijst

2. Heb ik snelle lidmaatschapscontroles nodig? → set

3. Heb ik zowel volgorde ALS snelle controles nodig? → set + lijst samen

4. Heb ik duplicaten nodig? → lijst (sets verwijderen duplicaten)

---

Het sleutelinzicht uit deze les: hetzelfde programma, dat hetzelfde probleem oplost, kan 1.000× tot 1.000.000× sneller lopen door simpelweg het juiste datastructuur te kiezen. Geen slimme trucs. Geen ingewikkelde wiskunde. Gewoon vragen: welke operaties doet mijn code het vaakst? Kies dan het hulpmiddel waar die operaties O(1) in plaats van O(N) kosten.

Deze les behandelde lijsten & sets. Andere datastructuren bestaan (dictionaries, trees, heaps) die andere problemen oplossen. Het besluitvormingsraamwerk blijft hetzelfde: begrijp je operaties, kies dan het hulpmiddel dat ze goedkoop maakt.

---

Wil je dieper gaan? Onze Big O les behandelt groeipercentages & schaalberekeningen in detail. Zie Big O: Hoe Snel Is Snel Genoeg?. Onze unhamming course behandelt het echte defect (MOAD-0001) waar deze exacte lijst-naar-set fix een 1.000× versnelling in productiesoftware opleverde. Zie Het Ontbrekende Hoofdstuk: Algoritmische Complexiteit.

Debug Deze Code

Een student schreef deze code om te tellen hoeveel unieke woorden in een boek voorkomen:

words = book.split()           # lijst van alle woorden
unique_count = 0
checked = []
for word in words:             # N woorden
    if word not in checked:    # scant checked lijst
        checked.append(word)
        unique_count += 1
print(unique_count)

Het boek heeft 100.000 woorden.