Quoi utiliser pour les piles et les files d'attente Python (comparaison de vitesse de chaque structure de données)

introduction

Cet article concerne principalement la programmation compétitive.

Il existe plusieurs façons d'implémenter des piles et des files d'attente en Python.

--Empiler --Utiliser la liste (ʻappend () , pop () ) --Utiliser collections.deque (ʻappend () ,pop ()) --Queue --Utiliser la liste (ʻappend () , pop (0) ) --Utiliser collections.deque (ʻappend () ,popleft ()) --Utilisez queue.Queue (put (), get ())

Au fait, laquelle de ces options est la meilleure à utiliser? Cette fois, nous allons nous concentrer sur l'aspect vitesse.

Méthode de mesure

Ajoutez et récupérez des éléments 10 fois, 100 fois, 1000 fois, 10000 fois et 100000 fois pour chaque structure de données.

Tout le code omet la partie d'importation ci-dessous.

importer une partie

from collections import deque
from queue import Queue
import time

empiler

utiliser la liste

# 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)

Utiliser 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)

queue

utiliser la liste

# 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)

Utiliser 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)

Utiliser la file d'attente

# 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)

Résultat de la mesure

Lorsque le résultat de la mesure est représenté graphiquement, c'est comme suit.

Commençons par le coin supérieur gauche.

Résultat de la pile

Ajouter un élément

Le graphique en haut à gauche. Deque est un peu plus rapide, mais c'est à peu près la même chose.

Extraction d'éléments

C'est un graphique en haut à droite. Encore une fois, deque est un peu plus rapide, mais c'est à peu près la même chose.

Résultat de la file d'attente

Ajouter un élément

C'est un graphique en bas à gauche. Avec un grand nombre d'éléments, la file d'attente est plus de 10 fois plus lente que les autres.

Extraction d'éléments

Le graphique en bas à droite. La file d'attente revient à ajouter un élément, mais la liste est évidemment mauvaise. Il est plus de 100 fois plus lent que le deque le plus rapide.

Conclusion

Il est préférable d'utiliser collections.deque pour les piles et les files d'attente.

Puisque c'est un gros problème, j'écrirai une utilisation simple.

empiler

from collections import deque

s = deque([])
s.append(1)  # [1]
s.append(2)  # [1, 2]
s.append(3)  # [1, 2, 3]
s.pop()      #Retirer du haut[1, 2, 3] -> [1, 2]
s.pop()      # [1, 2] -> [1]
s.pop()      # [1] -> []

queue

Dans la pile, c'était pop quand il a été supprimé, mais dans la file d'attente, c'est juste popleft.

from collections import deque

q = deque([])
q.append(1)  # [1]
q.append(2)  # [1, 2]
q.append(3)  # [1, 2, 3]
q.popleft()  #Retirer du bas[1, 2, 3] -> [2, 3]
q.popleft()  # [2, 3] -> [3]
q.popleft()  # [3] -> []