¿Por qué se implementa deque como una lista enlazada en lugar de una matriz circular?

CPython deque se implementa 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á lleno.

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 / free por 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 sola matriz circular de tamaño dynamic 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) (al ubicar de manera 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 enlazada en idiomas como C ++, donde la eliminación de un elemento del medio se puede hacer en O(1) usando un puntero o un iterador; Sin embargo, Python deque no tiene API para hacer esto.

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 push en ambos extremos sean eficientes. Eso es lo que hace la implementación actual: tiempo constante en el peor de los casos por empuje 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 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 mencionado por Jim Fasarakis Hilliard en su comentario:

https://www.mail-archive.com/python-dev@python.org/msg25024.html

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 reventara el valor

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 usa 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, debe 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.