Ensembles — une collection sans doublons

Le problème que nous résolvons

Les ventes d'une journée arrivent sous forme de liste, une entrée par vente :

sold = ["pen", "bag", "pen", "ink", "pen"]

La question : combien de produits différents ont été vendus ? len(sold) dit cinq, mais c'est le nombre de ventes. Il y avait trois produits distincts.

Les chapitres précédents savent le faire — créez une liste vide, et pour chaque élément vérifiez if item not in unique: avant d'ajouter. Six lignes, et cela fonctionne.

Mais si la question devient « quels produits ont été vendus à la fois lundi et mardi ? », il faut deux boucles imbriquées. « Lundi seulement ? » — encore une autre. Ces questions sont assez courantes pour avoir leur propre branche des mathématiques, et en Python cette mathématique s'écrit directement.

Un ensemble est le conteneur pour cela : il ne garde aucun doublon, et répond à « dans les deux », « dans l'un mais pas dans l'autre » avec un seul caractère.

À la fin de ce chapitre, vous pourrez

• Créer un ensemble et retirer les doublons d'une liste
• Comparer deux ensembles avec |, &, - et ^
• Expliquer pourquoi {} n'est pas un ensemble vide
• Savoir qu'un ensemble n'a pas d'ordre, et quand cela compte
• Écrire le motif qui supprime les doublons en gardant l'ordre

Prérequis : Dictionnaires — des paires de clé et de valeur.

Un ensemble — une collection sans doublons

sold = ["pen", "bag", "pen", "ink", "pen"]

unique = set(sold)
print(sorted(unique))
print(len(unique))

['bag', 'ink', 'pen']
3

set(...) prend une liste et supprime les doublons. Trois pen n'en font qu'un.

Remarquez sorted() autour de l'affichage, ce qui est volontaire — la raison arrive dans un instant.

Vous pouvez aussi en écrire un directement, avec des accolades :

letters = {"a", "b", "a"}
print(sorted(letters))
print(len(letters))

['a', 'b']
2

Le second "a" a disparu en silence. Pas d'erreur — un ensemble n'a pas de notion de doublon.

{} n'est pas un ensemble vide

not_a_set = {}
real_set = set()

print(type(not_a_set))
print(type(real_set))

<class 'dict'>
<class 'set'>

Les accolades ont d'abord servi aux dictionnaires, donc une {} vide est restée un dictionnaire. Pour un ensemble vide, il faut écrire set().

L'erreur reste muette au début : partez de {}, appelez .add(), et vous obtenez un AttributeError qui donne l'impression que add est le problème.

Il n'y a pas d'ordre

C'est la limitation la plus importante d'un ensemble, et sa propriété la plus mal comprise.

Les éléments d'un ensemble n'ont aucun ordre. Pas d'index et pas de slices :

tags = {"new", "sale"}
print(tags[0])

TypeError: 'set' object is not subscriptable

Et l'ordre que vous voyez à l'affichage n'est pas fiable — lancez le même programme deux fois et il peut différer. C'est pourquoi chaque exemple de ce chapitre trie avant d'afficher : ce que vous voyez en affichant un ensemble directement n'est pas garanti d'être ce que vous verrez la fois suivante.

La façon la plus courte de retirer les doublons d'une liste est list(set(sold)), et elle jette l'ordre original. Quand l'ordre compte, utilisez un ensemble et une liste ensemble :

sold = ["pen", "bag", "pen", "ink", "bag"]
seen = set()
unique = []

for item in sold:
    if item not in seen:
        seen.add(item)
        unique.append(item)

print(unique)

['pen', 'bag', 'ink']

La liste garde l'ordre et l'ensemble se souvient de ce qui a déjà été vu. Cette paire est un motif très courant.

Ajouter et supprimer

tags = {"new"}

tags.add("sale")
tags.add("new")
print(sorted(tags))

tags.discard("gone")
tags.remove("sale")
print(sorted(tags))

['new', 'sale']
['new']

add met une chose dedans — et si elle y est déjà, rien ne se passe et personne ne se plaint. L'append d'une liste aurait fait une seconde copie ; un ensemble non.

La suppression prend deux formes, et la différence est utile :

tags = {"new"}
tags.remove("gone")

KeyError: 'gone'

remove s'arrête quand il ne trouve pas la chose ; discard ne fait rien en silence. Si la chose devrait être là, écrivez remove pour que son absence soit attrapée.

Comparer deux ensembles

C'est là que les ensembles deviennent vraiment utiles :

monday = {"rafi", "ahmed", "bilal"}
tuesday = {"ahmed", "dia"}

print(sorted(monday | tuesday))
print(sorted(monday & tuesday))
print(sorted(monday - tuesday))
print(sorted(monday ^ tuesday))

['ahmed', 'bilal', 'dia', 'rafi']
['ahmed']
['bilal', 'rafi']
['bilal', 'dia', 'rafi']

Quatre symboles, quatre questions :

