Fiche de révision : Conteneurs de données

Conteneurs de données généralistes

• En Python, une liste est une structure de données dont les éléments individuels sont accessibles à partir de leur position indicielle.
• Les listes sont ordonnées et mutables. Elles peuvent contenir toutes sortes d’objets, y compris d’autres listes imbriquées et des doublons.
• La création d’une liste peut s’effectuer de la façon suivante :

# liste non vide
liste = ['Ada', 'Alan', 'Alice']

• L’ajout d’élément(s) en fin de liste s’effectue avec la méthode append() ou la notation courte équivalente.
• L’ajout est automatiquement effectué en fin de liste puisque, tant qu’elle n’a pas fait l’objet d’un tri, une liste reflète l’ordre d’insertion des éléments qui la composent.
• Chaque élément est accessible par sa position indicielle (la numérotation commence à $0$).
• Il est possible de modifier des éléments existants dans la liste.
• Il est possible d’insérer des éléments au sein d’une liste.
• Il est possible d’étendre une liste par l’ajout d’un contenu d’une autre liste ou d’un autre itérable, avec la méthode extend().
• Il est possible d’extraire des éléments d’une liste par la méthode pop() (extraction par défaut du dernier élément de la liste).
• Il est possible de supprimer un élément en fonction de sa valeur avec la méthode remove() (retire la première occurrence rencontrée).
• Une liste triée remplace la liste d'origine, avec la méthode sort(). L’ordre de la liste peut être facilement inversé avec la méthode reverse().

• En Python, les dictionnaires sont des conteneurs de données permettant de stocker des paires de clés et de valeurs associées à ces clés.
• Avec les dictionnaires, l’ordre n’est pas important, c’est la clé qui ouvre l’accès à la donnée.
• Ils sont mutables et peuvent contenir toutes sortes d’objets et des structures de données imbriquées, notamment d’autres dictionnaires et des listes.
• La création d’un dictionnaire peut s’effectuer de la façon suivante :

# dictionnaire non vide
meteo = {'Toulouse': 15, 'Strasbourg': 16}

• L’ajout d’un élément s’effectue en indiquant sa clé entre crochets et en lui affectant sa valeur.
• L’accès à un élément du dictionnaire (ou la modification de cet élément) s’effectue principalement par sa clé, avec la même notation que pour l’ajout.
• Le retrait d’un élément s’effectue avec la méthode pop() en spécifiant la clé concernée.
• Il est possible de compléter et mettre à jour le dictionnaire à partir d’un autre dictionnaire avec la méthode update(), selon les modalités suivantes :
• les clés absentes du dictionnaire sont ajoutées avec les valeurs correspondantes ;
• les valeurs des clés déjà présentes dans le dictionnaire d’origine sont remplacées par celles du dictionnaire ajouté.

• Les tuples sont des séquences ordonnées et non mutables. Ils peuvent contenir toutes sortes d’éléments de différents types ainsi que des doublons.
• La création d’un tuple peut s’effectuer par énumération ou à partir d’un itérable.
• Les tuples étant immutables, il n’est pas possible d’ajouter, de modifier ou de supprimer des éléments. Ceux-ci sont accessibles en lecture par la notation indicielle, comme pour les listes.
• Il est possible de compter le nombre d’occurrences d’une valeur au sein d’un tuple avec la méthode count().

• Les sets sont des conteneurs de données non ordonnés dont les éléments sont uniques.
• Ils sont mutables et peuvent contenir des éléments hétérogènes, mais ne peuvent pas contenir d’éléments mutables (listes, dictionnaires, sets) ni de doublons.
• La création d’un set s’effectue de la façon suivante :

villes = set() # set vide
villes = {'Toulouse', 'Strasbourg', 'Paris', 'Brest'}

• L’ajout d’éléments à un set s’effectue avec la méthode add().
• Il est possible de retirer un élément d’un set sur la base de sa valeur avec la méthode remove().
• Les sets disposent d’un jeu complet de méthodes ensemblistes spécifiques permettant d’obtenir très facilement :
• l’union entre deux sets avec la méthode union() ;
• l’intersection entre deux sets avec la méthode intersection() ;
• la différence entre deux sets avec la méthode difference() ;
• la différence symétrique entre deux sets avec la méthode symmetric_difference().

