Chapitre 13: Les ensembles (sets et frozensets)

Aujourd’hui, nous allons aborder une notion moins connue du langage Python, à savoir les ensembles (sets et frozensets).

Définition

Un ensemble est une collection non ordonnée d’objets uniques et immuables (en profondeur). La tentative d’insertion d’un doublon n’a absolument aucun effet et ne lève même pas d’exception. En revanche, la présence d’un élément modifiable tel qu’une liste par exemple lève l’exception ci-dessous:

TypeError: unhashable type: ‘list’

Puisqu’il s’agit d’un ensemble d’objets non ordonné, un set est idéal pour effectuer un test d’appartenance et je vais vous le prouver.

On trouve deux types d’ensembles:

  • Le set qui est un objet modifiable
  • le frozenset qui est un objet immuable (le mot anglais frozen signifie gelé en français)

Déclarer un set

Il y a deux manières de déclarer un set.

  • En utilisant des accolades.
s = { "Hervé", "Jacky", "Didier", "Toufik"}
print(s)

Résultat: {‘Didier’, ‘Toufik’, ‘Hervé’, ‘Jacky’}.

Notez bien qu’il s’agit d’un ensemble non ordonné ce qui explique que print() retourne les éléments dans un ordre aléatoire.

  • En transformant une liste en set grâce au constructeur set().
s2 = set(["Geneviève", "Geneviève", (1,2,3), 7.56])
print(s2)

Résultat: {7.56, ‘Geneviève’, (1, 2, 3)}

Notez que j’ai déclaré mon set avec un doublon (« Geneviève »). Comme je l’ai déjà précisé dans l’introduction, celui-ci n’est pas pris en compte et ne lève même pas d’exception. Le set est une collection d’objets uniques.

  • Il n’est pas possible de déclarer un ensemble vide avec la première méthode. Cela créé un dictionnaire.
 s = {}
print(type(s))

Résultat : <class ‘dict’>

  • Pour créer un ensemble vide, pas d’autre choix que d’utiliser la deuxième méthode.
 s = set()
print(type(s))

Résultat: <class ‘set’>

Pourquoi le set est préférable à la liste pour effectuer un test d’appartenance?

Une liste est une séquence. Elle contient des objets indicés. Lorsqu’on fait un test d’appartenance sur une liste, cette dernière est parcourue de l’indice 0 jusqu’à l’indice de l’objet recherché. Si la liste ne contient que dix éléments, le test d’appartenance est rapide mais si la liste contient cinquante millions d’éléments, la vitesse d’exécution s’en ressent. J’ai fait une courte vidéo pour vous montrer la différence entre une liste et un set contenant cinquante millions d’éléments.

Le set étant une implémentation de table de hachage, la vitesse d’exécution d’un test d’appartenance est identique quel que soit le nombre d’éléments qu’il contient.

Voici les trois exemples de code que j’ai exécutés dans la vidéo.

  • Test d’appartenance sur les premiers éléments d’une liste
l = [i for i in range(50000000)]
for i in range(2, 8):
    if i in l:
        print(i, "appartient à la liste")
  • Test d’appartenance sur les derniers éléments d’une liste
l = [i for i in range(50000000)]
for i in range(49999990, 49999999):
    if i in l:
        print(i, "appartient à la liste")
  • Test d’appartenance sur des éléments présents dans un set
s = {i for i in range(50000000)}
for i in range(49999990, 49999999):
    if i in s:
        print(i, "appartient au set")

Aperçu de quelques méthodes associées aux sets

  • Ajouter un élément avec set.add()
s = {"Kevin", "Kilian", "Morgane"}
s.add("Gustave")
print(s)

Résultat: {‘Morgane’, ‘Kilian’, ‘Gustave’, ‘Kevin’}

  • Ajouter tous les éléments d’un autre set avec set.update()
s = {"Kevin", "Kilian", "Morgane"}
s2 = {1, 2, 3}
s.update(s2)
print("s =", s)
print("s2 =", s2)

s = {1, 2, 3, ‘Kilian’, ‘Kevin’, ‘Morgane’}
s2 = {1, 2, 3}

Comme vous pouvez le constater, cette méthode rajoute les éléments de l’ensemble s2 dans l’ensemble s sans pour autant vider l’ensemble s2.

  • Supprimer un élément avec set.remove() et set.discard()
