Warum ist das Hinzufügen oder Entfernen von der Mitte eines collections.deque langsamer als das Nachschlagen?

Question

Diese wiki.python.org Seite auf algorithmische Komplexität einiger Datenstrukturen sagt der folgende für ein collections.deque Objekt:

A deque (Deque) wird intern als doppelt verknüpfte Liste dargestellt. (Nun, eine Liste von Arrays anstelle von Objekten, für mehr Effizienz.) Beide Enden sind zugänglich, aber selbst in der Mitte ist langsam, und Hinzufügen oder Entfernen von der Mitte ist noch langsamer.

Zwei Fragen:

1) ist das Hinzufügen zu der Mitte eines deque überhaupt möglich? Ich sehe keine Methode, dies in der API zu tun.

2) Warum sollte das Entfernen (oder Hinzufügen) langsamer sein als das Suchen in der Mitte eines deque? Es handelt sich um eine doppelt verknüpfte Liste. Daher sollte add/remove eine konstante Zeitoperation sein, sobald Sie das Objekt gefunden haben, das Sie hinzufügen möchten.

Answer 1

1. Es ist möglich, Gegenstände mit der remove()-Methode oder das del Schlüsselwort zu löschen. Das Einfügen von Elementen ist nicht möglich. (Die einzige Möglichkeit, dass einfügen würde in der API-Dokumentation nicht auftauchen würde slice Zuordnung sein, und das ist ungültig auf einem deque.)
2. Denn, wie die Beschreibung sagt, es ist eigentlich eine doppelt verknüpfte Liste von Arrays. Das Einfügen oder Entfernen von Objekten könnte daher erfordern, dass Elemente von einem Array zu einem anderen verschoben werden. (Ich habe die Implementierung nicht angeschaut, aber ich weiß, dass deque eine Stride-Technik verwendet, wenn nach Elementen gesucht wird und ich nehme an, dass die Größe der verwendeten Arrays dieselbe ist wie die Schrittlänge, die 62 ist.) Sie müssten verschieben eine Menge Speicher in einem regulären list beim Löschen von Elementen, aber zumindest ist es alles in einem Stück und es kann effizient bewegt werden.

Answer 2

1) Sieht aus wie deque.insert() 3,5

2) Von der Quelle in Python wurde hinzugefügt: https://github.com/python/cpython/blob/d16a1520c2b22c3cbde7547937ba283db3e88ff5/Modules/_collectionsmodule.c#L952-L958

insert(),() entfernen, und delitem() werden in Form umgesetzt von rotieren() zur Vereinfachung und angemessene Leistung gegen Ende Punkte. Wenn aus irgendeinem Grund diese Methoden populär werden, ist es nicht schwer, dies unter Verwendung direkter Datenbewegung (ähnlich der Code in Listen Slice-Zuweisungen) wieder zu implementieren und eine Leistung Boost zu erreichen (durch Verschieben jedes Zeigers nur einmal statt zweimal).

Der Grund, warum es langsamer ist, ist, wie es implementiert wurde.

Answer 3

Es ist möglich, mit python3.5 einzufügen. index(), insert(), and copy() sind drei neue Methoden nur in python3.5, new in python 3.5, gibt es keine Möglichkeit, in eine deque in früheren Versionen einzufügen:

Die Deque-Klasse definiert nun Index(), einfügen() und copy(), wie sowie unterstützt + und * Betreiber. Dadurch können Deques als MutableSequence erkannt und ihre Substituierbarkeit für Listen verbessert werden. (Beitrag von Raymond Hettinger, Ausgabe 23704.)

Sie können aus der Mitte eines Deque entfernen, entweder mit del oder deque.remove:

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