Comment les ensembles fonctionnent différemment

Ensembles : conçus pour les questions d'appartenance

Un ensemble (set) stocke des éléments uniques en utilisant une technique appelée hachage. Quand vous ajoutez un élément, l'ordinateur calcule un hachage (une empreinte numérique) qui lui indique exactement où stocker cet élément.

Quand vous vérifiez l'appartenance, l'ordinateur calcule le même hachage & saute directement au bon endroit. Pas de scan.

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

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

Remarquez trois différences par rapport aux listes :

1. Pas de doublons. « cat » apparaissait deux fois dans l'entrée mais l'ensemble en garde une seule copie.

2. Pas d'ordre garanti. L'ensemble pourrait afficher les éléments dans n'importe quel arrangement.

3. Pas d'accès par index. Vous ne pouvez pas écrire pets[0] — les ensembles n'ont pas de positions.

L'échange : vous perdez l'ordre & les doublons. Vous gagnez O(1) test d'appartenance — vérifier si un élément existe prend le même temps qu'il y ait 5 éléments ou 5 millions.

# 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

Ensemble vs Liste d'appartenance

Vous avez 500 noms d'étudiants stockés dans un ensemble au lieu d'une liste.

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

Comparaison côte à côte

Feuille de triche des opérations

Utilisez une liste quand vous avez besoin de :

- Éléments dans un ordre spécifique (une playlist, une recette, une file d'attente)

- Accès par position (items[3])

- Doublons préservés (« cat » apparaît 3 fois = 3 chats)

Utilisez un ensemble quand vous avez besoin de :

- Vérifications d'appartenance rapides (« ai-je déjà vu ceci ? »)

- Suppression automatique des doublons

- Pas besoin de l'ordre

Utilisez les deux quand vous avez besoin d'ordre ET recherche rapide :

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)

Ce motif « ensemble + liste » vous donne le meilleur des deux : résultats ordonnés avec détection rapide des doublons.

Choisir la bonne structure

Trois problèmes. Pour chacun, décidez : liste, ensemble, ou les deux ?

1. Vous devez stocker une playlist de chansons dans l'ordre où l'utilisateur les a ajoutées.

2. Vous devez vérifier rapidement si un nom d'utilisateur a déjà été pris.

3. Vous devez supprimer les e-mails en doublons d'une liste de diffusion mais les garder dans l'ordre où ils se sont inscrits.

Le problème de déduplication

Problème : Supprimer les doublons, garder l'ordre

Vous recevez une liste d'inscriptions par e-mail. Certaines personnes se sont inscrites deux fois. Vous devez envoyer un e-mail par personne, dans l'ordre où elles se sont inscrites en premier.

Tentative 1 : liste uniquement (lent)

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

Avec 100 inscriptions, cela fait ~5 000 vérifications. Avec 10 000 inscriptions : ~50 000 000 vérifications.

Tentative 2 : ensemble + liste (rapide)

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)

Même résultat. Même ordre. Mais : 10 000 inscriptions nécessitent maintenant ~10 000 vérifications au lieu de ~50 000 000.

Calculer l'accélération

La version liste uniquement s'exécute en O(N²). La version ensemble+liste s'exécute en O(N).

Vous avez 10 000 inscriptions par e-mail à dédupliquer.

Trouver les éléments communs

Problème : Trouver les éléments dans les deux listes

Vous avez deux listes de classe. Vous devez trouver les étudiants inscrits dans les deux classes.

Approche lente : boucles imbriquées 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

Approche rapide : convertir une liste en ensemble 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

Ou même plus simple en utilisant l'intersection d'ensemble intégrée de Python :

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

L'opérateur & trouve tous les éléments qui apparaissent dans les deux ensembles.

Réécrire pour la vitesse

Une école a deux clubs avec 200 membres chacun. Ce code trouve les étudiants dans les deux clubs :

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

Votre cadre de décision

Votre cadre de décision de structure de données

Chaque fois que vous écrivez du code qui stocke une collection d'éléments, demandez-vous :

1. Ai-je besoin d'éléments dans l'ordre ? → liste

2. Ai-je besoin de vérifications d'appartenance rapides ? → ensemble

3. Ai-je besoin à la fois d'ordre ET de vérifications rapides ? → ensemble + liste ensemble

4. Ai-je besoin de doublons ? → liste (les ensembles supprimaient les doublons)

---

L'idée clé de cette leçon : le même programme, résolvant le même problème, peut s'exécuter 1 000× à 1 000 000× plus vite juste en choisissant la bonne structure de données. Pas de trucs astucieux. Pas de math compliquée. Juste en demandant : quelles opérations mon code fait-il le plus souvent ? Puis en choisissant la structure où ces opérations coûtent O(1) au lieu de O(N).

Cette leçon couvrait les listes & ensembles. D'autres structures de données existent (dictionnaires, arbres, tas) qui résolvent d'autres problèmes. Le cadre de décision reste le même : comprenez vos opérations, puis choisissez la structure qui les rend bon marché.

---

Voulez-vous approfondir ? Notre leçon Big O couvre les taux de croissance & les calculs d'évolution en détail. Voir Big O : à quelle vitesse c'est assez rapide ?. Notre cours unhamming couvre le défaut du monde réel (MOAD-0001) où ce correctif exact liste-à-ensemble a produit une accélération 1 000× dans le logiciel en production. Voir Le chapitre manquant : complexité algorithmique.

Déboguer ce code

Un étudiant a écrit ce code pour compter combien de mots uniques apparaissent dans un livre :

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)

Le livre a 100 000 mots.