Dans cette vidéo, nous allons parler des sets. Les sets sont très proches des dictionnaires, comme les dictionnaires, ils permettent de faire des tests d'appartenance, d'accéder, modifier, effacer des éléments indépendamment du nombre d'éléments. Les sets sont également des objets mutables mais à la différence des dictionnaires, les sets ne stockent qu'une clé, il n'y a pas de valeur correspondante. Alors on peut se demander à quoi ça sert d'avoir une sorte de sous-dictionnaire qui ne stocke que des clés et pas de valeurs. En fait, la raison, c'est que le set est optimisé et a été créé pour des opérations spécifiques. Une première opération dans laquelle le set est très utilisé, c'est par exemple pour garder uniquement les éléments uniques d'une séquence ; si on calcule le set des éléments d'une séquence, on ne va avoir que les éléments uniques. Une deuxième opération pour laquelle le set est également très utilisé, c'est pour faire des tests d'appartenance sur les éléments d'une séquence. Ouvrons maintenant un interpréteur Python pour commencer à jouer avec les sets.
Les sets comme les dictionnaires sont des objets mutables, on peut donc les modifier en place. Commençons par créer un set, un set vide. Je vais le créer avec la fonction built-in set. J'ai bien un objet de type *set*qui est vide. Ensuite, je peux créer un objet avec la notation accolades ; on va faire 1, 2, 3, 'a' et 18, je peux même stocker un booléen puisque je peux stocker n'importe quel objet hashable dans un set. Je vous rappelle qu'en Python tous les immuables sont hashables et que les mutables ne sont pas hashables. Donc je peux stocker des entiers, des chaînes de caractères et des tuples d'entiers ou de chaînes de caractères. Je crée mon set. Quelle est la différence ici entre les accolades qui représentent un set et les accolades qui représentent un dictionnaire ? Dans un set simplement, je n'ai pas la notation : qui sépare la clé et la valeur. C'est ça qui fait la différence pour l'interpréteur Python. Ensuite, je peux créer un set à partir d'une séquence, par exemple, je peux avoir une liste a qui contient des éléments 1, 2, 3, 1, 18, 20, 4 je vois que j'ai une séquence d'entiers avec des éléments qui sont dupliqués ; si je fais un set de a, je vais garder uniquement les éléments uniques, et créer un set à partir de ces éléments-là. On voit que j'ai un ensemble d'éléments uniques maintenant.
Ensuite, je peux manipuler un set avec les fonctions built-in len pour obtenir le nombre d'éléments ; là encore, on remarque la grande uniformité en Python, len est utilisée pour les séquences, pour les dictionnaires et pour les sets ; le test d'appartenance, comme vous devez vous en douter, est fait avec l'instruction in. Est-ce que 1 in s ? Je vois que c'est vrai. Je regarde de nouveau mon ensemble s. Est-ce que 'b' in s ? Je vois que c'est faux. Là encore, test d'appartenance tout à fait uniforme entre tous les types built-in en Python. Ensuite dans mon ensemble s, je peux ajouter des éléments avec la méthode add(). Je peux ajouter ici par exemple la chaîne de caractères '18' alors je vais plutôt mettre 'alice' voilà, et donc j'ai ajouté dans mon ensemble dans mon ensemble s, j'ai ajouté la chaîne de caractères 'alice' et je peux ajouter une séquence d'éléments donc faire une opération répétitive d'ajout d'élément dans un set, avec la fonction update(). Donc je prends update d'une séquence 1, 2, 3, 4, 5, 6 et 7 ; et évidemment, lorsque je fais un update je ne rajoute que les éléments qui ne sont pas déjà dans mon ensemble s. Donc je fais un update sur s et je vois que dans s, j'ai rajouté les éléments qui n'y étaient pas, notamment les 4, 5, 6, 7 mais par contre, les éléments 1, 2, 3 qui étaient déjà présents n'ont pas été rajoutés. Ensuite, sur un set, je peux faire des opérations d'ensembles classiques ; je vais prendre un set s1 qui contient 1, 2, 3, et je vais prendre un ensemble s2 qui contient 3, 4, 5. Je peux maintenant calculer une différence entre deux ensembles, s1 moins s2, qui va en fait enlever tous les éléments de s2 dans s1, on voit le résultat ; et puis ensuite, on peut prendre l'union et l'intersection des ensembles. Là, j'ai pris l'union et l'intersection qui est notée de la manière suivante. Voilà, donc des opérations classiques sur des ensembles.
Regardons maintenant l'efficacité du test d'appartenance. Vous pouvez peut-être vous poser une question, lorsque je fais un test d'appartenance, est-ce que c'est rentable de convertir ma séquence en set ou est-ce qu'il vaut mieux que je fasse directement le test d'appartenance sur une séquence ? Il faut comprendre ce que veut dire ce test d'appartenance sur les ensembles. Lorsque vous faites un test d'appartenance sur une séquence, vous devez parcourir tous les éléments de la séquence jusqu'à trouver l'élément que vous cherchez. Si l'élément n'est pas présent, vous devez parcourir tous les éléments de la séquence. Essentiellement, parcourir tous les éléments d'une séquence ça correspond à regarder une case mémoire dans votre ordinateur et faire une comparaison entre l'objet stocké dans cette case mémoire et l'objet que vous voulez comparer. Faire un test d'appartenance sur un set, c'est très différent ; comme on l'a vu, un set, c'est une table de hash ; ça veut donc dire que faire un test d'appartenance, ça représente essentiellement un calcul d'une fonction de hash sur l'objet que vous voulez chercher. Cette fonction de hash va vous donner une case et ensuite vous allez comparer si cet objet est le bon. La question qu'on peut se poser c'est combien de temps prend le calcul de cette fonction de hash sur votre objet. En fait, nous allons voir que c'est extrêmement rapide et que c'est essentiellement, le temps de calcul de cette fonction de hash, de l'ordre de grandeur de l'accès à un élément dans une séquence. Regardons cela.
Je vais créer une liste qui contient un seul élément 0. Et je vais créer un set à partir de cette liste. Donc j'ai ma liste a qui contient uniquement 0, et j'ai mon set s qui contient uniquement 0. Et maintenant je vais faire un test d'appartenance avec timeit. Je vais faire un timeit, je lui donne un argument moins n 50 pour lui dire qu'il ne fasse que 50 boucles pour que mon timeit soit plus rapide, est-ce que 0 in a ? Et regardons le temps d'exécution. Sur ma machine, cela prend autour de 40 nanosecondes. Maintenant, je vais faire le même test mais sur le set. Je vous rappelle que le processus est différent ; sur la liste, je vais accéder à la première case mémoire, je vais comparer l'objet stocké dans ma liste avec 0, il se trouve que c'est le même objet, je retourne vrai. Pour le set, je vais faire un calcul avec la fonction de hash sur 0, je vais accéder à une case et ensuite je fais faire la comparaison. Regardons cela. Je regarde sur un set et je vois que le test d'appartenance est de l'ordre encore de 40 nanosecondes. Qu'est-ce que ça veut dire ? Ça veut dire qu'en fait, dès que vous avez à faire un test d'appartenance, convertissez toujours votre séquence en set, ce sera dans la quasi intégralité des cas une opération rentable. En fait, vous pouvez demander combien de temps cela va prendre de convertir une séquence en set. En fait, convertir une séquence en set, ça va prendre le temps de calculer la fonction de hash sur chaque élément. C'est essentiellement le temps qu'il vous faudrait pour parcourir une seule fois cette séquence si vous faisiez un test sur un objet qui n'appartient pas à la séquence. Donc on voit qu'en fait, quasiment tout le temps, c'est beaucoup plus rentable de convertir votre séquence en set, donc c'est notre recommandation: dès que vous faites un test d'appartenance sur une séquence, convertissez cette séquence en set et faites le test d'appartenance sur ce nouveau set.
Dans cette vidéo, nous avons vu le type set qui est une implémentation de table de hash, très proche du dictionnaire. La principale différence, c'est que le set ne stocke pas de valeurs, il ne stocke que des clés ; et nous avons vu notamment que le set était extrêmement efficace pour faire des tests d'appartenance.