Ensembles

Un set (ensemble) est une collection d'éléments uniques et non ordonnés. Trois superpouvoirs :

1. Déduplication automatique : ajouter le même élément deux fois n'a aucun effet.
2. Test d'appartenance O(1) : x in s est extrêmement rapide, même avec des millions d'éléments (basé sur le hash, comme les dictionnaires).
3. Opérations sur les ensembles : union, intersection, différence, différence symétrique.

Créer un set

vuoto = set()           # ATTENTION : {} est un dict vide, pas un set !
numeri = {1, 2, 3}
da_lista = set([1, 1, 2, 3, 3, 3])   # {1, 2, 3}

Les accolades seules {} créent un dictionnaire vide, pas un ensemble : pour un ensemble vide, vous devez utiliser set().

Modifier un set

s = {1, 2, 3}
s.add(4)         # {1, 2, 3, 4}
s.add(1)         # aucun effet (déjà présent)
s.discard(99)    # supprime si présent, silencieux sinon
s.remove(2)      # supprime ou lève KeyError

Opérations sur les ensembles

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

a | b    # {1, 2, 3, 4, 5, 6}     union
a & b    # {3, 4}                  intersection
a - b    # {1, 2}                  différence (dans a mais pas dans b)
a ^ b    # {1, 2, 5, 6}            différence symétrique (xor)

Il existe également des formes de méthodes (a.union(b), a.intersection(b), …) qui acceptent en outre tout itérable, pas seulement des sets.

Test d'appartenance

parole = {"ciao", "mondo", "python"}
"ciao" in parole       # True   O(1)
"java" not in parole   # True

Pour comparaison : la recherche avec in dans une list est en O(n) et sur des listes longues, elle est beaucoup plus lente.

Frozen set : la version immuable

frozenset({1, 2, 3}) est la version hashable : elle peut être une clé de dictionnaire ou un élément d'un autre ensemble.

Opérations sur les ensembles et performances

Les sets sont implémentés sous forme de tables de hachage, ce qui rend le test d'appartenance (x in mon_ensemble) extrêmement rapide : il s'exécute en temps constant O(1), contrairement aux listes où la recherche prend un temps linéaire O(n). De plus, ils prennent en charge des opérations algébriques comme l'union (|), l'intersection (&) et la différence (-).

À vous de jouer

Exercice de révision

Défi supplémentaire