Bases y colas basadas en matriz frente a listas

Question

Estoy tratando de comparar las tasas de crecimiento (tanto de tiempo de ejecución como de espacio) para las operaciones de cola y cola cuando se implementan como dos matrices y como listas vinculadas. Hasta ahora solo he podido encontrar tiempos de ejecución promedio para la cola pop() s, pero nada que explore exhaustivamente estas dos estructuras de datos y compara sus comportamientos en tiempo de ejecución/espacio.

Específicamente, Busco para comparar push() y pop() para ambas colas y pilas, implementado como tanto matrices y listas enlazadas (por lo tanto 2 operaciones x 2 x 2 estructuras implementaciones, o 8 valores).

Además, agradecería los mejores, los valores medios y peores de ambos, y todo lo relacionado con la cantidad de espacio que consumen.

Lo más parecido que he podido encontrar es este "pdf de la madre de todos los ches sheets" que es claramente un truco a nivel de maestría o doctorado de algoritmos avanzados y funciones discretas.

Estoy buscando una manera de determinar cuándo y dónde debo usar una implementación basada en arreglos frente a una implementación basada en listas para pilas y colas.

Answer 1

Existen múltiples formas diferentes de implementar colas y pilas con listas y matrices vinculadas, y no estoy seguro de cuáles está buscando. Sin embargo, antes de analizar cualquiera de estas estructuras, repasemos algunas consideraciones importantes de tiempo de ejecución para las estructuras de datos anteriores.

En una lista enlazada individualmente con solo un puntero a la cabeza, el costo de anteponer un valor es O (1) - simplemente creamos el nuevo elemento, cableamos su puntero para apuntar al encabezado anterior de la lista y luego actualizamos el puntero de la cabeza. El costo para eliminar el primer elemento también es O (1), que se hace actualizando el puntero del cabezal para apuntar al elemento después del encabezado actual, luego liberando la memoria para el encabezado anterior (si se realiza una administración de memoria explícita). Sin embargo, los factores constantes en estos términos O (1) pueden ser altos debido al gasto de las asignaciones dinámicas. La sobrecarga de memoria de la lista vinculada suele ser O (n) memoria extra total debido al almacenamiento de un puntero adicional en cada elemento.

En una matriz dinámica, podemos acceder a cualquier elemento en el tiempo O (1). También podemos agregar un elemento en amortized O(1), lo que significa que el tiempo total para n inserciones es O (n), aunque los límites de tiempo reales en cualquier inserción pueden ser mucho peores.Normalmente, las matrices dinámicas se implementan haciendo que la mayoría de las inserciones tengan O (1) añadiéndolas al espacio preasignado, pero teniendo un pequeño número de inserciones ejecutándose en el tiempo Θ (n) duplicando la capacidad de la matriz y copiando los elementos. Existen técnicas para tratar de reducir esto asignando espacio extra y copiando los elementos de forma perezosa (ver this data structure, por ejemplo). Normalmente, el uso de la memoria de una matriz dinámica es bastante buena: cuando la matriz está completamente llena, por ejemplo, solo hay O (1) carga adicional, aunque justo después de que la matriz se haya duplicado, puede haber O (n) sin usar. elementos asignados en la matriz. Debido a que las asignaciones son poco frecuentes y los accesos son rápidos, las matrices dinámicas suelen ser más rápidas que las vinculadas.

Ahora, pensemos en cómo implementar una pila y una cola utilizando una lista vinculada o una matriz dinámica. Hay muchas maneras de hacer esto, así que voy a asumir que usted está usando las siguientes implementaciones:

• Pila:
  • lista enlazada: Como singly-linked list con un puntero cabeza.
  • matriz: como una cola dynamic array
• :
  • lista enlazada: Como una lista simplemente enlazada con un puntero cabeza y la cola.
  • Matriz: como circular buffer respaldada por una matriz.

Vamos a considerar cada uno de ellos.

Pila respaldada por una lista de enlaces simples. Debido a que una lista de enlace único admite O (1) tiempo antes y eliminar primero, el costo de empujar o hacer estallar en una pila vinculada con lista vinculada también es O (1) el peor de los casos. Sin embargo, cada elemento nuevo agregado requiere una nueva asignación, y las asignaciones pueden ser costosas en comparación con otras operaciones.

Pila respaldada por una matriz dinámica. La inserción en la pila se puede implementar agregando un nuevo elemento a la matriz dinámica, que toma el tiempo O (1) amortizado y el tiempo O (n) del peor caso. El estallido de la pila se puede implementar simplemente eliminando el último elemento, que se ejecuta en el peor de los casos O (1) (o O amortizado (1) si desea intentar reclamar el espacio no utilizado). En otras palabras, la implementación más común tiene el mejor de los casos O (1) push y pop, el peor caso O (n) push y O (1) pop, y O (1) amortizado push y O (1) pop.

Cola respaldada por una lista de enlaces simples. La inserción en la lista vinculada se puede implementar añadiéndola al reverso de la lista de enlace único, que toma el tiempo peor de caso O (1). La eliminación de secuencias puede implementarse eliminando el primer elemento, que también toma el tiempo de peor caso O (1). Esto también requiere una nueva asignación por enqueue, que puede ser lenta.

Cola respaldada por un creciente buffer circular. La inserción en el búfer circular funciona insertando algo en la siguiente posición libre en el búfer circular. Esto funciona haciendo crecer la matriz si es necesario, luego insertando el nuevo elemento. Usando un análisis similar para la matriz dinámica, esto toma el tiempo en el mejor de los casos O (1), el tiempo en el peor caso O (n) y el tiempo amortizado O (1). La eliminación de la memoria intermedia funciona eliminando el primer elemento de la memoria intermedia circular, lo que lleva tiempo O (1) en el peor de los casos.

En resumen, todas las estructuras admiten presionar y abrir n elementos en el tiempo O (n). Las versiones de la lista vinculada tienen un mejor comportamiento en el peor de los casos, pero pueden tener un peor tiempo de ejecución general debido a la cantidad de asignaciones realizadas. Las versiones de matriz son más lentas en el peor de los casos, pero tienen un mejor rendimiento general si el tiempo por operación no es demasiado importante.

Otra opción que puede considerar para implementar stacks es VList, una estructura de datos reciente que es un híbrido de una lista vinculada y una matriz dinámica. Hace menos asignaciones que una lista vinculada y tiene menos punteros, aunque el uso del espacio es un poco más alto en el peor de los casos. También es posible que desee examinar listas de fragmentos, que son otro híbrido de matrices y listas vinculadas, que se pueden usar tanto para pilas como para colas.

Espero que esto ayude!

Answer 2

Lo siento si malinterpreté su pregunta, pero si no lo hice, entonces creo que esta es la respuesta que está buscando.

Con un vector, solo puede agregar/eliminar elementos de manera eficiente al final del contenedor. Con un deque, puede agregar/eliminar elementos de manera eficiente al principio/final del contenedor. Con una lista, puede insertar/eliminar elementos de manera eficiente en cualquier lugar del contenedor.

vectores/deque permiten iteradores de acceso aleatorio. Las listas solo permiten el acceso secuencial.

Cómo necesita usar y almacenar los datos es cómo determinar cuál es el más apropiado.

EDIT:

Hay mucho más que esto, mi respuesta es muy generalizada. Puedo profundizar más si estoy al corriente de cuál es tu pregunta.