python: deque vs lista comparación de rendimiento

En los documentos de Python puedo ver que deque es una colección especial altamente optimizada para abrir / agregar elementos desde el lado izquierdo o derecho. Por ejemplo, la documentación dice:

Deques es una generalización de stacks y colas (el nombre se pronuncia “deck” y es la abreviatura de “cola doble”). Deques es compatible con subprocesos seguros y eficientes en 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 .

Decidí hacer algunas comparaciones usando ipython . ¿Podría alguien explicarme lo que 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 

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 el pop es insignificante en comparación.

En su lugar, debe aislar lo que está tratando de probar (la velocidad del pop) del 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 tiene velocidad O (1) para appendleft () y popleft (), mientras que las listas tienen un rendimiento O (n) para insertar (0, valor) y pop (0) .

  • El rendimiento de la lista de agregados es impredecible porque usa realloc () debajo del capó. Como resultado, tiende a tener tiempos demasiado optimistas en código simple (porque el realloc no tiene que mover datos) y tiempos realmente lentos en código real (porque la fragmentación obliga a realloc a mover todos los datos). En contraste, el rendimiento de la adición de deque es consistente porque nunca se reasigna y nunca mueve los datos.

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 el appendleft frente a la insert .