CKTIS / Python
Ajouter un élément à droite d’une `deque`
`collections.deque.append` ajoute un élément à droite d’une file à deux extrémités. Dans cet exemple de fenêtre glissante, la file monotone stocke les indices plutôt que les valeurs elles-mêmes.
Version : Python 3.12
Syntaxe
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneEn Python 3.12, collections.deque.append est une méthode du type deque du module collections. Dans d.append(x), x est un argument positionnel. La méthode ajoute x à droite comme un seul élément, même si x est itérable. Elle modifie d sur place et renvoie None : n’écrivez pas d = d.append(x). Utilisez appendleft(x) pour ajouter à gauche et extend(iterable) pour ajouter à droite les éléments d’un itérable.
list.append et deque.append ajoutent tous deux un élément en fin de séquence. Pour une file, l’intérêt de deque est que les ajouts et retraits aux deux extrémités prennent un temps d’environ O(1), alors que list.pop(0) décale les éléments restants et prend un temps O(n).
Si maxlen est omis ou vaut None, la deque n’a pas de limite de longueur fixe. Lorsqu’une deque de maxlen positif est pleine, append supprime automatiquement l’élément le plus à gauche sans lever d’exception pour cause de saturation. Avec maxlen=0, aucun élément n’est conservé. L’exemple utilise une deque sans limite : c’est la position d’un indice dans les données, et non le nombre de candidats, qui détermine quand il sort de la fenêtre.
Pour trouver les maxima d’une fenêtre glissante, retirez à gauche avec popleft() les indices sortis de la fenêtre. Retirez ensuite à droite avec pop() les indices dont la valeur est inférieure ou égale à la nouvelle. À valeur égale, l’indice le plus récent reste plus longtemps dans la fenêtre. Appelez ensuite candidates.append(i) sur la deque : stockez l’indice i et utilisez values[i] pour les comparaisons. Les valeurs aux indices restants décroissent de gauche à droite ; une fois la fenêtre complète, values[candidates[0]] est donc le maximum.
Exemples
from collections import deque
values = [4, 2, 2, 5, 3, 1, 2]
width = 3
candidates = deque()
maxima = []
for i, value in enumerate(values):
while candidates and candidates[0] <= i - width:
candidates.popleft()
while candidates and values[candidates[-1]] <= value:
candidates.pop()
candidates.append(i)
if i >= width - 1:
maxima.append(values[candidates[0]])
print(maxima)
Résultat
[4, 5, 5, 5, 3]
À l’arrivée du second `2`, son indice `2` remplace l’indice `1`. Dans la dernière fenêtre, l’indice `3`, associé à la valeur `5`, sort de la fenêtre et est retiré à gauche. Le maximum devient `3`.
Leçons associées
- Python · Leçon 41 · Avancé · Version : 5