Python Language
Modulo Deque
Ricerca…
Sintassi
- dq = deque () # Crea un deque vuoto
- dq = deque (iterable) # Crea un deque con alcuni elementi
- dq.append (oggetto) # Aggiunge l'oggetto alla destra del deque
- dq.appendleft (oggetto) # Aggiunge l'oggetto alla sinistra del deque
- dq.pop () -> oggetto # Rimuove e restituisce l'oggetto più giusto
- dq.popleft () -> oggetto # Rimuove e restituisce l'oggetto più a sinistra
- dq.extend (iterable) # Aggiunge alcuni elementi alla destra del deque
- dq.extendleft (iterable) # Aggiunge alcuni elementi a sinistra del deque
Parametri
| Parametro | Dettagli |
|---|---|
iterable | Crea il deque con gli elementi iniziali copiati da un altro iterabile. |
maxlen | Limita la dimensione della deque, eliminando i vecchi elementi quando vengono aggiunti nuovi elementi. |
Osservazioni
Questa classe è utile quando è necessario un oggetto simile a un elenco che consente operazioni rapide di accodamento e pop da entrambi i lati (il nome deque sta per " coda a doppio attacco ").
I metodi forniti sono davvero molto simili, tranne per il fatto che alcuni come pop , append o extend possono essere suffissi con left . La struttura dei dati di deque dovrebbe essere preferibile a un elenco se è necessario inserire ed eliminare frequentemente elementi a entrambe le estremità poiché consente di farlo in tempo costante O (1).
Deque di base usando
I metodi principali che sono utili con questa classe sono popleft e appendleft
from collections import deque
d = deque([1, 2, 3])
p = d.popleft() # p = 1, d = deque([2, 3])
d.appendleft(5) # d = deque([5, 2, 3])
limite dimensioni deque
Utilizzare il parametro maxlen durante la creazione di una deque per limitare le dimensioni della deque:
from collections import deque
d = deque(maxlen=3) # only holds 3 items
d.append(1) # deque([1])
d.append(2) # deque([1, 2])
d.append(3) # deque([1, 2, 3])
d.append(4) # deque([2, 3, 4]) (1 is removed because its maxlen is 3)
Metodi disponibili in deque
Creazione deque vuota:
dl = deque() # deque([]) creating empty deque
Creare deque con alcuni elementi:
dl = deque([1, 2, 3, 4]) # deque([1, 2, 3, 4])
Aggiungere un elemento a deque:
dl.append(5) # deque([1, 2, 3, 4, 5])
Aggiunta elemento lato sinistro del deque:
dl.appendleft(0) # deque([0, 1, 2, 3, 4, 5])
Aggiunta di un elenco di elementi da deque:
dl.extend([6, 7]) # deque([0, 1, 2, 3, 4, 5, 6, 7])
Aggiunta di un elenco di elementi dal lato sinistro:
dl.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])
L'utilizzo .pop() rimuoverà naturalmente un oggetto dal lato destro:
dl.pop() # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])
Utilizzando l'elemento .popleft() per rimuovere un elemento dal lato sinistro:
dl.popleft() # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])
Rimuovi elemento dal suo valore:
dl.remove(1) # deque([-2, 0, 2, 3, 4, 5, 6])
Invertire l'ordine degli elementi nella nota:
dl.reverse() # deque([6, 5, 4, 3, 2, 0, -2])
Larghezza Prima ricerca
Il Deque è l'unica struttura dati Python con operazioni di coda veloci. (Nota queue.Queue non è normalmente adatto, poiché è inteso per la comunicazione tra thread). Un caso d'uso di base di una coda è la prima ricerca in ampiezza .
from collections import deque
def bfs(graph, root):
distances = {}
distances[root] = 0
q = deque([root])
while q:
# The oldest seen (but not yet visited) node will be the left most one.
current = q.popleft()
for neighbor in graph[current]:
if neighbor not in distances:
distances[neighbor] = distances[current] + 1
# When we see a new node, we add it to the right side of the queue.
q.append(neighbor)
return distances
Supponiamo di avere un semplice grafico diretto:
graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}
Ora possiamo trovare le distanze da una posizione iniziale:
>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}