• | — dans l'un ou l'autre (union). Tous ceux qui sont passés sur les deux jours.
• & — dans les deux (intersection). Ceux qui sont venus les deux jours.
• - — dans le premier et pas dans le second (différence). Ceux qui sont venus lundi seulement.
• ^ — dans exactement un des deux (différence symétrique). Ceux qui sont venus un jour mais pas les deux.

Remarquez que - tient compte de l'ordre : monday - tuesday et tuesday - monday donnent des réponses différentes. Les trois autres se lisent pareil dans les deux sens.

Écrire ces quatre-là avec des boucles demanderait plusieurs lignes chacun, avec de fortes chances d'en rater au moins un.

Ce qui peut y entrer

La même règle que pour les clés de dictionnaire : ce que vous mettez dedans doit être immuable.

s = set()
s.add([1, 2])

TypeError: unhashable type: 'list'

Mot pour mot le même message, pour la même raison — un ensemble utilise aussi le hachage en interne. Les chaînes, les nombres et les tuples conviennent ; les listes et les dictionnaires non.

Un exemple complet

sales.py :

# Which products sold on both days, and which only on one
monday = ["pen", "bag", "pen", "ink"]
tuesday = ["ink", "bottle", "pen", "ink"]

mon = set(monday)
tue = set(tuesday)

print("Monday sold    :", sorted(mon), f"({len(monday)} sales, {len(mon)} products)")
print("Tuesday sold   :", sorted(tue), f"({len(tuesday)} sales, {len(tue)} products)")
print()
print("Either day     :", sorted(mon | tue))
print("Both days      :", sorted(mon & tue))
print("Monday only    :", sorted(mon - tue))
print("Exactly one day:", sorted(mon ^ tue))
print()
print("Was ink sold on Monday?", "ink" in mon)

Monday sold    : ['bag', 'ink', 'pen'] (4 sales, 3 products)
Tuesday sold   : ['bottle', 'ink', 'pen'] (4 sales, 3 products)

Either day     : ['bag', 'bottle', 'ink', 'pen']
Both days      : ['ink', 'pen']
Monday only    : ['bag']
Exactly one day: ['bag', 'bottle']

Was ink sold on Monday? True

Trois choses à remarquer.

Les listes d'origine ont été conservées. len(monday) indique quatre ventes, len(mon) trois produits. Une fois convertie en ensemble, le nombre de ventes est perdu — l'ensemble n'est donc pas un remplacement des données, c'est un outil pour poser un seul type de question dessus.

sorted() avant chaque affichage. Sans lui, l'ordre paraîtrait arbitraire, et pourrait changer d'une exécution à l'autre.

Il écrit "ink" in mon, pas "ink" in monday. Les deux donnent True, mais chercher dans un ensemble est plus rapide que dans une liste — dans une liste, Python compare un élément à la fois ; dans un ensemble, il hache directement jusqu'à l'emplacement. Avec quatre choses c'est sans importance ; avec quarante mille, cela ne l'est pas.

En cas de problème

AttributeError: 'dict' object has no attribute 'add' Le code a écrit s = {} en pensant à un ensemble, mais c'est un dictionnaire vide. Écrivez s = set().

TypeError: 'set' object is not subscriptable Le code a écrit s[0]. Un ensemble n'a pas d'ordre, donc il n'a pas d'index. Si vous avez besoin d'un élément en particulier, vous vouliez probablement une liste ou un dictionnaire ; sinon sorted(s) vous donne une liste.

KeyError: 'gone' remove a été invité à retirer quelque chose que l'ensemble ne contient pas. Si les deux états sont normaux, utilisez discard.

TypeError: unhashable type: 'list' Une tentative de mettre une liste dans un ensemble. Convertissez-la avec tuple(...).

L'ordre est ressorti mélangé après list(set(...)) C'est normal ; les ensembles n'ont pas d'ordre. Si vous en avez besoin, utilisez le motif seen ci-dessus, ou sorted().

J'ai comparé deux ensembles avec == et j'ai obtenu True alors que l'ordre était différent Et à juste titre. Deux ensembles sont égaux quand ils contiennent les mêmes choses — l'ordre n'entre pas en jeu. [1, 2] == [2, 1] est False pour des listes ; {1, 2} == {2, 1} est True pour des ensembles.

À vous de jouer

Écrivez un fichier appelé visitors.py avec trois listes de visiteurs, une par jour, où certains noms apparaissent sur plus d'un jour.

Affichez ensuite :

1. Combien de visites chaque jour, et combien de personnes distinctes
2. Combien de personnes distinctes sur les trois jours
3. Les personnes venues les trois jours
4. Les personnes venues le premier jour seulement
5. Les personnes venues exactement un des deux premiers jours

Puis deux expériences :

• Retirez les doublons de deux façons — list(set(...)) et le motif seen ci-dessus — et affichez les deux résultats côte à côte. Quelle est la différence ?
• Essayez de faire un ensemble vide avec {} et d'y appeler .add(). Quelle erreur revient, et quel type d'objet le message nomme-t-il ?

La seconde est petite, et la voir une fois de vos propres yeux signifie que cette erreur ne vous coûtera plus jamais dix minutes.