python - ordenada - ¿Por qué se implementa deque como una lista enlazada en lugar de una matriz circular?
listas enlazadas ejemplos (2)
Adaptado de mi respuesta en la lista de correo de python-dev:
El punto principal de un deque es hacer que el popping y el empuje en ambos extremos sean eficientes. Eso es lo que hace la implementación actual: tiempo constante en el peor de los casos por inserción o pop independientemente de cuántos elementos haya en el deque. Eso supera "O (1) amortizado" en lo pequeño y en lo grande. Es por eso que se hizo de esta manera.
Algunos otros métodos de deque son por lo tanto más lentos que para las listas, pero ¿a quién le importa? Por ejemplo, los únicos índices que he usado con un deque son 0 y -1 (para mirar por un extremo o el otro de un deque), y la implementación hace que el acceso a esos índices específicos sea constante también.
De hecho, el mensaje de Raymond Hettinger al que Jim Fasarakis Hilliard hace referencia en su comentario:
confirma que
La única razón por la que se
__getitem__fue para permitir un acceso rápido a la cabeza y la cola sin que se revalorice
CPython deque se implemented como una lista doblemente enlazada de "bloques" de tamaño de 64 elementos (arrays). Todos los bloques están llenos, excepto los que se encuentran al final de la lista enlazada. IIUC, los bloques se liberan cuando un pop / popleft elimina el último elemento del bloque; se asignan cuando append / appendleft intenta agregar un nuevo elemento y el bloque correspondiente está completo.
Entiendo las ventajas enumeradas de usar una lista de bloques vinculados en lugar de una lista de elementos vinculados:
- Reducir el costo de memoria de los punteros a prev y siguiente en cada elemento.
- reducir el costo de tiempo de ejecución de hacer
malloc/freepor cada artículo agregado / eliminado - mejorar la localidad de caché colocando punteros consecutivos uno al lado del otro
Pero, ¿por qué no se utilizó una única matriz circular de tamaño dinámico en lugar de la lista de enlaces dobles en primer lugar?
AFAICT, la matriz circular conservaría todas las ventajas anteriores y mantendría el costo (amortizado) de pop* / append* en O(1) (por ubicación general, como en la list ). Además, mejoraría el costo de búsqueda por índice de la O(n) actual a O(1) . Una matriz circular también sería más sencilla de implementar, ya que puede reutilizar gran parte de la implementación de la list .
Puedo ver un argumento a favor de una lista vinculada en lenguajes como C ++, donde la eliminación de un elemento del medio se puede hacer en O(1) utilizando un puntero o un iterador; Sin embargo, Python deque no tiene API para hacer esto.
Además de aceptar la respuesta de @TimPeters, quería agregar un par de observaciones adicionales que no encajan en un formato de comentario.
Centrémonos en un caso de uso común en el que se utiliza deque como una simple cola FIFO.
Una vez que la cola alcanza su tamaño máximo, la matriz circular no necesita más asignaciones de memoria del montón. Pensé en esto como una ventaja, pero resulta que la implementación de CPython logró lo mismo al mantener una lista de bloques de memoria reutilizables. Una corbata.
Mientras el tamaño de la cola aumenta, tanto la matriz circular como el CPython necesitan memoria del montón. CPython necesita un malloc simple, mientras que la matriz necesita el realloc (potencialmente mucho más costoso) (a menos que haya espacio adicional disponible en el borde derecho del bloque de memoria original, necesita liberar la memoria antigua y copiar los datos). Ventaja para CPython.
Si la cola alcanzó un tamaño mucho mayor que su tamaño estable, tanto CPython como la implementación de la matriz desperdiciarían la memoria no utilizada (la primera guardándola en una lista de bloques reutilizables, la última dejando el espacio vacío no utilizado en la matriz) . Una corbata.
Como @TimPeters señaló, el costo de cada cola / recepción de FIFO es siempre O(1) para CPython, pero solo se amortiza O(1) para la matriz. Ventaja para CPython.