arrays - unir - Bases y colas basadas en matriz frente a listas

unir dos matrices en python

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 matrices y como listas vinculadas. Hasta ahora, solo he podido encontrar tiempos de ejecución promedio para cola pop() s, pero nada que explore exhaustivamente estas dos estructuras de datos y compara sus comportamientos de espacio de ejecución / espacio.

Específicamente, estoy buscando comparar push() y pop() para colas y pilas, implementadas como matrices y listas vinculadas (por lo tanto, 2 operaciones x 2 estructuras x 2 implementaciones u 8 valores).

Además, apreciaría los mejores, los valores medios y peores para 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 de algoritmos avanzados y funciones discretas a nivel de maestría o doctorado.

Solo busco una forma de determinar cuándo y dónde debería usar una implementación basada en arreglos comparados con una implementación basada en listas para apilamientos 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 unida 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 O (1) amortizado , 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 al tener la mayoría de las inserciones O (1) añadiéndolas al espacio preasignado, pero teniendo un pequeño número de inserciones ejecutándose en Θ (n) tiempo 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 (consulte esta estructura de datos , 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 usando una lista vinculada o una matriz dinámica. Hay muchas formas de hacerlo, así que supondré que estás usando las siguientes implementaciones:

• Apilar:
  • Lista enlazada: como una lista vinculada individualmente con un puntero a la cabeza.
  • Array: como una matriz dinámica
• Cola:
  • Lista enlazada: como una lista vinculada individualmente con un puntero de cabeza y cola.
  • Array: como un búfer circular respaldado por una matriz.

Consideremos cada uno a su vez.

Pila respaldada por una lista unida individualmente. Debido a que una lista enlazada individualmente admite O (1) tiempo antes y luego eliminar, el costo de empujar o hacer estallar en una pila con una lista vinculada también es O (1) en 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 enlace único. La inserción en la lista vinculada se puede implementar añadiendo al reverso de la lista de enlace único, que toma el tiempo peor (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.

Para resumir, 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 quizás desee 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

Perdón 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.

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

La forma en que necesita usar y almacenar los datos es cómo determinar cuál es el más apropiado.

EDITAR:

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