Les sets permettent aussi de déterminer :

• si un set est un sous-ensemble d’un autre set avec la méthode issubset() ;
• si un set est un sur-ensemble d’un autre set avec la méthode issuperset().

Piles et files

• LIFO signifie Last In, First Out (dernier entré, premier sorti).
• FIFO signifie First In, First Out (premier entré, premier sorti).
• Les piles de type FIFO sont communément appelées « files » ou « files d’attente ».
• Les méthodes principales des piles sont l’empilage et le dépilage :
• empiler consiste à ajouter un élément à la pile ;
• dépiler consiste à retirer un élément à la pile.
• Dans une pile LIFO, le point d’entrée de la pile est aussi le point de sortie.
• Dans une pile FIFO, le point d’entrée et le point de sortie sont aux extrémités opposées de la pile.
• Les listes natives de Python que nous avons étudiées en première partie nous permettent techniquement d’implémenter des piles LIFO et des piles FIFO.
• Si l’empilage et le dépilage avec pop() et append() sont rapides car effectués en fin de liste, les insertions en début de liste, nécessaires pour une file, sont lentes : elles obligent à décaler chaque fois en mémoire tous les éléments suivants composant la liste.
• On pourrait faire l’inverse en utilisant append() pour ajouter en fin de liste à la place d’insert(0) qui insérait en début de liste, mais le retrait d’une file devant s’effectuer à l’extrémité opposée, on aurait alors dû utiliser pop(0) pour les sorties de file, avec le même problème de décalage en mémoire des éléments suivants, et donc de performance.
• Il existe des conteneurs spécialisés pour implémenter les files avec le type deque du module collections de la bibliothèque standard.
• Ce type de conteneur a été conçu pour permettre l’ajout et le retrait d’éléments de manière optimisée à chaque extrémité du conteneur.
• Pour l’implémentation d’une file d’attente, on peut choisir d’effectuer :
• les entrées (enfilage) avec append() ;
• les sorties (défilage) avec popleft().
• On pourrait symétriquement réaliser notre implémentation en remplaçant append() par appendleft() et popleft() par pop().
• Dans les deux cas, l’entrée et la sortie s’effectuent aux extrémités opposées de la file d’attente.

Critères d’emploi des conteneurs de données

• La modélisation consiste à transposer un problème du monde réel en problématique traitable par un algorithme.
• Si certaines données sont liées entre elles, il est souhaitable que leur modélisation reflète ce lien pour éviter d’entrainer des incohérences.
• Illustrons-le avec l’exemple d’un groupe d’élèves dont on connaît les prénoms et les âges. On choisit dans un premier temps de stocker de manière parallèle ces informations dans deux listes distinctes.

prenoms = ['Ada', 'Alan', 'Alice', 'Bob']
ages = [17, 22, 21, 19]

for prenom, age in zip(prenoms, ages):

• Les données concernant le nom et l’âge de l’élève sont stockées dans des conteneurs différents, mais nous pouvons itérer en même temps sur les deux listes avec la fonction native zip(). *La concordance entre les informations sur le prénom et l’âge d’un élève repose uniquement sur leur position dans chaque liste. La moindre erreur lors d’un ajout ou d’une suppression pourrait introduire un décalage, rendant les données incohérentes.
• Le recours à un dictionnaire s’avère donc plus adapté au cas présent.
• La suppression d’un élève (clé du dictionnaire) entraîne automatiquement la suppression de son âge (valeur associée à la clé).
• On pourrait éventuellement utiliser une liste de tuples à la place d’un dictionnaire.
• Le recours à des tuples crée une association entre l’élève et son âge. La suppression d’un élément de la liste des élèves fait disparaître le tuple correspondant, contenant à la fois son prénom et son âge.
• Mais le caractère immutable des tuples nous empêche de modifier l’âge d’un élève.

print(eleves[0][1])
# affiche 17 (âge d'Alice)

eleves[0][1] = 18
# affiche TypeError: 'tuple' object does not support item assignment