pythoned - Eficiencia de usar una lista de Python como cola

funciones de pila en python (5)

Algunas respuestas afirmaron tener una ventaja de velocidad "10x" para deque vs list-used-as-FIFO cuando ambas tienen 1000 entradas, pero eso es un poco sobreabuso:

$ python -mtimeit -s''q=range(1000)'' ''q.append(23); q.pop(0)'' 1000000 loops, best of 3: 1.24 usec per loop $ python -mtimeit -s''import collections; q=collections.deque(range(1000))'' ''q.append(23); q.popleft()'' 1000000 loops, best of 3: 0.573 usec per loop

python -mtimeit es tu amigo: ¡un enfoque de micro-benchmarking realmente útil y simple! Con él, por supuesto, también puedes explorar el rendimiento de forma trivial en casos mucho más pequeños:

$ python -mtimeit -s''q=range(100)'' ''q.append(23); q.pop(0)'' 1000000 loops, best of 3: 0.972 usec per loop $ python -mtimeit -s''import collections; q=collections.deque(range(100))'' ''q.append(23); q.popleft()'' 1000000 loops, best of 3: 0.576 usec per loop

(no muy diferente para 12 en lugar de 100 artículos por cierto), y en mucho más grandes:

$ python -mtimeit -s''q=range(10000)'' ''q.append(23); q.pop(0)'' 100000 loops, best of 3: 5.81 usec per loop $ python -mtimeit -s''import collections; q=collections.deque(range(10000))'' ''q.append(23); q.popleft()'' 1000000 loops, best of 3: 0.574 usec per loop

Puede ver que el reclamo del rendimiento de O (1) para deque está bien fundado, mientras que una lista es más del doble de lenta alrededor de 1,000 artículos, un orden de magnitud de alrededor de 10,000. También puede ver que incluso en tales casos solo está desperdiciando 5 microsegundos más o menos por par Anexar / Pop y decide qué tan importante es ese desperdicio (aunque si eso es todo lo que hace con ese contenedor, deque no tiene inconvenientes, entonces también podría cambiar incluso si 5 usec más o menos no hará una diferencia importante).

Un compañero de trabajo escribió recientemente un programa en el que utilizó una lista de Python como cola. En otras palabras, usó .append(x) cuando necesita insertar elementos y .pop(0) cuando necesita eliminar elementos.

Sé que Python tiene collections.deque y estoy tratando de decidir si gastar mi tiempo (limitado) para volver a escribir este código para usarlo. Suponiendo que realizamos millones de anexos y pops pero nunca tenemos más de unos miles de entradas, ¿su uso de la lista será un problema?

En particular, ¿la matriz subyacente utilizada por la implementación de la lista Python continuará creciendo indefinidamente y tendrá millones de spots aunque la lista solo tenga mil cosas, o Python eventualmente hará un realloc y liberará parte de esa memoria?

Cada .pop(0) toma N pasos, ya que la lista debe ser reorganizada. La memoria requerida no crecerá infinitamente y solo será tan grande como se requiera para los artículos que se guardan.

Recomiendo usar deque para obtener O (1) anexar y pop de frente.

De la referencia esencial de Python de Beazley , cuarta edición , p. 194:

Algunos módulos de biblioteca proporcionan nuevos tipos que superan a los incorporados en ciertas tareas. Por ejemplo, el tipo collections.deque proporciona una funcionalidad similar a una lista pero ha sido altamente optimizado para la inserción de elementos en ambos extremos. Una lista, en cambio, solo es eficiente cuando se agregan elementos al final. Si inserta elementos en la parte delantera, todos los demás elementos deben desplazarse para dejar espacio. El tiempo requerido para hacer esto crece a medida que la lista se hace cada vez más grande. Solo para darle una idea de la diferencia, esta es una medida de tiempo para insertar un millón de artículos en la parte delantera de una lista y una deque:

Y sigue este ejemplo de código:

>>> from timeit import timeit >>> timeit(''s.appendleft(37)'', ''import collections; s = collections.deque()'', number=1000000) 0.13162776274638258 >>> timeit(''s.insert(0,37)'', ''s = []'', number=1000000) 932.07849908298408

Los tiempos son de mi máquina.

2012-07-01 Actualización

>>> from timeit import timeit >>> n = 1024 * 1024 >>> while n > 1: ... print ''-'' * 30, n ... timeit(''s.appendleft(37)'', ''import collections; s = collections.deque()'', number=n) ... timeit(''s.insert(0,37)'', ''s = []'', number=n) ... n >>= 1 ... ------------------------------ 1048576 0.1239769458770752 799.2552740573883 ------------------------------ 524288 0.06924104690551758 148.9747350215912 ------------------------------ 262144 0.029170989990234375 35.077512979507446 ------------------------------ 131072 0.013737916946411133 9.134140014648438 ------------------------------ 65536 0.006711006164550781 1.8818109035491943 ------------------------------ 32768 0.00327301025390625 0.48307204246520996 ------------------------------ 16384 0.0016388893127441406 0.11021995544433594 ------------------------------ 8192 0.0008249282836914062 0.028419017791748047 ------------------------------ 4096 0.00044918060302734375 0.00740504264831543 ------------------------------ 2048 0.00021195411682128906 0.0021741390228271484 ------------------------------ 1024 0.00011205673217773438 0.0006101131439208984 ------------------------------ 512 6.198883056640625e-05 0.00021386146545410156 ------------------------------ 256 2.9087066650390625e-05 8.797645568847656e-05 ------------------------------ 128 1.5974044799804688e-05 3.600120544433594e-05 ------------------------------ 64 8.821487426757812e-06 1.9073486328125e-05 ------------------------------ 32 5.0067901611328125e-06 1.0013580322265625e-05 ------------------------------ 16 3.0994415283203125e-06 5.9604644775390625e-06 ------------------------------ 8 3.0994415283203125e-06 5.0067901611328125e-06 ------------------------------ 4 3.0994415283203125e-06 4.0531158447265625e-06 ------------------------------ 2 2.1457672119140625e-06 2.86102294921875e-06

No se quedará sin memoria con la implementación de la list , pero el rendimiento será deficiente. De los documentos :

Aunque los objetos de list 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 insert(0, v) que cambian tanto el tamaño como la posición de la representación de datos subyacente .

Entonces, usar un deque será mucho más rápido.

Parece que un poco de prueba empírica podría ser lo mejor que se puede hacer aquí: los problemas de segundo orden podrían hacer que uno se acercara mejor en la práctica, incluso si no es mejor en teoría.