Verwendung für Python-Stapel und -Warteschlangen (Geschwindigkeitsvergleich jeder Datenstruktur)

Einführung

Dieser Artikel befasst sich hauptsächlich mit wettbewerbsfähiger Programmierung.

Es gibt mehrere Möglichkeiten, Stapel und Warteschlangen in Python zu implementieren.

--Stapel

• Liste verwenden (append (), pop ()) --Verwenden Sie collection.deque (append (), pop ()) --Warteschlange
• Liste verwenden (append (), pop (0)) --Verwenden Sie collection.deque (append (), popleft ()) --Verwenden Sie queue.Queue (put (), get ())

Welches davon ist übrigens das beste? Dieses Mal konzentrieren wir uns auf den Geschwindigkeitsaspekt.

Messmethode

Hinzufügen und Abrufen von Elementen 10-mal, 100-mal, 1000-mal, 10000-mal und 100000-mal für jede Datenstruktur.

Im gesamten Code wird der unten stehende Importteil weggelassen.

Teil importieren

from collections import deque
from queue import Queue
import time

Stapel

Liste verwenden

# stack(list)
stack_list_append = []
stack_list_pop = []
for i in range(1, 6):
    start = time.time()

    stack_list = []
    for j in range(10 ** i):
        stack_list.append(j)

    stack_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_list.pop()

    stack_list_pop.append(time.time() - start)

Verwenden Sie deque

# stack(deque)
stack_deque_append = []
stack_deque_pop = []
for i in range(1, 6):
    start = time.time()

    stack_deque = deque([])
    for j in range(10 ** i):
        stack_deque.append(j)

    stack_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_deque.pop()

    stack_deque_pop.append(time.time() - start)

Warteschlange

Liste verwenden

# queue(list)
queue_list_append = []
queue_list_pop = []
for i in range(1, 6):
    start = time.time()

    queue_list = []
    for j in range(10 ** i):
        queue_list.append(j)

    queue_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_list.pop(0)

    queue_list_pop.append(time.time() - start)

Verwenden Sie deque

# queue(deque)
queue_deque_append = []
queue_deque_pop = []
for i in range(1, 6):
    start = time.time()

    queue_deque = deque([])
    for j in range(10 ** i):
        queue_deque.append(j)

    queue_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_deque.popleft()

    queue_deque_pop.append(time.time() - start)

Warteschlange verwenden

# queue(Queue)
queue_Queue_append = []
queue_Queue_pop = []

for i in range(1, 6):
    start = time.time()

    queue_Queue = Queue()
    for j in range(10 ** i):
        queue_Queue.put(j)

    queue_Queue_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_Queue.get()

    queue_Queue_pop.append(time.time() - start)

Messergebnis

Wenn das Messergebnis grafisch dargestellt wird, ist es wie folgt.

Beginnen wir oben links.

Stapelergebnis

Element hinzufügen

Die Grafik oben links. Deque ist etwas schneller, aber es ist ungefähr das gleiche.

Elemente extrahieren

Es ist eine Grafik oben rechts. Auch hier ist Deque etwas schneller, aber es ist ungefähr das gleiche.

Ergebnis der Warteschlange

Element hinzufügen

Es ist eine Grafik unten links. Bei einer großen Anzahl von Elementen ist die Warteschlange mehr als zehnmal langsamer als die anderen.

Elemente extrahieren

Das Diagramm unten rechts. Die Warteschlange entspricht dem Hinzufügen eines Elements, die Liste ist jedoch offensichtlich schlecht. Es ist mehr als 100 Mal langsamer als die schnellste Deque.

Fazit

Es ist am besten, collection.deque sowohl für Stapel als auch für Warteschlangen zu verwenden.

Da es eine große Sache ist, schreibe ich eine einfache Verwendung.

Stapel

from collections import deque

s = deque([])
s.append(1)  # [1]
s.append(2)  # [1, 2]
s.append(3)  # [1, 2, 3]
s.pop()      #Von oben entfernen[1, 2, 3] -> [1, 2]
s.pop()      # [1, 2] -> [1]
s.pop()      # [1] -> []

Warteschlange

Im Stapel war es Pop, als es entfernt wurde, aber in der Warteschlange ist es nur Popleft.

from collections import deque

q = deque([])
q.append(1)  # [1]
q.append(2)  # [1, 2]
q.append(3)  # [1, 2, 3]
q.popleft()  #Von unten entfernen[1, 2, 3] -> [2, 3]
q.popleft()  # [2, 3] -> [3]
q.popleft()  # [3] -> []