s = {"Kevin", "Kilian", "Morgane", "Gustave"}
s.remove("Kevin")
print(s)

Résultat: {‘Kilian’, ‘Morgane’, ‘Gustave’}

Attention! Avec set.remove(), Python lève une exception si vous essayez d’enlever un élément qui n’appartient pas au set.

s = {"Kevin", "Kilian", "Morgane", "Gustave"}
s.remove("Robert")
print(s)

KeyError: ‘Robert’

Pour éviter cela, utiliser la méthode set.discard() qui, elle, ne lèvera pas d’exception.

s = {"Kevin", "Kilian", "Morgane", "Gustave"}
s.discard("Robert")
print(s)

Résultat: {‘Morgane’, ‘Gustave’, ‘Kevin’, ‘Kilian’}

  • Vider un set avec la méthode set.clear()
s = {"Kevin", "Kilian", "Morgane", "Gustave"}
s.clear()
print("s =", s)

Résultat: s = set()

Pour découvrir plus de méthodes associées aux sets, je vous invite à consulter la documentation officielle Python.

Aperçu de quelques opérations mathématiques associées aux sets

  • Différence entre deux sets
s = {"Kevin", "Kilian", "Morgane", "Gustave"}
s2 = {"Kevin", "Gustave"}
s3 = s - s2
print("s3 =", s3)

s3 = {‘Morgane’, ‘Kilian’}

  • Union de deux sets
s = {"Patrick", "Jacky"}
s2 = {"R12 Gordini", "Kronenbourg"}
s3 = s | s2
print("s3 =", s3)

s3 = {‘Kronenbourg’, ‘Jacky’, ‘R12 Gordini’, ‘Patrick’}

  • Intersection de deux sets
s = {"Patrick", "Jacky"}
s2 = {"R12 Gordini", "Jacky"}
s3 = s & s2
print("s3 =", s3)

s3 = {‘Jacky’}

Les frozensets

Les sets sont des objets modifiables donc il n’est pas possible d’utiliser un set comme clé de dictionnaire. En effet, je vous rappelle que les clés de dictionnaire doivent être immuables.

Il n’est pas possible non plus de placer un set dans un autre set car comme je l’ai déjà dit au début de ce chapitre, les éléments d’un set doivent être immuables dans toute leur profondeur. Cela signifie que ce genre de code va lever une exception:

s = { {"Jacky", "Hervé"}, 1, 3} # présence d'un set
print("s =", s)

TypeError: unhashable type: ‘set’

s = { 4, ([1, 2], 3)} # présence d'un tuple contenant une liste
print("s =", s)

TypeError: unhashable type: ‘list’

Pour remédier à cet inconvénient, on a inventé le frozenset que l’on pourrait traduire par ensemble gelé. Les frozensets sont des sets immuables. Par conséquent, certaines méthodes telles que add() ou remove() ne peuvent pas leur être associées. En revanche, ils peuvent appartenir à un set ou bien être utilisés comme clés de dictionnaire.

  • Pour déclarer un frozenset, il n’existe pas trente-six solutions:
s = {1, 2, 3}
fr_s = frozenset(s)
print(type(fr_s))

Résultat: <class ‘frozenset’>

  • Notez bien que le constructeur frozenset() fonctionne également avec un tuple ou une liste:
tup = (1, 2, 3)
fr_s = frozenset(tup)
print(type(fr_s))
liste = [1, 2, 3]
fr_s = frozenset(liste)
print(type(fr_s))

Résultat: <class ‘frozenset’>

Comme je l’ai écrit en début de paragraphe, une fois déclaré, un frozenset peut appartenir à un set car il est devenu immuable:

liste = [1, 2, 3]
fr_s = frozenset(liste)
s = {fr_s, 4, 5}
print("s =", s)

Résultat:  s = {5, frozenset({1, 2, 3}), 4}

Conclusion

Un set est un ensemble d’objets immuables qui est préférable à une liste lorsqu’il s’agit d’effectuer un test d’appartenance. Il existe plusieurs méthodes associées aux sets. Les frozensets sont des ensembles devenus immuables et qui peuvent donc être utilisés comme clés de dictionnaire ou bien appartenir à un set.