Python: Les ensembles (sets et frozensets)

Pour une lecture plus agréable (page plus large), je vous invite à cliquer sur ce lien et à lire ce chapitre dans la rubrique consacrée au langage Python.

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 &amp; 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.

Auteur : Ordinosor

Bienvenue sur Miamondo, mon blog personnel. "Mia mondo", c'est de l'espéranto et ça signifie "Mon monde" en français. Je m'appelle Benoît alias Ordinosor, Français expatrié en Allemagne. Mes centres d'intérêt sont les distributions GNU/Linux, le langage de programmation Python, la science-fiction et l'espéranto.

5 réflexions sur « Python: Les ensembles (sets et frozensets) »

    1. Bonjour,

      Merci pour ton commentaire. Je précise que dans la conclusion, l’adjectif « immuables » porte sur le mot « objets ». Un set est bien un ensemble d’objets immuables.
      Mais j’ai remarqué que ma syntaxe pouvait prêter à confusion car tout est au pluriel donc on ne sait pas si « immuables » porte sur le mot « objets » ou sur le mot « sets ». J’ai donc corrigé en mettant « set » au singulier pour qu’il n’y ait plus de confusion.
      Je te remercie pour la remarque.
      Bonne journée,
      Benoît.

      J'aime

  1. Bonjour Benoît.
    Merci pour cet article très sympathique 🙂 !

    Pour info, voici une autre manière de faire des recherches « rapide (?) » dans un lot de données important. Elle ne fonctionne par contre que pour des objets immuables. L’idée est de tester si l’objet recherché est bien une clé d’un dictionnaire dans lequel on a associé : clé (objet) : None pour chacune objet de nos données. Pour cela il suffit de faire une affectation type a = dictionnaire[donnée] et de lever une exception si ça échoue.
    Je trouve cette méthode assez rapide (sur python 2.6 en tous cas !). Attention toutefois, le temps de création du dictionnaire peut être pénalisant…

    Voici un morceau de code.
    Steven

    = CODE Python 2.6 ===========================================

    #!/usr/bin
    # -*- coding: utf-8 -*-
    
    from time import time
    
    a = 50000000
    
    print "Création..."
    #l = [i for i in xrange(a)] # liste
    #l = {i for i in xrange(a)} # set
    l = {} # dictionnaire
    for i in xrange(a):
        l[i] = None
    
    print "type(l)", type(l)
    
    print "Recherche..."
    
    tic = time()
    #for i in xrange(a-8, a-2):
    #    if i in l:
    #        print i, "appartient au set/liste."
    
    for i in xrange(a-8, a-2):
        try:
            b = l[i]
            print i, "appartient aux clés du dictionnaire."
        except:
            pass
    
    print "Temps écoulé pour la recherche", time() - tic, "s."

    J'aime

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s