Exploration des Structures de Données en Python
Cherchez-vous à enrichir votre expertise en programmation avec des structures de données? Commencez dès maintenant à explorer les structures de données offertes par Python.
L’apprentissage d’un nouveau langage de programmation implique la compréhension des types de données fondamentaux et des structures de données natives prises en charge. Ce guide sur les structures de données en Python abordera les aspects suivants:
- Les avantages des structures de données.
- Les structures de données intégrées de Python, telles que les listes, les tuples, les dictionnaires et les ensembles.
- La mise en œuvre de types de données abstraits comme les piles et les files d’attente.
C’est parti!
Pourquoi les Structures de Données sont-elles Utiles?
Avant d’examiner les différentes structures de données, comprenons comment leur utilisation peut s’avérer bénéfique:
- Traitement efficace des données: Choisir une structure de données adéquate permet de manipuler les données avec une meilleure efficacité. Par exemple, si vous avez besoin de stocker une collection d’éléments de même type (avec des recherches rapides et un fort couplage), un tableau pourrait être approprié.
- Gestion optimisée de la mémoire: Dans les projets de grande envergure, le stockage des mêmes données peut être plus économe en mémoire selon la structure de données utilisée. Par exemple, les listes et les tuples peuvent stocker des collections de données de différents types en Python. Cependant, si la collection ne doit pas être modifiée, un tuple occupera généralement moins de mémoire qu’une liste.
- Code mieux organisé: L’emploi de la structure de données adaptée à une tâche spécifique améliore l’organisation du code. Les autres développeurs s’attendront à ce que vous utilisiez des structures de données spécifiques en fonction du comportement désiré. Par exemple, si vous avez besoin d’une association clé-valeur avec des recherches et des insertions rapides, un dictionnaire est une excellente option.
Listes
Les listes sont les structures de données de choix en Python pour créer des tableaux dynamiques, que ce soit pour des entretiens de codage ou des cas d’utilisation courants.
Les listes Python sont des types de données conteneurs modifiables et dynamiques, ce qui signifie que vous pouvez ajouter et supprimer des éléments directement, sans avoir besoin de créer une copie.
Lors de l’utilisation de listes Python :
- L’indexation et l’accès à un élément spécifique sont des opérations en temps constant.
- L’ajout d’un élément à la fin de la liste est une opération en temps constant.
- L’insertion d’un élément à une position spécifique est une opération en temps linéaire.
Un ensemble de méthodes de liste permet de réaliser efficacement les tâches courantes. Le code ci-dessous illustre 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 supportent également le découpage et les tests d’appartenance avec l’opérateur in:
>>> nums[1:4]
[5, 4, 3]
>>> 3 in nums
True
La structure de données de la liste est non seulement flexible et simple, mais elle permet aussi de stocker des éléments de types différents. Python possède aussi une structure de données dédiée, le tableau, pour stocker efficacement des éléments de même type. Nous l’aborderons plus loin dans ce guide.
Tuples
Les tuples sont une autre structure de données intégrée populaire en Python. Similaires aux listes, ils permettent un accès par index en temps constant et le découpage. Cependant, ils sont immuables, il n’est donc pas possible de les modifier directement. L’exemple suivant avec un tuple `nums` illustre ceci:
>>> nums = (5,4,3,2)
>>> nums[0]
5
>>> nums[0:2]
(5, 4)
>>> 5 in nums
True
>>> nums[0] = 7 # opération invalide!
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
Ainsi, lorsqu’une collection immuable doit être traitée de manière efficace, un tuple est une bonne option. Si la collection doit être modifiable, une liste sera préférable.
📋 Découvrez les similarités et différences entre les listes Python et les tuples.
Tableaux
Les tableaux sont moins connus en Python. Ils partagent des similarités avec les listes Python en termes d’opérations supportées, comme l’accès par index en temps constant et l’insertion d’éléments à des positions spécifiques en temps linéaire.
Toutefois, 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, ce qui les rend étroitement couplés et économes en mémoire.
Pour créer un tableau, on utilise le constructeur `array()` du module intégré `array`. Il prend en argument une chaîne spécifiant le type de données des éléments et les éléments eux-mêmes. 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])
On peut indexer un tableau (comme pour les listes Python):
>>> nums_f[0]
1.5
Les tableaux sont modifiables:
>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])
Cependant, on ne peut pas modifier un élément pour lui attribuer un type de données différent:
>>> nums_f[0]='zero'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: must be real number, not str
Chaînes de Caractères
En Python, les chaînes sont des collections immuables de caractères Unicode. Contrairement à des langages comme le C, Python ne possède pas de type de données caractère dédié. Un caractère est donc une chaîne de longueur un.
Comme mentionné, les chaînes sont immuables:
>>> str_1 = 'python'
>>> str_1[0] = 'c'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment
Les chaînes Python supportent le découpage et un ensemble de méthodes pour les formater, comme le montrent ces exemples:
>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
'PYTHON'
>>> str_1.swapcase()
'PYTHON'
⚠ N’oubliez pas que toutes ces opérations retournent une copie de la chaîne et ne modifient pas la chaîne d’origine. Pour plus d’informations, consultez le guide sur les opérations de chaîne en Python.
Ensembles
Les ensembles en Python sont des collections d’éléments uniques et hachables. On peut effectuer des opérations d’ensemble courantes comme 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 modifiables par défaut, on peut y ajouter de nouveaux éléments:
>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}
📚 Ensembles en Python: guide complet avec exemples de code
FrozenSets
Si l’on souhaite un ensemble immuable, on peut utiliser un `frozenset`. On peut créer un `frozenset` à 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 gelé, toute tentative d’y ajouter des éléments (ou de le modifier d’une autre façon) lèvera une erreur:
>>> frozenset_1.add(15)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'
Dictionnaires
Un dictionnaire Python est similaire à une table de hachage. On l’utilise pour stocker des paires clé-valeur. Les clés doivent être hachables, ce qui signifie que la valeur de hachage de l’objet ne doit pas changer.
Il est possible d’accéder aux valeurs à l’aide des clés, d’insérer de nouveaux éléments et de supprimer des éléments existants en temps constant grâce à des méthodes spécifiques:
>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}
>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}
>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}
OrderedDict
Bien que les dictionnaires Python fournissent une association clé-valeur, ils sont par nature des structures de données non ordonnées. Depuis Python 3.7, l’ordre d’insertion est conservé, mais pour le rendre plus explicite, on peut utiliser `OrderedDict` du module `collections`.
Comme son nom l’indique, un `OrderedDict` préserve l’ordre des clés:
>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])
Defaultdict
Les erreurs de clé sont fréquentes lorsque l’on travaille avec des dictionnaires Python. Si l’on essaie d’accéder à une clé qui n’a pas été ajoutée au dictionnaire, une exception `KeyError` sera levée.
Toutefois, on peut gérer ce cas nativement en utilisant `defaultdict` du module `collections`. Lorsque l’on essaie d’accéder à une clé absente, elle 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
>>> prices = defaultdict(int)
>>> prices['carrots']
0
Piles
Une pile est une structure de données de type LIFO (dernier entré, premier sorti). Les opérations suivantes sont possibles:
- Ajouter des éléments au sommet de la pile (opération *push*).
- Supprimer des éléments du sommet de la pile (opération *pop*).
Un exemple illustrant le fonctionnement des opérations *push* et *pop*:
Comment implémenter une pile à l’aide d’une liste
En Python, on peut implémenter une pile en utilisant une liste. Les opérations sur la pile sont équivalentes aux opérations suivantes sur la liste :
| Opération sur la pile | Opération équivalente sur la liste |
| Ajouter au sommet de la pile | Ajouter à la fin de la liste avec `append()` |
| Retirer le sommet de la pile | Retirer et retourner le dernier élément avec `pop()` |
Le code suivant montre comment émuler une pile avec 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()
9
Comment implémenter une pile à l’aide d’un Deque
Une autre façon d’implémenter une pile est d’utiliser un `deque` du module `collections`. `Deque` signifie *double-ended queue* (file d’attente double) et permet d’ajouter et de supprimer des éléments des deux extrémités.
Pour émuler une pile, il faut:
- Ajouter à la fin du `deque` avec `append()`.
- Retirer le dernier élément avec `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()
9
Files d’Attente
Une file d’attente est une structure de données FIFO (premier entré, premier sorti). Les éléments sont ajoutés à la fin de la file et retirés au début (tête de la file):
On peut implémenter une file d’attente avec un `deque`:
- Ajouter des éléments à la fin avec `append()`.
- Retirer l’élément au début avec `popleft()`.
>>> from collections import deque
>>> q = deque()
>>> q.append(4)
>>> q.append(3)
>>> q.append(7)
>>> q.append(2)
>>> q.append(9)
>>> q.popleft()
4
Tas
Cette section est consacrée aux tas binaires, en particulier les tas min.
Un tas min est un arbre binaire complet. Décomposons cette définition:
- Un arbre binaire est une structure de données arborescente où chaque nœud a au maximum deux enfants, et où chaque nœud est inférieur à ses enfants.
- Complet signifie que l’arbre est complètement rempli, à l’exception éventuellement du dernier niveau. Si le dernier niveau est partiellement rempli, il est rempli de gauche à droite.
Comme chaque nœud a au maximum deux enfants et qu’il est inférieur à ses enfants, la racine est l’élément minimal dans un tas min.
Voici un exemple de tas min:
En Python, le module `heapq` permet de créer des tas et d’effectuer des opérations dessus. Importons les fonctions nécessaires de `heapq`:
>>> from heapq import heapify, heappush, heappop
Si l’on possède une liste ou un autre itérable, on peut en créer un tas en appelant `heapify()`:
>>> nums = [11,8,12,3,7,9,10]
>>> heapify(nums)
On peut vérifier que le premier élément (la racine) est bien l’élément minimum:
>>> nums[0]
3
Lors de l’insertion d’un élément dans le tas, les nœuds seront réorganisés de manière à respecter la propriété du tas min.
>>> heappush(nums,1)
Comme on a inséré 1 (1 < 3), on constate que `nums[0]` retourne maintenant 1 (qui est devenu la racine).
>>> nums[0]
1
Pour supprimer des éléments du tas min, il faut appeler la fonction `heappop()`:
>>> while nums:
... print(heappop(nums))
...
# Output
1
3
7
8
9
10
11
12
Tas maximum en Python
Maintenant que vous connaissez les tas min, comment implémenter un tas max?
On peut convertir un tas min en tas max en multipliant chaque nombre par -1. Les nombres négatifs placés dans un tas min sont équivalents aux nombres originaux placés dans un tas max.
Dans l’implémentation Python, il suffit de multiplier les éléments par -1 lors de l’ajout au tas avec `heappush()`:
>>> maxHeap = []
>>> heappush(maxHeap,-2)
>>> heappush(maxHeap,-5)
>>> heappush(maxHeap,-7)
Le nœud racine, multiplié par -1, sera l’élément maximum:
>>> -1*maxHeap[0]
7
Lors de la suppression d’éléments, il faut utiliser `heappop()` et multiplier par -1 pour retrouver la valeur d’origine:
>>> while maxHeap:
... print(-1*heappop(maxHeap))
...
# Output
7
5
2
Files d’Attente Prioritaires
Terminons notre exploration en examinant les files d’attente prioritaires en Python.
Dans une file d’attente classique, les éléments sont retirés dans l’ordre où ils sont entrés. Une file d’attente prioritaire, elle, sert les éléments en fonction de leur priorité. Ceci est utile pour des applications comme la planification. Ainsi, à tout moment, l’élément avec la priorité la plus élevée est renvoyé.
On peut utiliser des clés pour définir la priorité, par exemple des poids numériques.
Comment implémenter des files d’attente prioritaires avec Heapq
Voici l’implémentation d’une file d’attente prioritaire avec `heapq` et 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 de la suppression d’éléments, la file d’attente sert d’abord l’élément de plus haute priorité (1, ‘read’), puis (2, ‘write’), et enfin (3, ‘code’).
# Output
(1, 'read')
(2, 'write')
(3, 'code')
Comment implémenter des files d’attente prioritaires avec PriorityQueue
Pour implémenter une file d’attente prioritaire, on peut aussi utiliser la classe `PriorityQueue` du module `queue`. Elle utilise également un tas en interne.
Voici l’implémentation équivalente avec `PriorityQueue`:
>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1,'read'))
>>> pq.put((3,'code'))
>>> pq
<queue.PriorityQueue object at 0x00BDE730>
>>> while not pq.empty():
... print(pq.get())
...
# Output
(1, 'read')
(2, 'write')
(3, 'code')
En Résumé
Dans ce tutoriel, nous avons exploré diverses structures de données intégrées de Python. Nous avons examiné les opérations qu’elles supportent et les méthodes disponibles pour cela.
Nous avons également étudié d’autres structures de données telles que les piles, les files d’attente et les files d’attente prioritaires, et leur implémentation Python à l’aide des fonctionnalités du module `collections`.
Pour aller plus loin, découvrez notre liste de projets Python adaptés aux débutants.