Wie Mengen anders funktionieren

Mengen: Optimiert für Zugehörigkeitsfragen

Eine Menge speichert eindeutige Elemente mit einer Technik namens Hashing. Wenn du ein Element hinzufügst, berechnet der Computer einen Hash (einen numerischen Fingerabdruck), der ihm genau sagt, wo dieses Element gespeichert wird.

Wenn du die Zugehörigkeit prüfst, berechnet der Computer denselben Hash & springt direkt zur richtigen Stelle. Keine Suche.

# Eine Menge mit Haustieren
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — Duplikate wurden entfernt
print(len(pets)) # 3 — nur eindeutige Elemente

Beachte drei Unterschiede zu Listen:

1. Keine Duplikate. "cat" erschien zweimal in der Eingabe, aber die Menge behält nur eine Kopie.

2. Keine garantierte Reihenfolge. Die Menge könnte Elemente in jeder beliebigen Anordnung drucken.

3. Kein Indexzugriff. Du kannst nicht pets[0] schreiben — Mengen haben keine Positionen.

Der Kompromiss: Du verlierst Reihenfolge & Duplikate. Du gewinnst O(1) Zugehörigkeitsprüfung — die Überprüfung, ob ein Element existiert, dauert gleich lange, ob die Menge 5 Elemente oder 5 Millionen hat.

# Zugehörigkeitsprüfung — ist "fish" in der Menge?
if "fish" in pets:    # hash("fish") → springe zu Bucket → gefunden
    print("found!")   # hat genau 1 Stelle geprüft, nicht 4

Menge vs. Liste Zugehörigkeit

Du hast 500 Schülernamen in einer Menge statt einer Liste gespeichert.

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

Nebeneinander-Vergleich

Operationen Spickzettel

Nutze eine Liste, wenn du brauchst:

- Elemente in einer bestimmten Reihenfolge (eine Wiedergabeliste, ein Rezept, eine Warteschlange)

- Zugriff nach Position (items[3])

- Duplikate bleiben erhalten ("cat" erscheint 3-mal = 3 Katzen)

Nutze eine Menge, wenn du brauchst:

- Schnelle Zugehörigkeitsprüfungen ("habe ich das schon mal gesehen?")

- Automatische Duplikat-Entfernung

- Reihenfolge spielt keine Rolle

Nutze beide, wenn du brauchst Reihenfolge UND schnelle Suche:

seen = set()     # O(1) Zugehörigkeitsprüfungen
result = []      # behält Einfügungsreihenfolge bei
for item in data:
    if item not in seen:  # O(1) Prüfung
        seen.add(item)    # O(1) zur Menge hinzufügen
        result.append(item)  # O(1) zu Liste hinzufügen
# Gesamt: O(N) — ein Durchlauf, jeder Schritt O(1)

Dieses "Menge + Liste"-Muster gibt dir das Beste von beiden: geordnete Ergebnisse mit schneller Duplikat-Erkennung.

Das richtige Werkzeug wählen

Drei Aufgaben. Für jede, entscheide: Liste, Menge, oder beide?

1. Du musst eine Wiedergabeliste von Liedern in der Reihenfolge speichern, wie der Nutzer sie hinzugefügt hat.

2. Du musst schnell überprüfen, ob ein Nutzername bereits vergeben ist.

3. Du musst doppelte E-Mails aus einer Mailingliste entfernen, aber sie in der Reihenfolge behalten, in der sie sich angemeldet haben.

Das Duplikat-Entfernungsproblem

Aufgabe: Duplikate entfernen, Reihenfolge bewahren

Du erhältst eine Liste von E-Mail-Anmeldungen. Einige Personen haben sich zweimal angemeldet. Du musst eine E-Mail pro Person verschicken, in der Reihenfolge, in der sie sich zuerst angemeldet haben.

Versuch 1: Nur Liste (langsam)

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) Durchsuchung der unique Liste
        unique.append(email)
# Funktioniert! Aber: O(N) Prüfung × N Elemente = O(N²)

