[Python] Cas où le temps d'exécution diffère entre la liste intégrée et deque

• Si vous constatez des erreurs, n'hésitez pas à nous contacter (même si vous demandez une modification).

type de liste et type de déque

Regardons le comportement des types list et deque, qui sont des types intégrés de Python.

Vous trouverez ci-dessous le code qui crée une liste et une file d'attente d'une certaine longueur et récupère les éléments avec. Exécutez avec une longueur de 10 000, 100 000 et 1 million dans l'ordre.

import time
from collections import deque


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

    #opération de type liste
    time1 = time.time()
    while len(l) > 0:
        l.pop(0)

    #Fonctionnement de type Deque
    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()

Les opérations pour extraire le premier élément et le dernier élément sont les fonctions suivantes pour le type de liste et le type deque, respectivement.

from collections import deque

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

#Opération pour récupérer le premier élément
l.pop(0)  # => 1
d.popleft()  # => 1

#Opération pour récupérer l'élément de fin
l.pop(-1)  # => 3
d.pop()  # => 3

Résultat d'exécution

Les résultats suivants ont été obtenus dans l'environnement d'exécution actuel.

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.

Dans le cas d'un million de cas, l'opération de type liste a pris plus de 2 minutes.

Pourquoi cela arrive

Citez la partie pertinente de la documentation officielle. Vous pouvez faire des choses comme «ajouter» et «pop» sur les objets deque, mais cela mentionne en quoi ils diffèrent de ceux des objets de liste.

Une opération similaire peut être réalisée avec l'objet liste, mais il est spécialisé pour les opérations rapides de longueur fixe, telles que pop (0) et insert (0) qui modifient à la fois la taille et la position du format de représentation des données internes. Des opérations telles que, v) nécessitent le coût de O (n) pour déplacer la mémoire.

D'autre part, l'objet deque ne nécessite que le coût de calcul de ʻO (1) `.

Résumé

Les listes ne conviennent pas comme structure de données dont la longueur des données change fréquemment.

Au fait, le code (list.pop (-1)) qui récupère les données du dernier élément au lieu du premier élément (list.pop (0)) est le suivant. Dans ce cas, le temps de traitement de ʻO (1) `ne dépend pas de la longueur de la liste, il n'y a donc pratiquement aucune différence dans le temps d'exécution.

• Entrez «# here» à la différence de ce qui précède

import time
from collections import deque


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

    #opération de type liste
    time1 = time.time()
    while len(l) > 0:
        l.pop(-1)  # here1

    #Fonctionnement de type Deque
    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()

↓ Résultat de l'exécution

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.