Diferencias entre estructuras de datos estáticas y dinámicas

Question

¿Cuáles son las principales diferencias, ventajas y desventajas entre las estructuras de datos dinámicas y estáticas?

¿Bajo qué categorías caen las estructuras de datos más comunes?

¿Cómo podría saber en qué situación utilizar cada uno?

Answer 1

Para empezar con una simplificación excesiva:

Hay sólo unos pocos tipos básicos de estructuras de datos: arrays, listas y árboles. Todo lo demás se puede componer utilizando diferentes tipos de estas dos estructuras (por ejemplo, una tabla hash puede implementarse con una matriz para los valores hash y una lista para cada valor hash para manejar las colisiones).

De estas estructuras, las matrices son estáticas (es decir, su huella de memoria no varía con el tiempo a medida que se realizan operaciones) y todo lo demás es dinámico (es decir, en el caso general cambia la huella de memoria).

Las diferencias entre los dos tipos de estructuras pueden ser derivados de lo anterior:

• estático necesita el tamaño máximo a ser conocido de antemano, mientras dinámica puede adaptarse sobre la marcha
• estática no reasignar memoria no importa qué, por lo que puede tener requisitos de memoria garantizados

También hay otras diferencias, que sin embargo solo entran en juego si sus datos pueden ser ordenados. No puedo dar una lista extensa, ya que hay muchas estructuras dinámicas de datos que muestran diferentes características de rendimiento para diferentes operaciones ("agregar", "eliminar", "buscar") y por lo tanto no pueden colocarse todas bajo el mismo techo.

Una diferencia muy visible es que las matrices ordenadas requieren mover (posiblemente muchas) cosas en la memoria para cualquier operación que no sea "encontrar", mientras que las estructuras dinámicas generalmente realizan menos trabajo.

Así, para recapitular:

1. Si necesita una garantía sobre el uso máximo de la memoria, no tiene otra opción que una matriz.
2. Si tiene un límite superior difícil para su tamaño de datos, considere usar una matriz. Las matrices pueden ser aptas para problemas que requieren principalmente operaciones de agregar/quitar (mantener la matriz sin clasificar) y para aquellas que requieren principalmente operaciones de búsqueda (mantener la matriz ordenada), pero no para ambas al mismo tiempo.
3. Si no tiene un límite superior difícil, o si necesita que todos los add/remove/find sean rápidos, use un tipo apropiado de estructura dinámica.

Editar: no he mencionado gráficos, otro tipo de estructura de datos dinámica que posiblemente no puede estar compuesta de partes más simples (por definición, un árbol tiene exactamente un enlace que va "en" cualquier nodo, excepto la raíz, mientras que los gráficos pueden tener más de uno). Sin embargo, los gráficos realmente no se pueden comparar con otras estructuras en un escenario "lo que sería mejor usar", porque o bien necesita usar un gráfico o no (otras estructuras pueden exhibir un rendimiento diferente, pero al final todas respaldan el mismo conjunto de operaciones).

Answer 2

Siempre es al revés, si va con estática, entonces pierde memoria, mientras que en el caso de la dinámica, el rendimiento disminuirá. Un mejor diseño usaría las estructuras de datos de manera eficiente, no hay una respuesta perfecta.

Answer 3

Las estructuras de datos estáticos (SDS) son de tamaño fijo (por ejemplo, matrices), la cantidad de memoria una vez asignadas no puede cambiar en tiempo de ejecución mientras que las estructuras de datos dinámicas (DDS) tienen tamaño flexible. o reducir según sea necesario para contener los datos que se almacenarán.

SDS son estructuras de datos lineales que permiten un acceso rápido a elementos almacenados en ellas, pero las operaciones de inserción/eliminación son caras en comparación con DDS donde el acceso a los elementos es más lento pero la inserción/eliminación es más rápida.

La mayoría de los DS son Dynamic DS.

En el caso de SDS, el espacio se asigna antes de la inserción de datos real, por lo que puede desperdiciar espacio o puede ser insuficiente algunas veces, por lo que debe usarse solo en caso de conocer previamente la cantidad exacta de datos. se debe conocer en tiempo de ejecución DDS se debe utilizar.

Answer 4

Consejos simples

estructuras de datos dinámicos tienen las siguientes características:

• Posibilidad de añadir de manera eficiente, eliminar o modificar los elementos
• tamaño flexible
• uso eficaz de los recursos - porque los recursos se asignan en el tiempo de ejecución, según sea necesario.
• más lento el acceso a los elementos (cuando se compara con estructuras de datos estáticas)

estructuras de datos estáticas tienen las siguientes características:

• añadir, eliminar o modificar los elementos no es directamente posible. Si lo hace, es un proceso que consume recursos.
• Tamaño fijo.
• Recursos asignados en la creación de la estructura de datos, incluso si los elementos no contienen ningún valor.
• acceso más rápido a los elementos (en comparación con las estructuras de datos dinámicos)

En resumen, no es efectivo utilizar estructuras dinámicas para almacenar un conjunto de datos que se conocen, no cambiar. Usar una estructura de datos estática en tal caso ahorrará recursos del sistema y también proporcionará un acceso más rápido a los elementos. Si se sabe que el tamaño de los datos cambia, por otro lado, entonces use estructuras dinámicas.