Wie werden Deques in Python implementiert und wann sind sie schlechter als Listen?

85

Ich habe kürzlich untersucht, wie verschiedene Datenstrukturen in Python implementiert sind, um meinen Code effizienter zu gestalten. Bei der Untersuchung der Funktionsweise von Listen und Deques stellte ich fest, dass ich Vorteile erzielen kann, wenn ich die Zeit von O (n) in Listen auf O (1) in Deques verschieben und verschieben möchte (Listen werden als Arrays mit fester Länge implementiert) jedes Mal, wenn etwas vorne eingefügt wird, vollständig kopiert werden usw.). Was ich anscheinend nicht finden kann, sind die Besonderheiten der Implementierung einer Deque und die Besonderheiten ihrer Nachteile gegenüber Listen. Kann mich jemand über diese beiden Fragen aufklären?

Eli
quelle

Antworten:

74

https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c

A dequeobjectbesteht aus einer doppelt verknüpften Liste von blockKnoten.

Also ja, a deque ist eine (doppelt) verknüpfte Liste, wie eine andere Antwort nahelegt.

Ausarbeiten: Dies bedeutet, dass Python-Listen für Operationen mit wahlfreiem Zugriff und fester Länge, einschließlich Slicing, viel besser sind, während Deques viel nützlicher sind, um Dinge von den Enden zu schieben und zu entfernen, wobei das Indizieren (aber interessanterweise nicht das Slicing) der Fall ist möglich aber langsamer als bei Listen.

JAB
quelle
3
Beachten Sie, dass Listen, wenn Sie nur an einem Ende anhängen und einfügen müssen (Stapel), eine bessere Leistung erzielen sollten als O (1) .append()und .pop()amortisiert werden (Neuzuweisung und Kopieren erfolgen, jedoch sehr selten und nur bis Sie die maximale Größe des Stapels erreichen jemals haben).
@delnan: Aber wenn Sie eine Warteschlange wollen, dann ist so etwas dequedefinitiv der richtige Weg.
JAB
@delnan: Wie findest du das? .append () und .pop () werden in Listen mit O (1) amortisiert, aber sind sie nicht tatsächlich O (1) in Deques, und Kopien sind niemals erforderlich.
Eli
1
@Eli: Listen befassen sich nicht mit Thread-Sicherheit (naja, sie sind nicht mit ihren Interna verbunden) und wurden von vielen klugen Leuten schon lange optimiert.
3
@delnan: Eigentlich kümmern sich deques in CPython auch nicht wirklich um die Thread-Sicherheit. Sie profitieren nur davon, dass die GIL ihre Operationen atomar macht (und tatsächlich appendund popam Ende von a listden gleichen Schutz hat). In der Praxis sind , wenn Sie nur einen Stapel mit, beide listund dequeeffektiv identische Leistung in CPython haben; Die Blockzuweisungen sind häufiger mit deque(aber nicht einfach verknüpfte Listen häufig; Sie würden nur jedes Mal zuweisen / freigeben, wenn Sie eine 64-Mitglieder-Grenze in der CPython-Implementierung überschritten haben), aber das Fehlen großer intermittierender Kopien gleicht dies aus.
ShadowRanger
51

Auschecken collections.deque. Aus den Dokumenten:

Deques unterstützen thread-sichere, speichereffiziente Anhänge und Pops von beiden Seiten des Deques mit ungefähr der gleichen O (1) -Leistung in beide Richtungen.

Obwohl Listenobjekte ähnliche Operationen unterstützen, sind sie für schnelle Operationen fester Länge optimiert und verursachen O (n) Speicherbewegungskosten für Pop (0) - und Insert (0, v) -Operationen, die sowohl die Größe als auch die Position der zugrunde liegenden Datendarstellung ändern .

Wie bereits erwähnt, führt die Verwendung von pop (0) oder insert (0, v) zu hohen Strafen bei Listenobjekten. Sie können keine Slice / Index-Operationen für a verwenden deque, aber Sie können popleft/ verwenden appendleft, für die Operationen dequeoptimiert sind. Hier ist ein einfacher Benchmark, um dies zu demonstrieren:

import time
from collections import deque

num = 100000

def append(c):
    for i in range(num):
        c.append(i)

def appendleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.appendleft(i)
    else:
        for i in range(num):
            c.insert(0, i)
def pop(c):
    for i in range(num):
        c.pop()

def popleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.popleft()
    else:
        for i in range(num):
            c.pop(0)

for container in [deque, list]:
    for operation in [append, appendleft, pop, popleft]:
        c = container(range(num))
        start = time.time()
        operation(c)
        elapsed = time.time() - start
        print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed)

Ergebnisse auf meiner Maschine:

