queues - python: comparación de rendimiento de deque frente a lista

queue class python

Question

En python docs puedo ver que deque es una colección especial altamente optimizada para mostrar / agregar elementos desde el lado izquierdo o derecho. Por ejemplo, la documentación dice:

Deques son una generalización de stacks y colas (el nombre se pronuncia "deck" y es la abreviatura de "double-ended queue"). Deques es compatible con la seguridad de subprocesos, la memoria eficiente se agrega y emerge de cualquier lado del deque con aproximadamente el mismo rendimiento de 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 pop (0) e inserción (0, v) que cambian tanto el tamaño como la posición de la representación de datos subyacente .

Decidí hacer algunas comparaciones usando ipython . ¿Alguien podría explicarme qué hice mal aquí?

In [31]: %timeit range(1, 10000).pop(0)
 10000 loops, best of 3: 114 us per loop

In [32]: %timeit deque(xrange(1, 10000)).pop() 
10000 loops, best of 3: 181 us per loop

In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop

Answer 1

Por lo que vale la pena:

> python -mtimeit -s ''import collections'' -s ''c = collections.deque(xrange(1, 100000000))'' ''c.pop()''
10000000 loops, best of 3: 0.11 usec per loop

> python -mtimeit -s ''c = range(1, 100000000)'' ''c.pop()''
10000000 loops, best of 3: 0.174 usec per loop

> python -mtimeit -s ''import collections'' -s ''c = collections.deque()'' ''c.appendleft(1)''
10000000 loops, best of 3: 0.116 usec per loop

> python -mtimeit -s ''c = []'' ''c.insert(0, 1)''
100000 loops, best of 3: 36.4 usec per loop

Como puede ver, donde realmente brilla está en appendleft vs insert .

Answer 2

Could anyone explain me what I did wrong here

Sí, su tiempo está dominado por el tiempo para crear la lista o deque. El tiempo para hacer pop es insignificante en comparación.

En su lugar, debe aislar la cosa que está intentando probar (la velocidad del pop) desde el tiempo de configuración:

In [1]: from collections import deque

In [2]: s = range(1000)

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

Dicho esto, las diferencias reales entre los deques y la lista en términos de rendimiento son:

• Deques tienen O (1) velocidad para appendleft () y popleft () mientras que las listas tienen O (n) rendimiento para insert (0, value) y pop (0) .

• El rendimiento de la lista de anexos es inconsistente porque usa realloc () debajo del capó. Como resultado, tiende a tener tiempos excesivamente optimistas en código simple (porque el realloc no tiene que mover datos) y tiempos realmente lentos en el código real (porque la fragmentación obliga a realloc a mover todos los datos). Por el contrario, el rendimiento de deque de anexar es consistente porque nunca reasigna y nunca mueve datos.