Vous souhaitez ajouter des structures de données à votre boîte à outils de programmation ? Faites les premiers pas dès aujourd’hui en vous familiarisant avec les structures de données en Python.
Lorsque vous apprenez un nouveau langage de programmation, il est important de comprendre les types de données de base et les structures de données intégrées que le langage prend en charge. Dans ce guide sur les structures de données en Python, nous aborderons les points suivants :
- les avantages des structures de données
- les structures de données intégrées en Python, telles que les listes, les tuples, les dictionnaires et les ensembles
- les implémentations de types de données abstraits tels que les piles et les files d’attente.
C’est parti !
Pourquoi les structures de données sont-elles utiles ?
Avant de passer en revue les différentes structures de données, voyons en quoi l’utilisation des structures de données peut être utile :
- Traitement efficace des données: Le choix de la bonne structure de données permet de traiter les données plus efficacement. Par exemple, si vous devez stocker une collection d’éléments du même type de données, avec des temps de consultation constants et un couplage étroit, vous pouvez choisir un tableau.
- Meilleure gestion de la mémoire: Dans les grands projets, pour le stockage des mêmes données, une structure de données peut être plus efficace en termes de mémoire qu’une autre. Par exemple, en Python, les listes et les tuples peuvent être utilisés pour stocker des collections de données de types identiques ou différents. Toutefois, si vous savez que vous n’aurez pas à modifier la collection, vous pouvez choisir un tuple qui occupe relativement moins de mémoire qu’une liste.
- Uncode mieux organisé: L’utilisation de la bonne structure de données pour une fonctionnalité particulière rend votre code plus organisé. Les autres développeurs qui liront votre code s’attendront à ce que vous utilisiez des structures de données spécifiques en fonction du comportement souhaité. Par exemple : si vous avez besoin d’une correspondance clé-valeur avec des temps de consultation et d’insertion constants, vous pouvez stocker les données dans un dictionnaire.
Listes
Lorsque nous avons besoin de créer des tableaux dynamiques en Python – que ce soit lors d’entretiens de codage ou dans des cas d’utilisation courants – les listes sont les structures de données à utiliser.
Les listes Python sont des types de données de conteneur mutables et dynamiques, ce qui vous permet d’ajouter et de supprimer des éléments d’une liste sur place, sans avoir à en créer une copie.
Lorsque vous utilisez des listes Python :
- L’indexation dans la liste et l’accès à un élément à un index spécifique est une opération à temps constant.
- L’ajout d’un élément à la fin de la liste est une opération à temps constant.
- L’insertion d’un élément à un index spécifique est une opération en temps linéaire.
Il existe un ensemble de méthodes de liste qui nous aident à effectuer des tâches courantes de manière efficace. L’extrait de code ci-dessous montre comment effectuer ces opérations sur une liste d’exemple :
>>> nums = [5,4,3,2]
>>> nums.append(7)
>>> nums
[5, 4, 3, 2, 7]
>>> nums.pop()
7
>>> nums
[5, 4, 3, 2]
>>> nums.insert(0,9)
>>> nums
[9, 5, 4, 3, 2]Les listes Python prennent également en charge le découpage en tranches et les tests d’appartenance à l’aide de l’opérateur in:
>>> nums[1:4]
[5, 4, 3]
>>> 3 dans nums
VraiLa structure de données liste est non seulement flexible et simple, mais elle permet également de stocker des éléments de différents types de données. Python dispose également d’une structure de données de type tableau dédiée au stockage efficace d’éléments du même type de données. Nous en apprendrons plus à ce sujet plus loin dans ce guide.
Tuples
En Python, les tuples sont une autre structure de données intégrée populaire. Ils sont semblables aux listes Python, car vous pouvez les indexer en temps constant et les découper. Mais ils sont immuables, et vous ne pouvez donc pas les modifier sur place. L’extrait de code suivant explique ce qui précède à l’aide d’un exemple de tuple nums:
>>> nums = (5,4,3,2)
>>> nums<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x>
5
>>> nums[0:2]
(5, 4)
>>> 5 dans nums
Vrai
>>> nums<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x> = 7 # pas une opération valide !
Traceback (dernier appel le plus récent) :
Fichier "<stdin>", ligne 1, in <module>
TypeError : l'objet 'tuple' ne prend pas en charge l'affectation d'élémentsAinsi, lorsque vous souhaitez créer une collection immuable et être en mesure de la traiter efficacement, vous devriez envisager d’utiliser un tuple. Si vous souhaitez que la collection soit mutable, préférez plutôt utiliser une liste.
pour en savoir plus sur les similitudes et les différences entre les listes et les n-uplets de Python.
Tableaux
Les tableaux sont des structures de données moins connues en Python. Ils sont similaires aux listes Python en termes d’opérations qu’ils prennent en charge, telles que l’indexation en temps constant et l’insertion d’un élément à un index spécifique en temps linéaire.
Cependant, la principale différence entre les listes et les tableaux est que les tableaux stockent des éléments d’un seul type de données. Ils sont donc étroitement couplés et plus efficaces en termes de mémoire.
Pour créer un tableau, nous pouvons utiliser le constructeur array() du module array intégré. Le constructeur array() prend en charge une chaîne de caractères spécifiant le type de données des éléments et les éléments. Ici, nous créons nums_f, un tableau de nombres à virgule flottante :
>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])Vous pouvez indexer un tableau (comme les listes Python) :
>>> nums_f<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x>
1.5Les tableaux sont mutables, vous pouvez donc les modifier :
>>> nums_f<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x>=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])Mais vous ne pouvez pas modifier un élément pour qu’il soit d’un type de données différent:
>>> nums_f<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x>='zero'
Traceback (dernier appel le plus récent) :
Fichier "<stdin>", ligne 1, in <module>
TypeError : must be real number, not strChaînes de caractères
En Python, les chaînes de caractères sont des collections immuables de caractères Unicode. Contrairement à des langages de programmation comme le C, Python n’a pas de type de données dédié aux caractères. Un caractère est donc également une chaîne de longueur 1.
Comme indiqué, la chaîne est immuable :
>>> str_1 = 'python'
>>> str_1<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x> = 'c'
Traceback (dernier appel le plus récent) :
Fichier "<stdin>", ligne 1, in <module>
TypeError : l'objet 'str' ne supporte pas l'assignation d'élémentsLes chaînes Python prennent en charge le découpage des chaînes et un ensemble de méthodes pour les formater. Voici quelques exemples :
>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
pYTHON'
>>> str_1.swapcase()
'PYTHON'n’oubliez pas que toutes les opérations ci-dessus renvoient une copie de la chaîne de caractères et ne modifient pas la chaîne d’origine. Si vous êtes intéressé, consultez le guide des programmes Python sur les opérations sur les chaînes de caractères.
Ensembles
En Python, les ensembles sont des collections d’éléments uniques et hachables. Vous pouvez effectuer les opérations courantes sur les ensembles, telles que l’union, l’intersection et la différence :
>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}
>>> set_1.union(set_2)
{3, 4, 5, 6, 7}
>>> set_1.intersection(set_2)
{4, 7}
>>> set_1.difference(set_2)
{3, 5}Les ensembles sont mutables par défaut, vous pouvez donc ajouter de nouveaux éléments et les modifier :
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}📚 Lire Sets in Python : Un guide complet avec des exemples de code
Ensembles figés
Si vous voulez un ensemble immuable, vous pouvez utiliser un ensemble gelé. Vous pouvez créer un ensemble gelé à partir d’ensembles existants ou d’autres itérables.
>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})Comme frozenset_1 est un ensemble figé, nous rencontrons des erreurs si nous essayons d’ajouter des éléments (ou de le modifier) :
>>> frozenset_1.add(15)
Traceback (dernier appel le plus récent) :
Fichier "<stdin>", ligne 1, in <module>
AttributeError : l'objet 'frozenset' n'a pas d'attribut 'add'Dictionnaires
Un dictionnaire Python est fonctionnellement similaire à une carte de hachage. Les dictionnaires sont utilisés pour stocker des paires clé-valeur. Les clés du dictionnaire doivent pouvoir être hachées. Cela signifie que la valeur de hachage de l’objet ne change pas.
Vous pouvez accéder aux valeurs à l’aide des clés, insérer de nouveaux éléments et supprimer des éléments existants en temps constant. Il existe des méthodes de dictionnaire pour effectuer ces opérations.
>>> favoris = {'book':'Orlando'}
>>> favoris
{'book' : 'Orlando'}
>>> favoris['auteur']='Virginia Woolf'
>>> favoris
{'livre' : 'Orlando', 'auteur' : 'Virginia Woolf'}
>>> favoris.pop('auteur')
'Virginia Woolf'
>>> favoris
{'book' : 'Orlando'}OrderedDict
Bien qu’un dictionnaire Python fournisse une correspondance clé-valeur, il s’agit intrinsèquement d’une structure de données non ordonnée. Depuis Python 3.7, l’ordre d’insertion des éléments est préservé. Mais vous pouvez rendre cela plus explicite en utilisant OrderedDict du module collections.
Comme indiqué, un OrderedDict préserve l’ordre des clés :
>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='deux'
>>> od['third']='three' >>> od['third']='three' >>> od['third']='third'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])Défaut
Les erreurs de clé sont assez fréquentes lorsque l’on travaille avec des dictionnaires Python. Chaque fois que vous essayez d’accéder à une clé qui n’a pas été ajoutée au dictionnaire, vous rencontrez une exception KeyError.
Mais en utilisant defaultdict du module collections, vous pouvez gérer ce cas de manière native. Lorsque nous essayons d’accéder à une clé qui n’est pas présente dans le dictionnaire, la clé est ajoutée et initialisée avec les valeurs par défaut spécifiées par la fabrique par défaut.
>>> from collections import defaultdict
>>> prix = defaultdict(int)
>>> prix['carottes']
0Piles
La pile est une structure de données de type dernier entré-premier sorti (LIFO ). Nous pouvons effectuer les opérations suivantes sur une pile :
- Ajouter des éléments au sommet de la pile : opération “push
- Retirer des éléments du sommet de la pile : opération “pop”
Exemple illustrant le fonctionnement des opérations “push” et “pop” de la pile :
Comment implémenter une pile à l’aide d’une liste
En Python, nous pouvons implémenter la structure de données de la pile en utilisant une liste Python.
| Opération sur la pile | Opération équivalente sur une liste |
|---|---|
| Pousser au sommet de la pile | Ajouter à la fin de la liste à l’aide de la méthode append() |
| Retirer du sommet de la pile | Retirer et renvoyer le dernier élément à l’aide de la méthode pop() |
L’extrait de code ci-dessous montre comment émuler le comportement d’une pile à l’aide d’une liste Python :
>>> l_stk = []
>>> l_stk.append(4)
>>> l_stk.append(3)
>>> l_stk.append(7)
>>> l_stk.append(2)
>>> l_stk.append(9)
>>> l_stk
[4, 3, 7, 2, 9]
>>> l_stk.pop()
9Comment implémenter une pile à l’aide d’un deque
Une autre méthode pour mettre en œuvre une pile consiste à utiliser la fonction de que du module collections. Deque signifie “double-ended queue” (file d’attente à deux extrémités) et permet d’ajouter et de supprimer des éléments aux deux extrémités.
Pour émuler la pile, nous pouvons
- ajouter un élément à la fin de la file d’attente en utilisant
append(), et - retirer le dernier élément ajouté à l’aide de
pop().
>>> from collections import deque
>>> stk = deque()
>>> stk.append(4)
>>> stk.append(3)
>>> stk.append(7)
>>> stk.append(2)
>>> stk.append(9)
>>> stk
deque([4, 3, 7, 2,9])
>>> stk.pop()
9Files d’attente
La file d’attente est une structure de données de type premier entré-premier sorti (FIFO). Les éléments sont ajoutés à la fin de la file d’attente et retirés du début de la file d’attente (tête de file), comme indiqué :
Nous pouvons mettre en œuvre la structure de données de la file d’attente à l’aide d’un deque :
- ajouter des éléments à la fin de la file d’attente à l’aide de la méthode
append() - utiliser la méthode
popleft()pour retirer un élément du début de la file d’attente
>>> from collections import deque
>>> q = deque()
>>> q.append(4)
>>> q.append(3)
>>> q.append(7)
>>> q.append(2)
>>> q.append(9)
>>> q.popleft()
4Les tas
Dans cette section, nous allons discuter des tas binaires. Nous nous concentrerons sur les mini-superpositions.
Un mini tas est un arbre binaire complet. Voyons ce que signifie un arbre binaire complet :
- Un arbre binaire est une structure de données arborescente dans laquelle chaque nœud a au plus deux nœuds enfants, de sorte que chaque nœud est inférieur à son enfant.
- Le terme ” complet ” signifie que l’arbre est entièrement rempli, à l’exception, peut-être, du dernier niveau. Si le dernier niveau est partiellement rempli, il est rempli de gauche à droite.
Parce que chaque nœud a au plus deux nœuds enfants. Et qu’il satisfait également à la propriété selon laquelle il est plus petit que son enfant, la racine est l’élément minimum d’un mini tas.
Voici un exemple de mini tas :
En Python, le module heapq nous aide à construire des tas et à effectuer des opérations sur le tas. Importons les fonctions nécessaires du module heapq:
>>> from heapq import heapify, heappush, heappopSi vous disposez d’une liste ou d’un autre itérable, vous pouvez construire un tas à partir de celui-ci en appelant heapify():
>>> nums = [11,8,12,3,7,9,10]
>>> heapify(nums)
Vous pouvez indexer le premier élément pour vérifier qu’il s’agit de l’élément minimum :
>>> nums<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x>
3Maintenant, si vous insérez un élément dans le tas, les nœuds seront réorganisés de manière à satisfaire la propriété min heap.
>>> heappush(nums,1)
Comme nous avons inséré 1 (1 < 3), nous voyons que nums<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x> renvoie 1 qui est maintenant l’élément minimum (et le noeud racine).
>>> nums<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x>
1Vous pouvez supprimer des éléments du tas minimal en appelant la fonction heappop(), comme indiqué ci-dessous :
>>> while nums :
... print(heappop(nums))
...# Sortie
1
3
7
8
9
10
11
12Les tas maximaux en Python
Maintenant que vous connaissez les min heaps, pouvez-vous deviner comment nous pouvons implémenter un max heap ?
Eh bien, nous pouvons convertir une implémentation min heap en max heap en multipliant chaque nombre par -1. Les nombres négatifs disposés dans un min heap sont équivalents aux nombres originaux disposés dans un max heap.
Dans l’implémentation Python, nous pouvons multiplier les éléments par -1 lorsque nous ajoutons un élément au tas en utilisant heappush():
>>> maxHeap = []
>>> heappush(maxHeap,-2)
>>> heappush(maxHeap,-5)
>>> heappush(maxHeap,-7)Le nœud racine – multiplié par -1 – sera l’élément maximal.
>>> -1*maxHeap<x><x><x><x><x><x><x><x><x>[0]</x></x></x></x></x></x></x></x></x>
7Lorsque vous retirez des éléments du tas, utilisez heappop() et multipliez par -1 pour récupérer la valeur d’origine :
>>> while maxHeap :
... print(-1*heappop(maxHeap))
...# Sortie
7
5
2Les files d’attente prioritaires
Terminons la discussion en apprenant à connaître la structure de données des files d’attente prioritaires en Python.
Nous le savons : Dans une file d’attente, les éléments sont retirés dans l’ordre dans lequel ils sont entrés dans la file. Mais une file d’attente prioritaire sert les éléments par priorité, ce qui est très utile pour des applications telles que l’ordonnancement. Ainsi, à tout moment, l’élément ayant la priorité la plus élevée est renvoyé.
Nous pouvons utiliser des clés pour définir la priorité. Ici, nous utiliserons des poids numériques pour les clés.
Comment implémenter les files d’attente prioritaires en utilisant Heapq
Voici la mise en œuvre d’une file d’attente prioritaire à l’aide de Heapq et d’une liste Python :
>>> from heapq import heappush,heappop
>>> pq = []
>>> heappush(pq,(2,'write'))
>>> heappush(pq,(1, 'read'))
>>> heappush(pq,(3, 'code'))
>>> while pq :
... print(heappop(pq))
...Lors du retrait d’éléments, la file d’attente sert d’abord l’élément le plus prioritaire (1, "read"), suivi de (2, "write") puis de (3, "code").
# Sortie
(1, 'read')
(2, 'write')
(3, 'code')Comment implémenter les files d’attente prioritaires à l’aide de PriorityQueue
Pour mettre en œuvre une file d’attente prioritaire, nous pouvons également utiliser la classe PriorityQueue du module queue. Cette classe utilise également le tas en interne.
Voici l’implémentation équivalente de la file d’attente prioritaire à l’aide de PriorityQueue:
>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1, 'read'))
>>> pq.put((3, 'code'))
>>> pq
<queue.PriorityQueue objet à 0x00BDE730>
>>> while not pq.empty() :
... print(pq.get())
...# Sortie
(1, 'read')
(2, "écriture")
(3, 'code')Résumé
Dans ce tutoriel, vous avez appris à connaître les différentes structures de données intégrées à Python. Nous avons également passé en revue les différentes opérations prises en charge par ces structures de données, ainsi que les méthodes intégrées permettant d’effectuer ces opérations.
Nous avons ensuite abordé d’autres structures de données telles que les piles, les files d’attente et les files d’attente prioritaires, ainsi que leur implémentation en Python à l’aide des fonctionnalités du module collections.
Ensuite, consultez la liste des projets Python conviviaux pour les débutants.