Completed deque/append in 0.02 seconds: 5582877.2 ops/sec
Completed deque/appendleft in 0.02 seconds: 6406549.7 ops/sec
Completed deque/pop in 0.01 seconds: 7146417.7 ops/sec
Completed deque/popleft in 0.01 seconds: 7271174.0 ops/sec
Completed list/append in 0.01 seconds: 6761407.6 ops/sec
Completed list/appendleft in 16.55 seconds: 6042.7 ops/sec
Completed list/pop in 0.02 seconds: 4394057.9 ops/sec
Completed list/popleft in 3.23 seconds: 30983.3 ops/sec
Zeekay
quelle
3
Huh, habe gerade bemerkt, dass man mit Deques nicht schneiden kann, obwohl man indizieren kann. Interessant.
JAB
1
+1 für die Timings - interessant, dass listAnhänge etwas schneller sind als dequeAnhänge.
senderle
1
@zeekay: Das ist ziemlich seltsam, wenn man bedenkt, dass das Suchen nach dem Index eines bestimmten Elements normalerweise ohnehin das Durchlaufen der Elemente der Sammlung erfordert und dass Sie dequegenau wie ein Index in ein indizieren können list.
JAB
1
@senderle: Natürlich waren die list pops langsamer als dequedie s (wahrscheinlich aufgrund der listhöheren Kosten für die zeitweise Größenänderung, wenn sie verkleinert werden, wobei dequenur Blöcke zurück in die freie Liste oder den kleinen Objektpool freigegeben werden), also bei der Auswahl einer Datenstruktur für ein Stapel (auch bekannt als LIFO - Warteschlange), die leer zu voll zu leer Leistung sieht etwas besser deque(Mittelwert 6365K ops / sec für append/ pop, vs. list‚s 5578K ops / sec). Ich vermute, dequedass es in der realen Welt etwas besser laufen würde, da dequedie freie Liste bedeutet, dass das erste Wachstum teurer ist als das Wachstum nach dem Schrumpfen.
ShadowRanger
1
Um meine Freelist-Referenz zu verdeutlichen: CPython dequewird nicht freebis zu 16 Blöcke (modulweit, nicht pro deque) enthalten, sondern sie in einem billigen Array verfügbarer Blöcke zur Wiederverwendung ablegen. Wenn also ein dequezum ersten Mal wächst , muss es immer neue Blöcke herausziehen malloc(was appendteurer wird), aber wenn es sich ein bisschen ständig ausdehnt, dann ein bisschen schrumpft und hin und her, wird es normalerweise nicht malloc/ freeat beinhalten alles solange die Länge ungefähr in einem Bereich von 1024 Elementen bleibt (16 Blöcke auf der freien Liste, 64 Slots pro Block).
ShadowRanger
17

Der Dokumentationseintrag für dequeObjekte enthält vermutlich das meiste, was Sie wissen müssen. Bemerkenswerte Zitate:

Deques unterstützen thread-sichere, speichereffiziente Anhänge und Pops von beiden Seiten des Deques mit ungefähr der gleichen O (1) -Leistung in beide Richtungen.

Aber...

Der indizierte Zugriff ist an beiden Enden O (1), verlangsamt sich jedoch in der Mitte auf O (n). Verwenden Sie für einen schnellen Direktzugriff stattdessen Listen.

Ich müsste mir die Quelle ansehen, um festzustellen, ob es sich bei der Implementierung um eine verknüpfte Liste oder um etwas anderes handelt, aber für mich klingt es so, als hätte a dequeungefähr die gleichen Eigenschaften wie eine doppelt verknüpfte Liste.

senderle
quelle
11

Neben all den anderen hilfreichen Antworten finden Sie hier einige weitere Informationen zum Vergleich der Zeitkomplexität (Big-Oh) verschiedener Operationen in Python-Listen, Deques, Mengen und Wörterbüchern. Dies sollte bei der Auswahl der richtigen Datenstruktur für ein bestimmtes Problem hilfreich sein.

PythonJin
quelle
-3

Ich bin mir zwar nicht ganz sicher, wie Python es implementiert hat, aber hier habe ich eine Implementierung von Queues geschrieben, die nur Arrays verwendet. Es hat die gleiche Komplexität wie Pythons Warteschlangen.

class ArrayQueue:
""" Implements a queue data structure """

def __init__(self, capacity):
    """ Initialize the queue """

    self.data = [None] * capacity
    self.size = 0
    self.front = 0

def __len__(self):
    """ return the length of the queue """

    return self.size

def isEmpty(self):
    """ return True if the queue is Empty """

    return self.data == 0

def printQueue(self):
    """ Prints the queue """

    print self.data 

def first(self):
    """ Return the first element of the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    else:
        return self.data[0]

def enqueue(self, e):
    """ Enqueues the element e in the queue """

    if self.size == len(self.data):
        self.resize(2 * len(self.data))
    avail = (self.front + self.size) % len(self.data) 
    self.data[avail] = e
    self.size += 1

def resize(self, num):
    """ Resize the queue """

    old = self.data
    self.data = [None] * num
    walk = self.front
    for k in range(self.size):
        self.data[k] = old[walk]
        walk = (1+walk)%len(old)
    self.front = 0

def dequeue(self):
    """ Removes and returns an element from the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    answer = self.data[self.front]
    self.data[self.front] = None 
    self.front = (self.front + 1) % len(self.data)
    self.size -= 1
    return answer

class Empty(Exception):
""" Implements a new exception to be used when stacks are empty """

pass

Und hier können Sie es mit etwas Code testen:

def main():
""" Tests the queue """ 

Q = ArrayQueue(5)
for i in range(10):
    Q.enqueue(i)
Q.printQueue()    
for i in range(10):
    Q.dequeue()
Q.printQueue()    


if __name__ == '__main__':
    main()

Es funktioniert nicht so schnell wie die C-Implementierung, verwendet jedoch dieselbe Logik.

TheRevanchist
quelle
1
Das Rad nicht neu erfinden!
Abhijit Sarkar
Die Frage war, wie Pythons Deque implementiert wird. Es wurde nicht nach einer alternativen Implementierung gefragt.
Gino Mempin