Bei 100 Anmeldungen macht das ~5000 Prüfungen. Bei 10000 Anmeldungen: ~50000000 Prüfungen.

Versuch 2: Menge + Liste (schnell)

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) zur Menge hinzufügen
        unique.append(email) # O(1) zur Liste hinzufügen
# O(1) Prüfung × N Elemente = O(N)

Gleiches Ergebnis. Gleiche Reihenfolge. Aber: 10000 Anmeldungen erfordern jetzt ~10000 Prüfungen statt ~50000000.

Berechne die Speedup

Die Listenversion läuft mit O(N²). Die Menge+Liste-Version läuft mit O(N).

Du hast 10000 E-Mail-Anmeldungen zum Deduplizieren.

Gemeinsame Elemente finden

Aufgabe: Elemente in beiden Listen finden

Du hast zwei Klassenlisten. Du musst Schüler finden, die in beiden Klassen eingeschrieben sind.

Langsamer Ansatz: Verschachtelte Schleifen O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N Iterationen
    if student in class_b:     # M Durchsuchungen jedes Mal
        both.append(student)
# O(N × M) — jeder Schüler gegen alle class_b durchsucht

Schneller Ansatz: Konvertiere eine Liste zu einer Menge O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) zum Erstellen
both = []
for student in class_a:        # N Iterationen
    if student in class_b_set: # O(1) jedes Mal
        both.append(student)
# O(N + M) — einmal die Menge erstellen, N-mal mit O(1) überprüfen

Oder noch einfacher mit Pythons eingebautem Menge-Schnittpunkt:

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

Der & Operator findet alle Elemente, die in beiden Mengen erscheinen.

Umschreibe für Geschwindigkeit

Eine Schule hat zwei Clubs mit je 200 Mitgliedern. Dieser Code findet Schüler, die in beiden Clubs sind:

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

Dein Entscheidungs-Rahmen

Dein Entscheidungs-Rahmen für Datenstrukturen

Jedes Mal wenn du Code schreibst, der eine Sammlung von Elementen speichert, frage:

1. Brauch ich Elemente in Reihenfolge? → Liste

2. Brauch ich schnelle Zugehörigkeitsprüfungen? → Menge

3. Brauch ich Reihenfolge UND schnelle Prüfungen? → Menge + Liste zusammen

4. Brauch ich Duplikate? → Liste (Mengen entfernen Duplikate)

---

Der Kerngedanke dieser Lektion: Das gleiche Programm, das das gleiche Problem löst, kann 1000× bis 1000000× schneller laufen, nur durch die Wahl der richtigen Datenstruktur. Keine cleveren Tricks. Keine komplizierte Mathematik. Nur fragend: Welche Operationen macht mein Code am häufigsten? Dann wähle die Struktur, bei der diese Operationen O(1) statt O(N) kosten.

Diese Lektion behandelte Listen & Mengen. Andere Datenstrukturen existieren (Wörterbücher, Bäume, Heaps), die andere Probleme lösen. Der Entscheidungs-Rahmen bleibt gleich: Verstehe deine Operationen, dann wähle die Struktur, die sie billig macht.

---

Willst du tiefer gehen? Unsere Big-O Lektion behandelt Wachstumsraten & Skalierungsberechnungen im Detail. Sieh Big O: Wie schnell ist schnell genug?. Unser unhamming Kurs behandelt den echten Defekt (MOAD-0001) wobei genau diese Liste-zu-Menge-Korrektur einen 1000× Speedup in Produktionssoftware erzeugte. Sieh Das fehlende Kapitel: Algorithmische Komplexität.

Debugge diesen Code

Ein Schüler schrieb diesen Code, um zu zählen, wie viele eindeutige Wörter in einem Buch erscheinen:

words = book.split()           # Liste aller Wörter
unique_count = 0
checked = []
for word in words:             # N Wörter
    if word not in checked:    # durchsucht checked Liste
        checked.append(word)
        unique_count += 1
print(unique_count)

Das Buch hat 100000 Wörter.