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

deque python 3

Question

Recientemente he investigado cómo se implementan varias estructuras de datos en Python para que mi código sea más eficiente. Al investigar cómo funcionan las listas y los deques, descubrí que puedo obtener beneficios cuando deseo cambiar y cambiar sin cambios el tiempo de O (n) en las listas a O (1) en los deques (las listas se implementan como matrices de longitud fija que tienen para ser copiado por completo cada vez que se inserta algo en la parte delantera, 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. ¿Puede alguien iluminarme sobre estas dos preguntas?

Answer 1

Además de todas las otras respuestas útiles, here 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 correcta para un problema particular.

Answer 2

Echa un vistazo a collections.deque . De la documentación:

Deques es compatible con subprocesos seguros y eficientes con la memoria y hace estallar desde cualquier lado del deque con aproximadamente el mismo rendimiento O (1) en cualquier dirección.

Aunque los objetos de la 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 pop (0) e insertar (0, v) que cambian el tamaño y la posición de la representación de datos subyacente .

Tal como dice, el uso de pop (0) o insert (0, v) incurre en grandes penalizaciones con los objetos de lista. No puede usar las operaciones de popleft / índice en un deque , pero puede usar popleft / appendleft , que son operaciones para las que se optimiza el deque . Aquí hay un simple punto de referencia 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

Answer 3

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

Deques es compatible con subprocesos seguros y eficientes con la memoria y hace estallar 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 disminuye a 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 un deque tiene aproximadamente las mismas características que una lista con un enlace doble.

Answer 4

Mientras, no estoy exactamente seguro de cómo Python lo ha implementado, aquí escribí una implementación de colas usando solo arreglos. 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.

Answer 5

https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

Un objeto de dequeobject está compuesto por una lista de nodos de block enlaces dequeobject .

Así que sí, un deque es una lista enlazada (doblemente) como sugiere otra respuesta.

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