performance - operaciones - pilas colas y listas en java

Lista vinculada vs. matriz dinámica para implementar una pila (5)

Empecé a revisar las estructuras de datos y los algoritmos antes de que mi último año escolar empiece a asegurarme de estar al tanto de todo. Un problema de revisión decía: "Implemente una pila usando una lista vinculada o una matriz dinámica y explique por qué tomó la mejor decisión".

Para mí, me pareció más intuitivo usar una lista con un puntero de cola para implementar una pila, ya que puede ser necesario cambiar su tamaño a menudo. Parece que para una gran cantidad de datos, una lista es la mejor opción ya que un tamaño de matriz dinámico es una operación costosa. Además, con una lista, no necesita asignar más espacio del que realmente necesita para que sea más eficiente en cuanto a espacio.

Sin embargo, una matriz dinámica definitivamente permitiría agregar datos mucho más rápido (excepto cuando se necesita cambiar el tamaño). Sin embargo, no estoy seguro si el uso de una matriz es en general más rápido, o solo si no es necesario cambiar el tamaño.

La solución del libro decía "para almacenar objetos muy grandes, una lista es una mejor implementación", pero no entiendo por qué.

¿Qué camino es el mejor? ¿Qué factores deberían usarse para determinar qué implementación es la "mejor"? Además, ¿alguna de mi lógica está desactivada?

Aquí hay muchas concesiones involucradas y no creo que haya una respuesta "correcta" a esta pregunta.

Si implementa la pila usando una lista vinculada con un puntero de cola, entonces el peor tiempo de ejecución para presionar, abrir, o mirar es O (1). Sin embargo, cada elemento tendrá una sobrecarga adicional asociada (es decir, el puntero), lo que significa que siempre hay una sobrecarga de O (n) para la estructura. Además, dependiendo de la velocidad de su asignador de memoria, el costo de asignar nuevos nodos para la pila puede ser notable. Además, si tuviera que desconectar continuamente todos los elementos de la pila, podría tener un golpe de rendimiento de una localidad pobre, ya que no hay garantía de que las celdas de la lista vinculada se almacenen contiguamente en la memoria.

Si implementa la pila con una matriz dinámica, entonces el tiempo de ejecución amortizado para presionar o estallar es O (1) y el costo en el peor de los casos es O (1). Esto significa que si te importa el costo de una sola operación en la pila, este puede no ser el mejor enfoque. Dicho esto, las asignaciones son poco frecuentes, por lo que es probable que el costo total de agregar o eliminar n elementos sea más rápido que el costo correspondiente en el enfoque basado en listas vinculadas. Además, la sobrecarga de memoria de este enfoque suele ser mejor que la sobrecarga de memoria de la lista vinculada. Si su matriz dinámica simplemente almacena punteros a los elementos, la sobrecarga de memoria en el peor de los casos se produce cuando se completan la mitad de los elementos, en cuyo caso hay n punteros adicionales (los mismos que en el caso cuando estaba usando el enlace list), y en el mejor de los casos cuando la matriz dinámica está llena, no hay celdas vacías y la sobrecarga adicional es O (1). Si, por otro lado, su matriz dinámica contiene directamente los elementos, la sobrecarga de memoria puede empeorar en el peor de los casos. Finalmente, debido a que los elementos se almacenan contiguamente, hay mejor localidad si desea presionar continuamente o extraer elementos de la pila, ya que todos los elementos están uno al lado del otro en la memoria.

En breve:

El enfoque de lista enlazada tiene las garantías O (1) del peor caso en cada operación; la matriz dinámica ha amortizado O (1) garantías.
La localidad de la lista vinculada no es tan buena como la localidad de la matriz dinámica.
Es posible que la sobrecarga total de la matriz dinámica sea más pequeña que la sobrecarga total de la lista vinculada, suponiendo que ambos punteros de tienda están en sus elementos.
La sobrecarga total de la matriz dinámica es probable que sea mayor que la de la lista vinculada si los elementos se almacenan directamente.

Ninguna de estas estructuras es claramente "mejor" que la otra. Realmente depende de tu caso de uso. La mejor manera de descubrir cuál es más rápido sería cronometrar ambos y ver cuál funciona mejor.

¡Espero que esto ayude!

Bueno, para la pregunta de objetos pequeños frente a objetos grandes, considere cuánto espacio extra usar para una lista vinculada si tiene pequeños objetos en su pila. Luego, considere cuánto espacio adicional necesitará si tiene un montón de objetos grandes en su pila.

A continuación, considere las mismas preguntas, pero con una implementación basada en matrices dinámicas.

Cambiar el tamaño de la matriz dinámica no sería una tarea costosa si diseña bien su implementación.

Por ejemplo, para hacer crecer la matriz, si está llena, cree una nueva matriz de dos veces el tamaño y copie los elementos.

Usted terminará con un costo amortizado de ~ 3N por agregar N artículos.

Creo que respondiste la pregunta tú mismo. Para una pila con una gran cantidad de elementos, la matriz dinámica tendría costos indirectos excesivos (sobrecarga de copia) cuando simplemente se agrega un elemento adicional a la parte superior de la pila. Con una lista, es un simple cambio de punteros.

Lo que importa es la cantidad de veces que se llama a malloc () en el curso de ejecutar una tarea. Podría llevar de cientos a miles de instrucciones obtener un bloque de memoria. (El tiempo en free () o GC debe ser proporcional a eso.) Además, mantenga un sentido de perspectiva. Esto podría ser el 99% del tiempo total, o solo el 1%, dependiendo de qué más esté sucediendo.