Comment les deques en Python sont-ils implémentés, et quand sont-ils pires que les listes?

Découvrez collections.deque. De la docs:

Deques soutien thread-safe, mémoire efficace ajoute et pop de soit côté de la deque avec environ la même performance O(1) dans l'un ou l'autre direction.

Bien que les objets de liste prennent en charge opérations, ils sont optimisés pour opérations de longueur fixe rapides et O (N) coûts de déplacement de la mémoire pour les pop (0) et insert (0, v) opérations qui modifier la taille et la position de le sous-jacent la représentation des données.

Comme il est dit, l'utilisation de pop (0) ou insert (0, v) entraîne de lourdes pénalités avec les objets list. Vous ne pouvez pas utiliser la tranche/index opérations sur un deque, mais vous pouvez utiliser popleft/appendleft, qui sont des opérations deque est optimisé pour. Voici un benchmark 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 documentation pour deque objects décrit la plupart de ce que vous devez savoir, je soupçonne. Citations notables:

Les Deques prennent en charge les ajouts et les pops de chaque côté de la deque avec approximativement la même performance O(1) 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.

Je devrais prendre un regardez la source pour dire si l'implémentation est une liste liée ou autre chose, mais il me semble qu'un deque a à peu près les mêmes caractéristiques qu'une liste doublement liée.

En plus de toutes les autres réponses utiles, 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 à choisir la bonne structure de données pour un problème particulier.

Bien que, je ne suis pas exactement sûr de la façon dont Python l'a implémenté, ici j'ai écrit une implémentation de files d'attente en utilisant uniquement des tableaux. Il a la même complexité que les Files D'attente de Python.

class ArrayQueue:
""" Implements a queue data structure """

def __init__(self, capacity):
    """ Initialize the queue """

    self.data = [None] * capacity
    self.size = 0
    self.front = 0

def __len__(self):
    """ return the length of the queue """

    return self.size

def isEmpty(self):
    """ return True if the queue is Empty """

    return self.data == 0

def printQueue(self):
    """ Prints the queue """

    print self.data 

def first(self):
    """ Return the first element of the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    else:
        return self.data[0]

def enqueue(self, e):
    """ Enqueues the element e in the queue """

    if self.size == len(self.data):
        self.resize(2 * len(self.data))
    avail = (self.front + self.size) % len(self.data) 
    self.data[avail] = e
    self.size += 1

def resize(self, num):
    """ Resize the queue """

    old = self.data
    self.data = [None] * num
    walk = self.front
    for k in range(self.size):
        self.data[k] = old[walk]
        walk = (1+walk)%len(old)
    self.front = 0

def dequeue(self):
    """ Removes and returns an element from the queue """

    if self.isEmpty():
        raise Empty("Queue is empty")
    answer = self.data[self.front]
    self.data[self.front] = None 
    self.front = (self.front + 1) % len(self.data)
    self.size -= 1
    return answer

class Empty(Exception):
""" Implements a new exception to be used when stacks are empty """

pass

Et ici vous pouvez le tester avec du code:

def main():
""" Tests the queue """ 

Q = ArrayQueue(5)
for i in range(10):
    Q.enqueue(i)
Q.printQueue()    
for i in range(10):
    Q.dequeue()
Q.printQueue()    


if __name__ == '__main__':
    main()

Cela ne fonctionnera pas aussi vite que l'implémentation C, mais il utilise la même logique.