Les Ensembles immuables (frozensets) en Python

1. Introduction

1.1 Définition

Un frozenset en Python est une structure de données immuable, non ordonnée et qui ne contient pas de doublons. Contrairement aux ensembles traditionnels (sets), les frozensets ne peuvent pas être modifiés après leur création. Ils sont utilisés pour représenter des collections d'éléments uniques et offrent des opérations efficaces pour les tests d'appartenance et les opérations mathématiques sur les ensembles (union, intersection, différence, etc.). Du fait de leur immutabilité, les frozensets sont hashables et peuvent ainsi être utilisés comme clés de dictionnaires ou comme éléments d'autres ensembles (ou frozensets).

1.2 Contextualisation

Comparaison avec d'autres structures de données Python :

Listes : Mutables, ordonnées, permettent les doublons, non hashables.
Tuples : Immuables, ordonnés, permettent les doublons, hashables.
Ensembles (sets) : Mutables, non ordonnés, pas de doublons, non hashables.
frozensets : Immuables, non ordonnés, pas de doublons, hashables.
Dictionnaires : Mutables, ordonnés (depuis Python 3.7), paires clé-valeur uniques, les clés doivent être hashables.

1.3 Cas d'utilisation

Les frozensets sont particulièrement adaptés pour :

Utiliser des ensembles comme clés de dictionnaire ou éléments d'autres ensembles (ou frozensets). Cela est possible en raison de leur nature hashable.
Éliminer les doublons d'une collection d'éléments (comme les sets) qu'on ne souhaite pas modifier ultérieurement.
Vérifier rapidement si un élément existe dans une collection (test d'appartenance).
Réaliser des opérations mathématiques sur les ensembles (union, intersection, différence, différence symétrique).
Représenter des groupes uniques d'éléments (par exemple, les permissions d'un utilisateur) de manière immuable.
Implémenter des algorithmes qui requièrent l'unicité des valeurs, comme la détection de cycles dans un graphe ou le calcul des ensembles de couverture et où l'immutabilité est requise.

2. Caractéristiques Fondamentales

2.1 Non-ordonnancement

Les frozensets en Python sont des collections non ordonnées. L'ordre des éléments à l'intérieur d'un frozenset n'est pas garanti et peut varier. Cela signifie que vous ne pouvez pas accéder aux éléments d'un frozenset par leur position (index).


# Demonstrating unordered nature of frozensets
my_frozenset = frozenset({3, 1, 2})
print(f"Original frozenset: {my_frozenset}")

# Iteration order is not predictable
print("Iterating through the frozenset:")
for element in my_frozenset:
print(element)

2.2 Unicité

Les frozensets ne contiennent pas de doublons. Si vous tentez d'ajouter plusieurs fois le même élément lors de la création d'un frozenset, il n'apparaîtra qu'une seule fois. L'immutabilité empêche les ajouts et suppressions ultérieures.


# Demonstrating uniqueness of elements
my_frozenset = frozenset({1, 2, 2, 3, 3, 3})
print(f"Frozenset with duplicates: {my_frozenset}")

2.3 Immutabilité

Les frozensets sont immuables. Une fois créé, leur contenu ne peut pas être modifié. Cela signifie qu'on ne peut ni ajouter, ni supprimer des éléments après l'initialisation. Du côté de la gestion de la mémoire, les frozensets disposent aussi d'un avantage notable: leurs données ne peuvent pas se corrompre et d'être ainsi des entités sécurisées.


# Demonstrating immutability of frozensets
my_frozenset = frozenset({1, 2, 3})
print(f"Original frozenset: {my_frozenset}")

# Attempting to add or remove elements will raise an AttributeError:
# my_frozenset.add(4)        # AttributeError: 'frozenset' object has no attribute 'add'
# my_frozenset.remove(2)     # AttributeError: 'frozenset' object has no attribute 'remove'
# my_frozenset.discard(2)    # AttributeError: 'frozenset' object has no attribute 'discard'

