In Python, puoi utilizzare collections.deque per gestire in modo efficiente i dati come coda, stack e deque (coda a doppia estremità, elenco collegato testa-coda).
È anche possibile utilizzare l’elenco integrato come coda, stack o deque, ma collections.deque è più efficiente perché l’eliminazione o l’aggiunta al primo elemento nell’elenco è lenta.
Si noti che deque ha lo svantaggio di un accesso lento agli elementi nel mezzo.
In questo articolo vengono descritti i seguenti contenuti.
- Complessità di elenco e collections.deque
- Vieni a usare collezioni.deque
- Crea un oggetto deque
- Aggiungi un elemento:
append(), appendleft(), extend(), extendleft(), insert() - Rimuovi un elemento:
pop(), popleft(), remove(), clear() - Ruota la Deque:
rotate() - Ottieni valore e indice:
[], index() - Altre operazioni
- Limita la lunghezza massima con maxlen
- Usa deque come coda (FIFO)
- Usa deque come stack (LIFO)
- Usa deque come deque (coda a doppia estremità)
Vedere il seguente articolo sull’aggiunta e la rimozione di elementi per l’elenco.
Complessità di elenco e collections.deque
La complessità di list e deque per varie operazioni è riassunta nel Wiki ufficiale.
In list, operazioni come pop(0) per rimuovere e restituire il primo elemento, insert(0, v) per aggiungere un elemento alla testa, ecc. richiedono O(n), ma in deque, append(), appendleft(), pop() e popleft() per aggiungere e rimuovere il primo e l’ultimo elemento possono essere tutti eseguiti con O(1).
È menzionato anche nella documentazione ufficiale.
Deques supporta append e pop thread-safe ed efficienti in prestazioni di entrambi i lati del deque con approssimativamente termini le stesse O(1) in entrambe le direzioni.
Per gli oggetti elenco di supporto operazioni simili, sono ottimizzati per operazioni rapide a lunghezza fissa e comportano costi di spostamento della memoria O(n) per operazioni pop(0) e insert(0, v) che modificano sia la dimensione che la posizione della rappresentazione dei dati sottostanti.
collezioni – oggetti deque — Tipi di dati del contenitore — Documentazione di Python 3.9.7
D’altra parte, l’accesso agli elementi nel mezzo di [] è più veloce con l’elenco.
L’accesso indicizzato è O(1) su entrambe le ma rallenta fine fino a O(n) nel mezzo. Per un accesso casuale veloce, usa invece le liste.
collezioni – oggetti deque — Tipi di dati del contenitore — Documentazione di Python 3.9.7
Pertanto una linea guida approssimativa è la seguente.
- Aggiungi, elimina e accedi agli elementi solo a entrambe le estremità -> deque
- Accedi frequentemente agli elementi nel mezzo -> elenco
Se vuoi trattare i dati in modo esplicito come una coda, uno stack o usare deque.
Tuttavia, a seconda dell’ambiente e delle condizioni, se il numero di elementi è solo di poche differenze o poche migliaia, non vi è nessuna percettibile nella velocità di elaborazione tra list e deque. A meno che tu voglia non ridurre il tempo di elaborazione in un ordine di millisecondi, non ci sono se usi l’elenco nella maggior parte dei casi.
Se stai valuta qualendo utilizzare in un ambiente o in una condizione fissi, puoi utilizzare il modulo timeit per misurare il tempo di elaborazione effettivo.
Vieni a usare collezioni.deque
Crea un oggetto deque
Crea un oggetto deque con deque().
Se non viene specificato alcun argomento, viene creato un oggetto deque vuoto. Se viene specificato un oggetto iterabile come list, viene creato un oggetto deque con i suoi elementi.
from collections import deque
d = deque()
print(d)
# deque([])
print(type(d))
# <class 'collections.deque'>
d = deque(['m', 'n'])
print(d)
# deque(['m', 'n'])
Puoi anche limitare la lunghezza massima (numero massimo di elementi) con il secondo argomento, maxlen. I dettagli sono descritti più avanti.
Aggiungi un elemento:append(), appendleft(), extend(), extendleft(), insert()
append() aggiunge un elemento sul lato destro, appendleft() sul lato sinistro.
d.append('o')
print(d)
# deque(['m', 'n', 'o'])
d.appendleft('l')
print(d)
# deque(['l', 'm', 'n', 'o'])
extend() aggiunge tutti gli elementi di un oggetto iterabile, come list, sul lato destro. expandleft() li aggiunge al lato sinistro. Si noti che con expandleft(), l’ordine degli elementi dell’iterable viene specificato invertito e concatenato.
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() aggiunge un elemento nel mezzo. Specificare la posizione come primo argomento e il valore da aggiungere come secondo argomento. È possibile specificare una posizione dalla fine con un valore negativo per il primo argomento. Se viene specificata una posizione inesistente (fuori intervallo), l’elemento viene aggiunto all’inizio o alla fine.
insert() è stato aggiunto in 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'])
Rimuovi un elemento:pop(), popleft(), remove(), clear()
pop() rimuove un elemento dal lato destro, popleft() rimuove un elemento dal lato sinistro e ne richiede il valore. A differenza di pop() in list, è impossibile specificare la posizione come argomento.
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() rimuove il primo elemento il cui valore è uguale all’argomento specificato. Anche se due o più elementi vengono assegnati al valore specificato, solo il primo elemento viene rimosso. Se nessun elemento corrisponde al valore specificato, viene generato un errore.
d.remove('b')
print(d)
# deque(['c', 'b'])
# d.remove('X')
# ValueError: deque.remove(x): x not in deque
clear() rimuove tutti gli elementi. Diventa un deque vuoto.
d.clear()
print(d)
# deque([])
Per una deque vuota, pop() e popleft() generano un errore. clear() non genera un errore.
# d.pop()
# IndexError: pop from an empty deque
# d.popleft()
# IndexError: pop from an empty deque
d.clear()
print(d)
# deque([])
Ruota la Deque:rotate()
deque ha un metodo rotate() che non è nell’elenco. Per impostazione predefinita, gli elementi vengono ruotati uno per uno verso destra.
d = deque(['a', 'b', 'c', 'd', 'e'])
d.rotate()
print(d)
# deque(['e', 'a', 'b', 'c', 'd'])
Se viene specificato un valore intero, ruota a destra di quel numero. Se viene specificato un valore negativo, ruota a sinistra.
È inoltre possibile specificare un valore superiore al numero di elementi.
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'])
Ottieni valore e indice:[], index()
Come con list, puoi ottenere il valore di un elemento specificando il suo indice in []. Puoi anche specificare la posizione dalla fine con un valore negativo. Puoi anche migliorare il valore.
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 : non è disponibile direttamente, ma può essere sostituito da islice() della libreria 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'])
Con index(), puoi ottenere l’indice del primo elemento che corrisponde al valore specificato come argomento. Se viene specificato un valore inesistente, viene generato un errore.
index() è stato aggiunto in 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
Altre operazioni
Inoltre sono possibili varie altre operazioni e liste.
Ottieni il numero di elementi con la funzione incorporata len().
d = deque(['a', 'a', 'b', 'c'])
print(len(d))
# 4
Conta il numero di elementi uguale al valore specificato da count().
print(d.count('a'))
# 2
print(d.count('x'))
# 0
L’operatore in utilizzatore viene per verificare se esiste un elemento.
print('b' in d)
# True
print('x' in d)
# False
Invertire l’ordine con il metodo reverse() o la funzione incorporata reversed(). Il metodo reverse() inverte l’oggetto originale stesso e reversed() restituisce l’iteratore invertito.
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'])
Puoi convertirlo in una lista o in una tupla con list() o tuple().
d = deque(['a', 'b', 'c'])
l = list(d)
print(l)
# ['a', 'b', 'c']
print(type(l))
# <class 'list'>
Limita la lunghezza massima con maxlen
Se viene specificato il secondo argomento maxlen di deque(), la lunghezza massima (il numero massimo di elementi) può essere limitato. Il valore predefinito di maxlen è None, il che significa che non c’è limite alla lunghezza.
from collections import deque
d = deque(['l', 'm', 'n'], 3)
print(d)
# deque(['l', 'm', 'n'], maxlen=3)
Se maxlen è specificato e deque è full, elementi vengono scartati dal lato gli opposto quando si aggiungono elementi.
Il comportamento di append(), appendleft(), extend() ed extendleft() è il seguente.
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)
Con insert(), viene generato un errore anche durante l’aggiunta alla fine.
# d.insert(0, 'XXX')
# IndexError: deque already at its maximum size
Se il numero di elementi non raggiunge maxlen, può essere aggiunto con insert().
print(d.pop())
# n
print(d)
# deque(['l', 'm'], maxlen=3)
d.insert(1, 'XXX')
print(d)
# deque(['l', 'XXX', 'm'], maxlen=3)
Il maxlen può essere ottenuto come attributo, ma è di sola lettura e non può essere modificato.
print(d.maxlen)
# 3
# d.maxlen = 5
# AttributeError: attribute 'maxlen' of 'collections.deque' objects is not writable
Usa deque come coda (FIFO)
Una coda contiene i dati in una struttura FIFO (First In, First Out). In una coda, l’inserimento dei dati viene chiamato accodamento e la rimozione dei dati viene chiamato annullamento della coda.
Per usare deque come coda, usa append() come enqueue e popleft() come 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'])
Usa deque come stack (LIFO)
Uno stack contiene i dati in una struttura LIFO (Last In, First Out). In uno stack, l’inserimento dei dati si chiama push e la rimozione dei dati si chiama pop.
Per usare deque come stack, usa append() come push e pop() come 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'])
Usa deque come deque (coda a doppia estremità)
Una deque (coda a doppia estremità) è una coda in cui è possibile aggiungere o rimuovere elementi a entrambe le estremità (testa e coda).
Come negli esempi precedenti, deque consenti di aggiungere e rimuovere elementi da entrambe le estremità con append(), appendleft(), pop() e popleft().