¿Cómo se implementan los deques en Python y cuándo son peores que las listas?

Recientemente me he dedicado a investigar cómo se implementan varias estructuras de datos en Python para hacer que mi código sea más eficiente. Al investigar cómo funcionan las listas y los deques, descubrí que puedo obtener beneficios cuando quiero cambiar y deshacer el cambio reduciendo el tiempo de O (n) en listas a O (1) en deques (listas que se implementan como matrices de longitud fija que tienen copiar completamente cada vez que se inserta algo en la parte frontal, etc ...). Lo que parece que no puedo encontrar son los detalles de cómo se implementa un deque y los detalles de sus desventajas frente a las listas. ¿Alguien puede iluminarme sobre estas dos preguntas?

https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c

A dequeobjectse compone de una lista de blocknodos doblemente enlazados .

Entonces, sí, a dequees una lista (doblemente) vinculada, como sugiere otra respuesta.

Elaboración: lo que esto significa es que las listas de Python son mucho mejores para operaciones de acceso aleatorio y de longitud fija, incluido el corte, mientras que los deques son mucho más útiles para empujar y sacar cosas de los extremos, con indexación (pero no corte, curiosamente) siendo posible pero más lento que con listas.

Echa un vistazo collections.deque. De los documentos:

Los deques admiten agregados y estallidos seguros para subprocesos y eficientes en memoria desde cualquier lado del deque con aproximadamente el mismo rendimiento O (1) en cualquier dirección.

Aunque los objetos de lista admiten operaciones similares, están optimizados para operaciones rápidas de longitud fija e incurren en costos de movimiento de memoria O (n) para operaciones de inserción (0) e inserción (0, v) que cambian tanto el tamaño como la posición de la representación de datos subyacentes .

Tal como dice, el uso de pop (0) o insert (0, v) conlleva grandes penalizaciones con los objetos de lista. No puede usar operaciones de corte / índice en a deque, pero puede usar popleft/ appendleft, que son operaciones para las que dequeestá optimizado. Aquí hay un punto de referencia simple para demostrar esto:

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)

Resultados en mi máquina:

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

La entrada de documentación para dequeobjetos explica la mayor parte de lo que necesita saber, sospecho. Citas notables:

Los deques admiten agregados y estallidos seguros para subprocesos y eficientes en memoria desde cualquier lado del deque con aproximadamente el mismo rendimiento O (1) en cualquier dirección.

Pero...

El acceso indexado es O (1) en ambos extremos, pero se ralentiza hasta O (n) en el medio. Para un acceso aleatorio rápido, use listas en su lugar.

Tendría que echar un vistazo a la fuente para saber si la implementación es una lista vinculada o algo más, pero me parece que dequetiene aproximadamente las mismas características que una lista doblemente vinculada.

Además de todas las otras respuestas útiles, aquí hay más información que compara la complejidad del tiempo (Big-Oh) de varias operaciones en listas, deques, conjuntos y diccionarios de Python. Esto debería ayudar a seleccionar la estructura de datos adecuada para un problema en particular.

Si bien no estoy exactamente seguro de cómo lo implementó Python, aquí escribí una implementación de Colas usando solo matrices. Tiene la misma complejidad que las colas 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

Y aquí puedes probarlo con algún código:

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

No funcionará tan rápido como la implementación de C, pero usa la misma lógica.