[Python] Fall, in dem sich die Ausführungszeit zwischen der integrierten Liste und der Deque unterscheidet

• Wenn Sie Fehler finden, zögern Sie bitte nicht, uns zu kontaktieren (auch wenn Sie eine Bearbeitung anfordern).

Listentyp und Deque-Typ

Schauen wir uns das Verhalten der Listen- und Deque-Typen an, bei denen es sich um integrierte Python-Typen handelt.

Unten finden Sie den Code, der eine Liste und Warteschlange mit einer bestimmten Länge erstellt und die Elemente mit abruft. Ausführen mit einer Länge von 10.000, 100.000 und 1 Million in der Reihenfolge.

import time
from collections import deque


for count in [10000, 100000, 1000000]:
    #Objektinitialisierung
    l = ['a'] * count
    q = deque(l)

    #Listentyp Operation
    time1 = time.time()
    while len(l) > 0:
        l.pop(0)

    #Deque-Typ-Betrieb
    time2 = time.time()
    while len(q) > 0:
        q.popleft()
    time3 = time.time()

    print('count:', count)
    print(f'list  finished: {time2 - time1} sec.')
    print(f'deque finished: {time3 - time2} sec.')
    print()

Die Operationen zum Extrahieren des ersten Elements und des letzten Elements sind die folgenden Funktionen für den Listentyp bzw. den Deque-Typ.

from collections import deque

#Initialisieren
l = [1, 2, 3]
q = deque(l)

#Operation zum Abrufen des ersten Elements
l.pop(0)  # => 1
d.popleft()  # => 1

#Operation zum Abrufen des nachfolgenden Elements
l.pop(-1)  # => 3
d.pop()  # => 3

Ausführungsergebnis

Die folgenden Ergebnisse wurden in der vorliegenden Ausführungsumgebung erhalten.

count: 10000
list  finished: 0.006018161773681641 sec.
deque finished: 0.0003972053527832031 sec.

count: 100000
list  finished: 0.9306132793426514 sec.
deque finished: 0.003919839859008789 sec.

count: 1000000
list  finished: 133.8608682155609 sec.
deque finished: 0.04343390464782715 sec.

Bei 1 Million Fällen dauerte der Vorgang vom Listentyp mehr als 2 Minuten.

Warum passiert das?

Zitieren Sie den relevanten Teil aus der offiziellen Dokumentation. Sie können Dinge wie "Anhängen" und "Pop" an Deque-Objekten ausführen, es wird jedoch erwähnt, wie sie sich von denen auf Listenobjekten unterscheiden.

Eine ähnliche Operation kann mit dem Listenobjekt erzielt werden, ist jedoch auf schnelle Operationen mit fester Länge wie pop (0) und insert (0) spezialisiert, die sowohl die Größe als auch die Position des internen Datendarstellungsformats ändern. Operationen wie v) erfordern die Kosten von O (n), um Speicher zu verschieben.

Andererseits benötigt das Deque-Objekt nur die Berechnungskosten von "O (1)".

Zusammenfassung

Listen eignen sich nicht als Datenstruktur, deren Datenlänge sich häufig ändert.

Der Code (list.pop (-1)), der Daten vom letzten Element anstelle des ersten Elements (list.pop (0)) abruft, lautet übrigens wie folgt. In diesem Fall hängt die Verarbeitungszeit von "O (1)" nicht von der Länge der Liste ab, so dass es fast keinen Unterschied in der Ausführungszeit gibt.

• Geben Sie "# hier" in der Differenz zu den oben genannten ein.

import time
from collections import deque


for count in [10000, 100000, 1000000]:
    #Objektinitialisierung
    l = ['a'] * count
    q = deque(l)

    #Listentyp Operation
    time1 = time.time()
    while len(l) > 0:
        l.pop(-1)  # here1

    #Deque-Typ-Betrieb
    time2 = time.time()
    while len(q) > 0:
        q.pop()  # here2
    time3 = time.time()

    print('count:', count)
    print(f'list  finished: {time2 - time1} sec.')
    print(f'deque finished: {time3 - time2} sec.')
    print()

↓ Ausführungsergebnis

count: 10000
list  finished: 0.0006232261657714844 sec.
deque finished: 0.0005576610565185547 sec.

count: 100000
list  finished: 0.005739688873291016 sec.
deque finished: 0.004764080047607422 sec.

count: 1000000
list  finished: 0.05780482292175293 sec.
deque finished: 0.05013251304626465 sec.