3. Création et Constructeur

3.1 Syntaxe de création

Les frozensets peuvent être créés de plusieurs manières :

Utilisation du constructeur frozenset().


# Different ways to create frozensets

# Empty frozenset
empty_frozenset = frozenset()

# Frozenset with initial values
numbers = frozenset({1, 2, 3, 4, 5})
mixed_types = frozenset({1, "hello", 3.14, (1,2)})  #Tuples are hashable, so they can be in the frozenset

# Using the frozenset() constructor with other iterables
from_list = frozenset([1, 2, 3])
from_string = frozenset("Python")
from_tuple = frozenset((1, 2, 3))
from_range = frozenset(range(5))

print(f"From list: {from_list}")
print(f"From string: {from_string}")
print(f"From tuple: {from_tuple}")
print(f"From range: {from_range}")

3.2 Conversion

Le constructeur frozenset() permet de convertir d'autres types de données itérables en frozensets , en éliminant les doublons. Le constructeur tentera d'itérer sur l'objet fourni et d'ajouter chaque élément unique au frozenset.


# Converting other data types to frozensets

# From list
list_data = [10, 20, 30, 10]
frozenset_from_list = frozenset(list_data)

# From string
string_data = "Hello"
frozenset_from_string = frozenset(string_data)

# From tuple
tuple_data = (1, 2, 3, 1)
frozenset_from_tuple = frozenset(tuple_data)

# From dictionary (gets the keys)
dict_data = {"a": 1, "b": 2, "c": 3}
frozenset_from_dict_keys = frozenset(dict_data)

print(f"From list: {frozenset_from_list}")
print(f"From string: {frozenset_from_string}")
print(f"From tuple: {frozenset_from_tuple}")
print(f"From dict keys: {frozenset_from_dict_keys}")

4. Opérations de Base

4.1 Opérations non disponibles sur frozensets

En raison de leur immutabilité, les frozensets ne supportent pas les opérations permettant d'ajouter ou supprimer des éléments. Les méthodes telles que :

add()
remove()
discard()
pop()
clear()

ne sont pas disponibles et génèreront une erreur AttributeError.


# Demonstrating that methods to add or remove are not available
my_frozenset = frozenset({1, 2, 3, 4})

# These operations will raise an AttributeError:
# my_frozenset.add(5)        # AttributeError: 'frozenset' object has no attribute 'add'
# my_frozenset.remove(3)     # AttributeError: 'frozenset' object has no attribute 'remove'
# my_frozenset.discard(6)    # AttributeError: 'frozenset' object has no attribute 'discard'
# my_frozenset.pop()         # AttributeError: 'frozenset' object has no attribute 'pop'
# my_frozenset.clear()       # AttributeError: 'frozenset' object has no attribute 'clear'

4.2 Opérations de test d'appartenance

Python permet de vérifier si un élément est présent dans un frozenset avec l'opérateur in. Cette opération est très rapide (complexité temporelle O(1) en moyenne), ce qui rend les frozensets très efficaces pour les tests d'appartenance.


# Test d'appartenance
my_frozenset = frozenset({1, 2, 3})

# Checking existence
is_present = 2 in my_frozenset  # Returns True
is_absent = 4 in my_frozenset  # Returns False

print(f"Is 2 present? {is_present}")
print(f"Is 4 present? {is_absent}")

4.3 Opérations mathématiques sur les ensembles

Les frozensets offrent les mêmes opérations mathématiques que les ensembles (sets), car ces opérations ne modifient pas les ensembles originaux (elles retournent de nouveaux frozensets ) :

