CKTIS / Python
Aggiungere un elemento a destra di una `deque`
`collections.deque.append` aggiunge un elemento all’estremità destra di una coda a doppia estremità. In questo esempio con una finestra scorrevole, la coda monotona memorizza gli indici anziché i valori.
Versione: Python 3.12
Sintassi
d.append(x) # d is a collections.deque; x is passed positionally; returns NoneIn Python 3.12, collections.deque.append è un metodo del tipo deque del modulo collections. In d.append(x), passa x come argomento posizionale. Il metodo aggiunge x a destra come singolo elemento, anche se x è iterabile. Modifica direttamente d e restituisce None, quindi non scrivere d = d.append(x). Usa appendleft(x) per aggiungere a sinistra oppure extend(iterable) per aggiungere a destra gli elementi di un iterabile.
Sia list.append sia deque.append aggiungono in fondo. Per una coda, la differenza è che una deque consente aggiunte e rimozioni a entrambe le estremità in tempo circa O(1), mentre list.pop(0) sposta gli elementi rimanenti e richiede tempo O(n).
Se maxlen è omesso o vale None, la deque non ha un limite di lunghezza fisso. Quando una deque con maxlen positivo è piena, append scarta automaticamente l’elemento più a sinistra senza sollevare un’eccezione per il raggiungimento del limite. Con maxlen=0 non viene conservato alcun elemento. L’esempio usa una deque senza limite: è la posizione di un indice nei dati in ingresso, non il numero di candidati, a stabilire quando esce dalla finestra.
Per trovare i massimi di una finestra scorrevole, rimuovi con popleft() gli indici a sinistra che sono usciti dalla finestra. Poi rimuovi con pop() gli indici a destra i cui valori sono minori o uguali al nuovo valore. A parità di valore, l’indice più recente resta più a lungo nella finestra. Quindi chiama candidates.append(i) sulla deque: salva l’indice i e usa values[i] per i confronti. I valori agli indici rimanenti decrescono da sinistra a destra, quindi values[candidates[0]] è il massimo quando la finestra è completa.
Esempi
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)
Risultato
[4, 5, 5, 5, 3]
Quando arriva il secondo `2`, il suo indice `2` sostituisce l’indice `1`. Nell’ultima finestra, l’indice `3`, associato al valore `5`, esce dalla finestra e viene rimosso da sinistra. Il massimo diventa `3`.
Lezioni correlate
- Python · Lezione 41 · Avanzato · Versione: 5