Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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 None

In 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

Fonti