deque.popleft () y list.pop (0). ¿Hay diferencia de rendimiento?

deque.popleft() y list.pop(0) parecen devolver el mismo resultado. ¿Hay alguna diferencia de rendimiento entre ellos y por qué?

deque.popleft () es más rápido que list.pop (0), porque el deque se ha optimizado para hacer popleft () aproximadamente en O (1), mientras que list.pop (0) toma O (n) (vea los objetos deque ) .

Los comentarios y el código en _collectionsmodule.c para deque y listobject.c para lista proporcionan información de implementación para explicar las diferencias de rendimiento. Es decir, que un objeto deque “se compone de una lista doblemente enlazada”, que efectivamente optimiza los apéndices y los pops en ambos extremos, mientras que los objetos de la lista no son ni siquiera listas enlazadas individualmente sino arrays C (de punteros a elementos) h # l22 y Python 3.5 listobject.h # l23 ), lo que los hace buenos para el acceso aleatorio rápido de elementos pero requiere O (n) tiempo para reposicionar todos los elementos después de eliminar el primero.

Para Python 2.7 y 3.5, las URL de estos archivos de código fuente son:

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

  2. https://hg.python.org/cpython/file/2.7/Objects/listobject.c

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

  4. https://hg.python.org/cpython/file/3.5/Objects/listobject.c

Usando% timeit, la diferencia de rendimiento entre deque.popleft () y list.pop (0) es aproximadamente un factor de 4 cuando tanto el deque como la lista tienen los mismos 52 elementos y crecen por encima de un factor de 1000 cuando sus longitudes son 10 ** 8. Los resultados de la prueba se dan a continuación.

 import string from collections import deque %timeit d = deque(string.letters); d.popleft() 1000000 loops, best of 3: 1.46 µs per loop %timeit d = deque(string.letters) 1000000 loops, best of 3: 1.4 µs per loop %timeit l = list(string.letters); l.pop(0) 1000000 loops, best of 3: 1.47 µs per loop %timeit l = list(string.letters); 1000000 loops, best of 3: 1.22 µs per loop d = deque(range(100000000)) %timeit d.popleft() 10000000 loops, best of 3: 90.5 ns per loop l = range(100000000) %timeit l.pop(0) 10 loops, best of 3: 93.4 ms per loop 

¿Hay diferencia de rendimiento?

Sí. deque.popleft() es O(1) – una operación de tiempo constante. Si bien list.pop(0) es O(n) , operación de tiempo lineal: cuanto mayor sea la lista, más tiempo tomará.

¿Por qué?

La implementación de la lista CPython está basada en matrices. pop(0) elimina el primer elemento de la lista y requiere desplazar len(lst) - 1 izquierdo len(lst) - 1 elementos para llenar el espacio.

deque() implementación deque() utiliza una lista doblemente enlazada. No importa el tamaño del deque, deque.popleft() requiere un número constante (limitado arriba) de operaciones.

Sí, y es considerable si tienes una lista larga o deque. Todos los elementos de una lista se colocan de forma contigua en la memoria, por lo que si elimina cualquier elemento, todos los elementos posteriores deben desplazarse una posición hacia la izquierda; por lo tanto, el tiempo requerido para eliminar o insertar un elemento al comienzo de una lista es proporcional a la longitud de la lista. Por otro lado, un deque se construye específicamente para permitir inserciones o eliminaciones rápidas en cualquiera de los extremos (por lo general, permite ubicaciones de memoria “vacías” al comienzo del deque, o se envuelve de manera que el final del segmento de memoria ocupado por el deque puede contener elementos que en realidad se consideran al principio del deque).

Compara el rendimiento de estos dos fragmentos:

 d = deque([0] * 1000000) while d: d.popleft() if len(d) % 100 == 0: print(len(d)) lst = [0] * 1000000 while lst: lst.pop(0) if len(lst) % 100 == 0: print(len(lst))