En Python, vous pouvez utiliser collections.deque pour gérer efficacement les données sous forme de file d’attente, de pile et de deque (file d’attente à double extrémité, liste liée tête-queue).
Il est également possible d’utiliser la liste intégrée comme file d’attente, pile ou deque, mais collections.deque est plus efficace car la suppression ou l’ajout au premier élément de la liste est lent.
Notez que deque a l’inconvénient de ralentir l’accès aux éléments du milieu.
Cet article décrit le contenu suivant.
- Complexité de la liste et des collections.deque
- Comment utiliser collections.deque
- Créer un objet deque
- Ajouter un élément :
append(), appendleft(), extend(), extendleft(), insert() - Supprimer un élément :
pop(), popleft(), remove(), clear() - Faites pivoter le deque :
rotate() - Obtenir la valeur et l’index :
[], index() - Autres opérations
- Limiter la longueur maximale avec maxlen
- Utiliser deque comme file d’attente (FIFO)
- Utiliser deque comme pile (LIFO)
- Utiliser deque comme deque (file d’attente double)
Consultez l’article suivant sur l’ajout et la suppression d’éléments pour la liste.
Complexité de la liste et des collections.deque
La complexité de list et deque pour diverses opérations est résumée dans le Wiki officiel.
Dans la liste, les opérations telles que pop(0) pour supprimer et renvoyer le premier élément, insert(0, v) pour ajouter un élément à la tête, etc. nécessitent O(n), mais dans deque, append(), appendleft( ), pop() et popleft() pour ajouter et supprimer les premier et dernier éléments peuvent tous être effectués avec O(1).
Il est également mentionné dans la documentation officielle.
Deques prend en charge les ajouts et les pops à mémoire thread-safe et efficaces de chaque côté du deque avec approximativement les mêmes performances O(1) dans les deux sens.
Bien que les objets de liste prennent en charge des opérations similaires, ils sont optimisés pour les opérations rapides de longueur fixe et entraînent des coûts de déplacement de mémoire O(n) pour les opérations pop(0) et insert(0, v) qui modifient à la fois la taille et la position de la représentation sous-jacente des données. .
collections – objets deque — Types de données de conteneur — Documentation Python 3.9.7
En revanche, l’accès aux éléments du milieu par [] est plus rapide avec list.
L’accès indexé est O(1) aux deux extrémités mais ralentit à O(n) au milieu. Pour un accès aléatoire rapide, utilisez plutôt des listes.
collections – objets deque — Types de données de conteneur — Documentation Python 3.9.7
Par conséquent, une directive approximative est la suivante.
- Ajouter, supprimer et accéder aux éléments uniquement aux deux extrémités -> deque
- Accéder fréquemment aux éléments du milieu -> liste
Si vous souhaitez traiter les données explicitement comme une file d’attente, une pile ou deque, vous devez utiliser deque.
Cependant, selon l’environnement et les conditions, si le nombre d’éléments n’est que de quelques centaines ou quelques milliers, il n’y a pas de différence perceptible de vitesse de traitement entre list et deque. À moins que vous ne souhaitiez réduire le temps de traitement d’une milliseconde, il n’y a aucun problème si vous utilisez la liste dans la plupart des cas.
Si vous envisagez lequel utiliser dans un environnement ou une condition fixe, vous pouvez utiliser le module timeit pour mesurer le temps de traitement réel.
Comment utiliser collections.deque
Créer un objet deque
Créez un objet deque avec deque().
Si aucun argument n’est spécifié, un objet deque vide est créé. Si un objet itérable tel que list est spécifié, un objet deque avec ses éléments est créé.
from collections import deque
d = deque()
print(d)
# deque([])
print(type(d))
# <class 'collections.deque'>
d = deque(['m', 'n'])
print(d)
# deque(['m', 'n'])
Vous pouvez également limiter la longueur maximale (nombre maximal d’éléments) avec le deuxième argument, maxlen. Les détails sont décrits plus tard.
Ajouter un élément :append(), appendleft(), extend(), extendleft(), insert()
append() ajoute un élément sur le côté droit, appendleft() sur le côté gauche.
d.append('o')
print(d)
# deque(['m', 'n', 'o'])
d.appendleft('l')
print(d)
# deque(['l', 'm', 'n', 'o'])
extend() ajoute tous les éléments d’un objet itérable, tel que list, sur le côté droit. expandleft() les ajoute sur le côté gauche. Notez qu’avec expandleft(), l’ordre des éléments de l’itérable spécifié est inversé et concaténé.
d.extend(['p', 'q'])
print(d)
# deque(['l', 'm', 'n', 'o', 'p', 'q'])
d.extendleft(['k', 'j'])
print(d)
# deque(['j', 'k', 'l', 'm', 'n', 'o', 'p', 'q'])
insert() ajoute un élément au milieu. Spécifiez la position comme premier argument et la valeur à ajouter comme deuxième argument. Vous pouvez spécifier une position à partir de la fin avec une valeur négative pour le premier argument. Si une position inexistante (hors plage) est spécifiée, l’élément est ajouté au début ou à la fin.
insert() a été ajouté dans Python 3.5.
d.insert(3, 'XXX')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'q'])
d.insert(-1, 'YYY')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q'])
d.insert(100, 'ZZZ')
print(d)
# deque(['j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])
d.insert(-100, 'XYZ')
print(d)
# deque(['XYZ', 'j', 'k', 'l', 'XXX', 'm', 'n', 'o', 'p', 'YYY', 'q', 'ZZZ'])
Supprimer un élément :pop(), popleft(), remove(), clear()
pop() supprime un élément du côté droit, popleft() supprime un élément du côté gauche et renvoie sa valeur. Contrairement à pop() dans la liste, il est impossible de spécifier la position en argument.
d = deque(['a', 'b', 'c', 'b', 'd'])
print(d.pop())
# d
print(d)
# deque(['a', 'b', 'c', 'b'])
print(d.popleft())
# a
print(d)
# deque(['b', 'c', 'b'])
remove() supprime le premier élément dont la valeur est égale à l’argument spécifié. Même si deux éléments ou plus correspondent à la valeur spécifiée, seul le premier élément est supprimé. Si aucun élément ne correspond à la valeur spécifiée, une erreur est levée.
d.remove('b')
print(d)
# deque(['c', 'b'])
# d.remove('X')
# ValueError: deque.remove(x): x not in deque
clear() supprime tous les éléments. Cela devient une deque vide.
d.clear()
print(d)
# deque([])
Pour un deque vide, pop() et popleft() génèrent une erreur. clear() ne génère pas d’erreur.
# d.pop()
# IndexError: pop from an empty deque
# d.popleft()
# IndexError: pop from an empty deque
d.clear()
print(d)
# deque([])
Faites pivoter le deque :rotate()
deque a une méthode rotate() qui n’est pas dans la liste. Par défaut, les éléments sont pivotés un par un vers la droite.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate()
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])
Si une valeur entière est spécifiée, elle pivote vers la droite de ce nombre. Si une valeur négative est spécifiée, il tourne vers la gauche.
Une valeur supérieure au nombre d’éléments peut également être spécifiée.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(2)
print(d)
# deque(['d', 'e', 'a', 'b', 'c'])
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(-1)
print(d)
# deque(['b', 'c', 'd', 'e', 'a'])
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate(6)
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])
Obtenir la valeur et l’index :[], index()
Comme pour la liste, vous pouvez obtenir la valeur d’un élément en spécifiant son index dans []. Vous pouvez également spécifier la position à partir de la fin avec une valeur négative. Vous pouvez également modifier la valeur.
d = deque(['a', 'b', 'c', 'd', 'e'])
print(d[0])
# a
print(d[-1])
# e
d[2] = 'X'
print(d)
# deque(['a', 'b', 'X', 'd', 'e'])
Slice : n’est pas disponible directement, mais peut être remplacé par islice() de la bibliothèque standard itertools.
# print(d[2:4])
# TypeError: sequence index must be integer, not 'slice'
import itertools
print(deque(itertools.islice(d, 2, 4)))
# deque(['X', 'd'])
Avec index(), vous pouvez obtenir l’index du premier élément qui correspond à la valeur spécifiée en argument. Si une valeur inexistante est spécifiée, une erreur est générée.
index() a été ajouté dans Python 3.5.
d = deque(['a', 'b', 'c', 'c', 'd'])
print(d.index('c'))
# 2
# print(d.index('x'))
# ValueError: 'x' is not in deque
Autres opérations
De plus, diverses autres opérations sont possibles ainsi que la liste.
Obtenez le nombre d’éléments avec la fonction intégrée len().
d = deque(['a', 'a', 'b', 'c'])
print(len(d))
# 4
Comptez le nombre d’éléments égal à la valeur spécifiée par count().
print(d.count('a'))
# 2
print(d.count('x'))
# 0
L’opérateur in est utilisé pour vérifier si un élément existe.
print('b' in d)
# True
print('x' in d)
# False
Inversez l’ordre avec la méthode reverse() ou la fonction intégrée reversed(). La méthode reverse() inverse l’objet d’origine lui-même et reversed() renvoie l’itérateur inversé.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.reverse()
print(d)
# deque(['e', 'd', 'c', 'b', 'a'])
d = deque(['a', 'b', 'c', 'd', 'e'])
print(deque(reversed(d)))
# deque(['e', 'd', 'c', 'b', 'a'])
Vous pouvez le convertir en liste ou tuple avec list() ou tuple().
d = deque(['a', 'b', 'c'])
l = list(d)
print(l)
# ['a', 'b', 'c']
print(type(l))
# <class 'list'>
Limiter la longueur maximale avec maxlen
Si le deuxième argument maxlen de deque() est spécifié, la longueur maximale (le nombre maximal d’éléments) peut être limitée. La valeur par défaut de maxlen est None, ce qui signifie qu’il n’y a pas de limite de longueur.
from collections import deque
d = deque(['l', 'm', 'n'], 3)
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
Si maxlen est spécifié et que deque est plein, les éléments sont ignorés du côté opposé lors de l’ajout d’éléments.
Le comportement de append(), appendleft(), extend() et extendleft() est le suivant.
d.append('o')
print(d)
# deque(['m', 'n', 'o'], maxlen=3)
d.appendleft('l')
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
d.extend(['o', 'p'])
print(d)
# deque(['n', 'o', 'p'], maxlen=3)
d.extendleft(['m', 'l'])
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
Avec insert(), une erreur est levée même lors de l’ajout à la fin.
# d.insert(0, 'XXX')
# IndexError: deque already at its maximum size
Si le nombre d’éléments n’atteint pas maxlen, il peut être ajouté avec insert().
print(d.pop())
# n
print(d)
# deque(['l', 'm'], maxlen=3)
d.insert(1, 'XXX')
print(d)
# deque(['l', 'XXX', 'm'], maxlen=3)
Le maxlen peut être obtenu en tant qu’attribut, mais il est en lecture seule et ne peut pas être modifié.
print(d.maxlen)
# 3
# d.maxlen = 5
# AttributeError: attribute 'maxlen' of 'collections.deque' objects is not writable
Utiliser deque comme file d’attente (FIFO)
Une file d’attente contient des données dans une structure FIFO (First In, First Out). Dans une file d’attente, l’insertion de données est appelée mise en file d’attente et la suppression de données est appelée retrait de la file d’attente.
Pour utiliser deque comme file d’attente, utilisez append() comme file d’attente et popleft() comme dequeue.
from collections import deque
d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])
d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])
print(d.popleft())
# a
print(d)
# deque(['b', 'c', 'd'])
Utiliser deque comme pile (LIFO)
Une pile contient des données dans une structure LIFO (Last In, First Out). Dans une pile, l’insertion de données s’appelle push et la suppression de données s’appelle pop.
Pour utiliser deque comme pile, utilisez append() comme push et pop() comme pop.
from collections import deque
d = deque(['a', 'b', 'c'])
print(d)
# deque(['a', 'b', 'c'])
d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])
print(d.pop())
# d
print(d)
# deque(['a', 'b', 'c'])
Utiliser deque comme deque (file d’attente double)
Une deque (file d’attente à double extrémité) est une file d’attente où des éléments peuvent être ajoutés ou supprimés aux deux extrémités (tête et queue).
Comme dans les exemples précédents, deque vous permet d’ajouter et de supprimer des éléments des deux côtés avec append(), appendleft(), pop() et popleft().