CKTIS / Python
Añadir un elemento al extremo derecho de una `deque`
`collections.deque.append` añade un elemento al extremo derecho de una cola de doble extremo. En este ejemplo de ventana deslizante, la cola monótona guarda índices en lugar de los valores.
Versión: Python 3.12
Sintaxis
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneEn Python 3.12, collections.deque.append es un método del tipo deque del módulo collections. En d.append(x), pasa x como argumento posicional. El método añade x a la derecha como un solo elemento, incluso si x es iterable. Modifica d en el sitio y devuelve None, así que no escribas d = d.append(x). Usa appendleft(x) para añadir a la izquierda o extend(iterable) para añadir a la derecha los elementos de un iterable.
Tanto list.append como deque.append añaden al final. Para una cola, la diferencia es que una deque permite añadir y quitar elementos en ambos extremos en un tiempo de aproximadamente O(1), mientras que list.pop(0) desplaza los elementos restantes y tarda O(n).
Si omites maxlen o le das el valor None, la deque no tiene un límite de longitud fijo. Cuando una deque con un maxlen positivo está llena, append descarta automáticamente el elemento del extremo izquierdo en vez de lanzar una excepción por estar llena. Con maxlen=0 no se conserva ningún elemento. El ejemplo usa una deque sin límite: lo que determina si un índice sale de la ventana es su posición en la entrada, no la cantidad de candidatos.
Para hallar los máximos de una ventana deslizante, elimina con popleft() los índices de la izquierda que ya están fuera de la ventana. Después usa pop() para eliminar por la derecha los índices cuyos valores sean menores o iguales que el nuevo valor. Si los valores coinciden, el índice más reciente permanece más tiempo en la ventana. Llama entonces a candidates.append(i) sobre la deque: guarda el índice i y usa values[i] para comparar. Los valores de los índices restantes decrecen de izquierda a derecha, de modo que values[candidates[0]] es el máximo cuando la ventana está completa.
Ejemplos
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)
Resultado
[4, 5, 5, 5, 3]
Al llegar el segundo `2`, su índice `2` sustituye al índice `1`. En la última ventana, el índice `3`, cuyo valor es `5`, queda fuera y se elimina por la izquierda. El máximo pasa a ser `3`.
Lecciones relacionadas
- Python · Lección 41 · Avanzado · Versión: 5