J'ai récemment commencé à étudier la façon dont diverses structures de données sont mises en œuvre dans Python afin de rendre mon code plus efficace. En étudiant le fonctionnement des listes et des deques, j'ai découvert que je pouvais obtenir des avantages lorsque je voulais décaler et décaler en réduisant le temps de O(n) dans les listes à O(1) dans les deques (les listes étant implémentées comme des tableaux de longueur fixe qui doivent être copiés complètement à chaque fois que quelque chose est inséré à l'avant, etc...). Ce que je n'arrive pas à trouver, ce sont les spécificités de l'implémentation d'une deque, et les spécificités de ses inconvénients par rapport aux listes. Quelqu'un peut-il m'éclairer sur ces deux questions ?
Réponses
Trop de publicités?https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c
A
dequeobject
est composé d'une liste doublement liée deblock
nœuds.
Alors oui, un deque
est une liste (doublement) chaînée, comme le suggère une autre réponse.
Élaborer : Cela signifie que les listes Python sont bien meilleures pour l'accès aléatoire et les opérations de longueur fixe, y compris le découpage, tandis que les deques sont bien plus utiles pour pousser et sortir des éléments des extrémités, l'indexation (mais pas le découpage, ce qui est intéressant) étant possible mais plus lente qu'avec les listes.
Vérifier collections.deque
. D'après la documentation :
Deques prend en charge la sécurité des threads, la mémoire de la mémoire à l'abri des threads, des appends et des pops de chaque d'un côté ou de l'autre de la deque avec approximativement la même performance O(1) dans l'un ou l'autre dans l'une ou l'autre direction.
Bien que les objets de type liste prennent en charge des opérations similaires, ils sont optimisés pour opérations rapides de longueur fixe et encourent des coûts de des coûts de déplacement de mémoire O(n) pour pop(0) et insert(0, v) qui qui modifient à la fois la taille et la position la représentation des données sous-jacentes.
Comme indiqué, l'utilisation de pop(0) ou insert(0, v) entraîne des pénalités importantes avec les objets de type liste. Vous ne pouvez pas utiliser les opérations de tranche/index sur un objet de type deque
mais vous pouvez utiliser popleft
/ appendleft
qui sont des opérations deque
est optimisé pour. Voici un exemple simple pour le démontrer :
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)
Résultats sur ma machine :
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
L'entrée de la documentation pour deque
objets explique l'essentiel de ce qu'il faut savoir, je pense. Citations notables :
Les déques prennent en charge les appends et pops de part et d'autre de la déque de manière sûre pour les threads et efficace en termes de mémoire, avec des performances O(1) à peu près identiques dans les deux sens.
Mais...
L'accès indexé est O(1) aux deux extrémités mais ralentit à O(n) au milieu. Pour un accès aléatoire rapide, utilisez plutôt des listes.
Il faudrait que je jette un coup d'œil à la source pour savoir si l'implémentation est une liste chaînée ou quelque chose d'autre, mais il me semble qu'il y a un deque
présente à peu près les mêmes caractéristiques qu'une liste doublement liée.
En plus de toutes les autres réponses utiles, aquí Voici quelques informations supplémentaires comparant la complexité temporelle (Big-Oh) de diverses opérations sur les listes, les déques, les ensembles et les dictionnaires Python. Cela devrait aider à sélectionner la structure de données appropriée pour un problème particulier.