Perché aggiungere o rimuovere dal centro di una collezioni è più lento della ricerca?

Question

Questa wiki.python.org pagina su complessità algoritmica di alcune strutture di dati dice il seguente per un oggetto collections.deque:

Una coda doppia (Deque) è rappresentato internamente come una lista doppiamente collegata. (Bene, una lista di matrici piuttosto che di oggetti, per una maggiore efficienza.) Entrambe le estremità sono accessibili, ma anche guardare al centro è lento, e l'aggiunta o la rimozione dal centro è ancora più lenta.

Due domande:

1) è l'aggiunta al centro di una deque anche possibile? Non vedo alcun metodo per farlo in API.

2) Perché rimuovere (o aggiungere) essere più lento della ricerca nel mezzo di un deque? È una lista doppiamente collegata, quindi aggiungi/rimuovi dovrebbe essere un'operazione a tempo costante una volta trovato l'oggetto che vuoi aggiungere.

Answer 1

1. È possibile eliminare elementi utilizzando il metodo remove() o la parola chiave del. Non è possibile inserire oggetti. (L'unico modo possibile per inserire quello che non si presenterebbe nella documentazione dell'API sarebbe l'assegnazione dello slice, che non è valida su un deque.)
2. Perché, come dice la descrizione, è in realtà un elenco di array con doppio collegamento. Pertanto, l'inserimento o la rimozione di elementi potrebbe richiedere la migrazione di elementi da una matrice all'altra. (Non ho guardato l'implementazione, ma so che lo deque usa una tecnica di passo quando cerco elementi e presumo che la dimensione degli array usati sia la stessa della lunghezza del passo, che è 62.) Dovresti cambiare un sacco di memoria in giro in un regolare list quando si eliminano gli elementi, ma almeno è tutto in un pezzo e può essere spostato in modo efficiente.

Answer 2

1) Sembra deque.insert() è stato aggiunto in Python 3,5

2) Dalla fonte: https://github.com/python/cpython/blob/d16a1520c2b22c3cbde7547937ba283db3e88ff5/Modules/_collectionsmodule.c#L952-L958

insert(), remove(), e delItem() sono implementate in termini di ruotare() per semplicità e prestazioni ragionevoli vicino alla fine punti. Se per qualche motivo questi metodi diventano popolari, non è difficile da implementare utilizzando il movimento di dati diretto (simile a il codice utilizzato nelle assegnazioni degli elenchi) e ottenere una prestazione boost (spostando ciascun puntatore una sola volta invece di due volte).

Il motivo per cui è più lento è a causa di come è stato implementato.

Answer 3

È possibile inserire con python3.5. index(), insert(), and copy() sono tre nuovi metodi disponibili solo in python3.5, new in python 3.5, non c'è modo di inserire in una deque nelle versioni precedenti:

La classe deque definisce ora index(), inserire(), e copy(), come così come supporta gli operatori + e *. Ciò consente ai deques di essere riconosciuti come MutableSequence e migliora la loro sostituibilità per le liste. (Contribuito da Raymond Hettinger numero 23704.)

È possibile rimuovere dal mezzo di una coda doppia, sia utilizzando del o deque.remove:

deq = deque([1,2,3,4,5,6]) 
del deq[4] 
deq.remove(3)