Warum benötigt Python O (n) Zeit, um das erste Element aus einer Liste zu entfernen?

Question

Die Python wiki page on time complexity besagt, dass das Löschen eines Elements O (n) Zeit dauert. Die description of the deque class in the documentation of the collections module besagt, dass "list Objekte [...] O (n) Speicherbewegungskosten für pop(0) und insert(0, v) Operationen verursachen, die sowohl die Größe als auch die Position der zugrunde liegenden Datendarstellung ändern".

Warum brauchen Listen O (n) Zeit? Ist eine Liste nicht nur ein paar Elemente oder Zeiger auf Elemente, die physisch nebeneinander im Speicher liegen, zusammen mit einem Zeiger auf den Anfang der Liste? Wenn ja, warum kann der list-Typ keine popleft-Methode ähnlich der in collections.deque haben, die das erste Element in O (1) -Zeit entfernt, indem der Startzeiger der Liste entsprechend inkrementiert wird?

Ich versuche nicht, ein bestimmtes Problem zu lösen. Ich möchte nur meine Neugier befriedigen, warum es so gestaltet ist.

EDIT: Hier ist ein Diagramm, wie meine popleft Methode funktionieren würde:

Vor popleft Aufruf:

------------------------------------------------------------------- 
| The | quick | brown | fox | jumps | over | 
------------------------------------------------------------------- 
    ^
     pointer to list 

Nach dem Aufruf von popleft:

------------------------------------------------------------------- 
| The | quick | brown | fox | jumps | over | 
------------------------------------------------------------------- 
       ^
       pointer to list 

Vor dem Aufruf an popleft ist das erste Element der Liste The, das 2. ist quick usw. Nach dem Aufruf war der Ort, an dem das erste Element war, ungenutzter Speicher (der leer gelassen oder vom Müll beansprucht werden kann) collector), das neue erste Element ist quick, das neue zweite Element ist brown, usw. Es müssen keine großen Datenmengen bewegt werden, und es muss nichts passieren, was O (n) Zeit in Anspruch nimmt.

Answer 1

Python list ist eigentlich ein Array. deque ist eine echte verknüpfte Liste. Es ist Pythons Schuld, den falschen Begriff zu benutzen (für den ich keine Erklärung habe). O(n) zum Einfügen und Löschen ist normal für Arrays (wie folgende Elemente müssen nach oben oder unten verschoben werden), die ein Kompromiss für die O(1) Geschwindigkeit für get und gesetzt ist. Verknüpfte Listen machen einen ähnlichen Kompromiss in der entgegengesetzten Richtung: O(1) für Operationen an Enden, aber O(n) für jeden Zugang in der Mitte.

Answer 2

Der Zeiger auf, wo die Liste wirklich startet, muss beibehalten werden, um den Speicher entsprechend zu befreien.

Tatsächlich könnte remove(0) schneller gemacht werden, indem man einen zweiten Zeiger hat, der in diesem Fall erhöht wird. Und wenn danach eine .add(0, x) passiert, könnte dies beschleunigt werden, indem dieser "Datenstart-Timer" dekrementiert wird, solange er größer als der "Speicherstart-Timer" ist.

Aber alle anderen Operationen, ich. e. Einfügungen und Löschungen in andere Indizes wären immer noch O(n), also würde sich das nicht viel ändern.

Nur wissen, was Ihre Operationen sein werden und somit welche Datenstruktur zu wählen.

Answer 3

Es gibt keinen Grund es konnte nicht sein, es war einfach nicht.Es ist jedoch eine Komplikation für den Code, und das Problem, mit dem Sie konfrontiert sind, ist normalerweise ein Anzeichen dafür, dass Sie den falschen Ansatz verfolgen.

Sie könnten dieses Verhalten selbst in einer Wrapper-Klasse implementieren, und das in den Fällen verwenden, in denen Sie wissen, dass es sich lohnt.

Das sagte something similar has been submitted to PyPy.