union() ou | : Retourne un nouvel frozenset contenant tous les éléments des deux frozensets . L'opérateur | est une forme abrégée pour l'opération union().
intersection() ou & : Retourne un nouvel frozenset contenant les éléments communs aux deux frozensets . L'opérateur & est une forme abrégée pour l'opération intersection().
difference() ou - : Retourne un nouvel frozenset contenant les éléments qui sont dans le premier frozenset mais pas dans le second. L'opérateur - est une forme abrégée. L'ordre compte : frozenset1 - frozenset2 est différent de frozenset2 - frozenset1.
symmetric_difference() ou ^ : Retourne un nouvel frozenset contenant les éléments qui sont dans l'un ou l'autre des frozensets , mais pas les deux (c'est-à-dire l'union moins l'intersection). L'opérateur ^ est une forme abrégée.


# Set operations
frozenset1 = frozenset({1, 2, 3, 4})
frozenset2 = frozenset({3, 4, 5, 6})

# Union
union_frozenset = frozenset1.union(frozenset2)  # or frozenset1 | frozenset2
print(f"Union: {union_frozenset}")

# Intersection
intersection_frozenset = frozenset1.intersection(frozenset2)  # or frozenset1 & frozenset2
print(f"Intersection: {intersection_frozenset}")

# Difference
difference_frozenset = frozenset1.difference(frozenset2)  # or frozenset1 - frozenset2
print(f"Difference (frozenset1 - frozenset2): {difference_frozenset}")

difference_frozenset2 = frozenset2.difference(frozenset1)
print(f"Difference (frozenset2 - frozenset1): {difference_frozenset2}")

# Symmetric difference
symmetric_difference_frozenset = frozenset1.symmetric_difference(frozenset2)  # or frozenset1 ^ frozenset2
print(f"Symmetric difference: {symmetric_difference_frozenset}")

5. Copie et Références

5.1 Références et assignation

Comme pour les autres types de données immuables, les variables de frozenset sont des références aux objets en mémoire. Lorsqu'un frozenset est assigné à une nouvelle variable, les deux variables font référence au même objet. Dans le cas d'un frozenset , comme il est immuable, il n'y a pas de distinction entre l'original et la copie car le contenu ne peut pas être modifié.


# References and assignment

# Creating a frozenset
original = frozenset({1, 2, 3, 4, 5})

# Assigning to a new variable (creates a reference, not a copy)
reference = original

# Because frozensets are immuable, we cannot change the content (no side effects)

# Both variables reference the same frozenset
print(f"Original: {original}")
print(f"Reference: {reference}")

# Checking if they reference the same object
print(f"Same object? {original is reference}")

5.2 Pas de méthode de copie directe

Étant donné que les frozensets sont immuables, la création d'une copie via .copy() n'est pas nécessaire, l'assignation simple crée déjà une référence. Et il n'existe pas de méthode .copy() pour les frozensets.

6. Frozensets et Hashabilité

6.1. Hashabilité

L'un des principaux avantages des frozensets est leur hashabilité. Un objet est dit hashable s'il possède une valeur de hachage qui ne change jamais pendant sa durée de vie (considérant sa nature immuable), et qu'il peut être comparé à d'autres objets. Contrairement aux ensembles traditionnels (sets) qui sont mutables et donc non-hashables, les frozensets sont immuables et hashables.

6.2. Cas d'usage de la hashabilité des frozensets

Clés de dictionnaires. Vous pouvez utiliser un frozenset comme clé dans un dictionnaire. Cela permet de représenter des structures uniques d'éléments hashables.
Éléments d'autres ensembles ou frozensets. Les frozensets peuvent être des éléments d'autres sets, et ils peuvent servir aussi comme éléments d'autres frozensets..
Optimisation dans les algorithmes. L'hashage des frozensets offre une lookup (recherche) efficace, en O(1) en moyenne, ce qui peut améliorer considérablement les performances dans les opérations sur les ensembles.


# Using frozensets as dictionary keys
my_dict = {
frozenset({1, 2}): "value1",
frozenset({3, 4}): "value2"
}

print(my_dict[frozenset({1, 2})])  # Output: value1
print(my_dict[frozenset({3, 4})])  # Output: value2

# Using frozensets as elements of sets
set_of_frozensets = {frozenset({1, 2}), frozenset({3, 4})}
print(set_of_frozensets)  #Output: {frozenset({1, 2}), frozenset({3, 4})}

# This fails for regular sets because they are not hashable
# my_dict = {
#    {1,2}: "value1"  # This will raise a TypeError: unhashable type: 'set'
# }

7. Itération

7.1 Boucles et itération

Les frozensets Python sont itérables, ce qui permet de parcourir leurs éléments de différentes manières :

Boucle for classique
(Pas de compréhensions de frozenset possible)


# Iterating through frozensets
my_frozenset = frozenset({"apple", "banana", "cherry"})

# Basic for loop
print("Basic for loop:")
for fruit in my_frozenset:
print(f"- {fruit}")

# Note: the order of iteration is not guaranteed.  It might appear random.

8. Performance

8.1 Complexité temporelle

La complexité temporelle des opérations sur les frozensets Python est importante à comprendre pour écrire du code efficace :

Test d'appartenance (in) : O(1) en moyenne, O(n) dans le pire des cas (collisions) - Très rapide. (Similaire aux sets)
Union (|) : O(len(frozenset1) + len(frozenset2)). (Similaire aux sets)
Intersection (&) : O(min(len(frozenset1), len(frozenset2))). (Similaire aux sets)
Différence (-) : O(len(frozenset1)). (Similaire aux sets)

Les opérations de base sur les frozensets ont généralement une complexité temporelle constante (O(1)) ou linéaire (O(n)). La complexité temporelle de ces opérations rend les frozensets très performants pour de nombreuses tâches, notamment les tests d'appartenance et les opérations ensemblistes.


# Performance demonstration
import time

# Create a large frozenset
large_frozenset = frozenset(range(100000))

# Function to measure execution time
def measure_time(func, *args):
start = time.time()
result = func(*args)
end = time.time()
return (end - start) * 1000  # Convert to milliseconds

# Measure membership test time (O(1) on average)
membership_time = measure_time(lambda s: 99999 in s, large_frozenset)
print(f"Membership test time: {membership_time:.4f} ms")

# (Pas de mesure du temps pour 'add' car les frozensets sont immuables)

# Measure intersection time
large_frozenset2 = frozenset(range(90000, 110000))
intersection_time = measure_time(lambda s1, s2: s1.intersection(s2), large_frozenset, large_frozenset2)
print(f"Intersection time: {intersection_time:.4f} ms")

9. Cas d'Utilisation Pratiques

9.1 Élimination des doublons (Utilisation détournée avec frozenset)

Les frozensets ne peuvent pas être directement utilisés pour éliminer des doublons *en-place*. Néanmoins , on peut toujours construire un frozenset à partir d'une collection pour en éliminer les doublons.


# Removing duplicates from a list (and creating a frozenset)
my_list = [1, 2, 2, 3, 4, 4, 4, 5]
unique_frozenset = frozenset(my_list) # On construit un frozenset
unique_list = list(unique_frozenset) # Si on souhaite une liste ordonnée

print(f"Original list: {my_list}")
print(f"list with duplicates removed: {unique_list}")

9.2 Test d'appartenance

Les frozensets offrent un test d'appartenance très efficace, comme les sets. Ils sont plus rapides que les listes pour vérifier si un élément est présent. Il est fortement recommandé d'utiliser les frozensets si les performances sont critiques et si l'ordre des éléments n'est pas important. Ils ont l'avantage d'être hashable et donc utilisables comme clé de dictionnaire.


# Checking for existence
my_frozenset = frozenset({1, 2, 3, 4, 5})

if 3 in my_frozenset:
print("3 is in the frozenset")

if 6 not in my_frozenset:
print("6 is not in the frozenset")

9.3 Opérations sur les ensembles (ex: permissions)

Les frozensets sont utiles pour représenter et manipuler des ensembles d'éléments, comme les permissions ou les rôles d'utilisateurs. Ils sont immuables donc plus sûrs pour ce type de cas.


# Frozenset operations for permissions or roles
admin_permissions = frozenset({"read", "write", "delete", "update"})
editor_permissions = frozenset({"read", "write", "update"})
viewer_permissions = frozenset({"read"})

# Checking if a user has specific permissions
def has_permission(user_permissions, required_permissions):
return required_permissions.issubset(user_permissions)

if has_permission(admin_permissions, frozenset({"read", "delete"})):
print("Admin has read and delete permissions")

# Finding the common permissions between admin and editor
common_permissions = admin_permissions.intersection(editor_permissions)
print(f"Common permissions: {common_permissions}")

# Finding permissions unique to the admin (impossible à modifier les frozensets)
admin_unique_permissions = admin_permissions.difference(editor_permissions)
print(f"Admin's unique permissions: {admin_unique_permissions}")

10. Exercices

10.1 Exercice 1: Manipulation de base

Créez un frozenset avec les nombres 1 à 5, puis effectuez les opérations suivantes :

(Impossible) Ajoutez un nombre au frozenset. Il faudrait créer un nouveau frozenset.
(Impossible) Supprimez le nombre 3 du frozenset. Il faudrait créer un nouveau frozenset.
Vérifiez si le nombre 2 est dans le frozenset.
Créez un autre frozenset avec les nombres 4, 5, 6, et 7. Effectuez les opérations d'union, d'intersection et de différence entre les deux frozensets.


# Exercice 1: Solution

# Créer un frozenset de nombres de 1 à 5
numbers = frozenset({1, 2, 3, 4, 5})
print(f"frozenset initial: {numbers}")

# 1. (Impossible) Ajouter 6 : créer un nouveau frozenset
# numbers.add(6)  # Ceci provoquerait une erreur
# print(f"Après ajout de 6: {numbers}")

# 2. (Impossible) Supprimer 3: créer un nouveau frozenset
# numbers.discard(3) # Ceci provoquerait une erreur
# print(f"Après suppression de 3: {numbers}")

# 3. Vérifier si 2 est dans le frozenset
if 2 in numbers:
print("Le nombre 2 est dans le frozenset.")
else:
print("Le nombre 2 n'est pas dans le frozenset.")

# 4. Opérations avec un autre frozenset
other_numbers = frozenset({4, 5, 6, 7})

# Union
union_set = numbers | other_numbers  # ou numbers.union(other_numbers)
print(f"Union: {union_set}")

# Intersection
intersection_set = numbers & other_numbers  # ou numbers.intersection(other_numbers)
print(f"Intersection: {intersection_set}")

# Différence (numbers - other_numbers)
difference_set = numbers - other_numbers  # ou numbers.difference(other_numbers)
print(f"Différence (numbers - other_numbers): {difference_set}")

10.2 Exercice 2: Applications des Sets

Considérez une situation de gestion de présence. On a deux listes, une pour les employés présents et une autre pour les employés qui étaient prévus. Utilisez les frozensets pour :

Trouver les employés qui étaient présents mais n'étaient pas prévus (absences non autorisées)
Trouver les employés qui étaient prévus mais absents (absences autorisées ou non)
Trouver tous les employés impliqués (présents ou prévus) (mais avec un nouveau frozenset final)


# Exercice 2: Solution

# Employés présents et prévus
employes_presents = ["Alice", "Bob", "Charlie", "David"]
employes_prevus = ["Bob", "Charlie", "Eve", "Frank"]

# Convertir en frozensets
set_presents = frozenset(employes_presents)
set_prevus = frozenset(employes_prevus)

# 1. Absences non autorisées (présents non prévus)
absences_non_autorisees = set_presents - set_prevus
print(f"Absences non autorisées: {absences_non_autorisees}")

# 2. Absents (prévus mais non présents)
absents = set_prevus - set_presents
print(f"Absents: {absents}")

# 3. Tous les employés impliqués (union)
tous_employes = set_presents | set_prevus
print(f"Tous les employés impliqués: {tous_employes}")

10.3 Exercice 3: Analyse de données avec Sets

Vous avez deux fichiers contenant des listes de mots. Utilisez les frozensets pour :

Trouver les mots uniques qui apparaissent dans les deux fichiers.
Trouver tous les mots uniques apparaissant dans les deux fichiers.
Trouver les mots qui apparaissent dans le premier fichier mais pas dans le second.


# Exercice 3: Solution

# Simuler le contenu des fichiers (remplacez ceci par la lecture de fichiers réels)
fichier1_mots = ["pomme", "banane", "orange", "pomme", "fraise"]
fichier2_mots = ["banane", "kiwi", "orange", "raisin"]

# Convertir en frozensets (pour se débarrasser des doublons)
set_fichier1 = frozenset(fichier1_mots)
set_fichier2 = frozenset(fichier2_mots)

# 1. Mots communs
mots_communs = set_fichier1 & set_fichier2
print(f"Mots communs: {mots_communs}")

# 2. Tous les mots uniques
tous_les_mots = set_fichier1 | set_fichier2
print(f"Tous les mots uniques: {tous_les_mots}")

# 3. Mots présents dans le fichier 1 mais pas dans le fichier 2
mots_fichier1_uniques = set_fichier1 - set_fichier2
print(f"Mots uniques dans le fichier 1: {mots_fichier1_uniques}")

11. Résumé et Comparaisons

Points clés à retenir sur frozensets Python :

Structure de données non ordonnée et immuable - contrairement aux sets.
Éléments uniques (pas de doublons).
Opérations mathématiques sur frozensets (union, intersection, différence, différence symétrique)
Utilisation pour pour créer des clés de dictionnaires notamment.
Accès rapide pour la vérification de l'appartenance (grâce au hachage)

Bonnes Pratiques

Utilisez les frozensets lorsque l'ordre des éléments n'est pas important, que l'unicité est requise, et que l'immutabilité est nécessaire (ex: clés de dictionnaires).
Utilisez les frozensets pour des opérations de comparaison efficaces (intersection, union, etc.).
Préférez la syntaxe des opérateurs (|, &, -) pour plus de lisibilité.
Convertissez une liste en frozenset ( frozenset(ma_liste) ) pour éliminer rapidement les doublons.

Comparaison sets / frozensets

Mutabilité: Les set sont mutables (modifiables), les `frozenset` sont immuables.
Hashabilité: Les set ne sont pas hashables et ne peuvent pas être utilisés comme clés de dictionnaire ou éléments d'autres set. Les `frozenset` sont hashables.
Opérations de modification: On peut ajouter/supprimer des éléments à un set. Impossible pour un `frozenset`.
Cas d'utilisation: set pour les collections changeantes, `frozenset` quand l'immutabilité est requise (sécurité, clés de dictionnaire).

12. Conclusion

Les frozensets sont des structures de données puissantes et efficaces en Python, particulièrement utiles pour gérer des collections d'éléments uniques et effectuer des opérations ensemblistes. Leur immutabilité et leur hashabilité en font un outil précieux dans de nombreuses situations.

Points clés à retenir :

Les frozensets sont non ordonnés, contiennent uniquement des éléments uniques et sont immuables.
Ils offrent des opérations efficaces pour la comparaison et la manipulation de collections.
Ils sont utiles pour la création de clés de dictionnaires, la vérification de l'appartenance, et le traitement de données ensemblistes immuables.
Comprendre les frozensets vous aidera à écrire du code Python plus efficace et plus concis.

Maîtriser les frozensets et leurs opérations vous permettra de résoudre élégamment une grande variété de problèmes de programmation, notamment le traitement de données, la gestion de collections et l'optimisation des algorithmes. Les frozensets complètent les listes et les dictionnaires pour enrichir vos outils de développement Python.