Árboles: Listas vinculadas frente a matrices (Eficiencia)

Question

Esta es una pregunta de asignación que tengo problemas para redactar una respuesta.

"Supongamos que un árbol puede tener hasta k hijos por nodo. Sea v el número promedio de hijos por nodo. Para qué valor (es) de v es más eficiente (en términos de espacio utilizado) para almacenar el nodos secundarios en una lista vinculada versus almacenamiento en una matriz? ¿Por qué? "

Creo que puedo responder el "¿por qué?" más o menos en inglés sencillo: será más eficiente usar la lista vinculada porque, en lugar de tener un montón de nodos vacíos (es decir, índices vacíos en la matriz si su promedio es menor que el máximo) ocupando memoria, solo se asigna espacio para un nodo en una lista vinculada cuando en realidad está completando un valor.

Así que si tienes un promedio de 6 hijos cuando tu máximo es 200, la matriz creará espacio para los 200 hijos de cada nodo cuando se cree el árbol, pero la lista vinculada solo asignará espacio para el nodos según sea necesario. Entonces, con la lista enlazada, el espacio utilizado será aproximadamente (?) El promedio; con la matriz, espaciado utilizado será el máximo.

... No veo cuándo sería más eficiente usar la matriz. ¿Es esta una pregunta con trampa? ¿Debo tener en cuenta el hecho de que la matriz debe tener un límite en el número total de nodos cuando se crea?

Answer 1

Para muchos idiomas de uso común, la matriz requerirá la asignación de almacenamiento k direcciones de memoria (de los datos). Una lista de enlace único requerirá 2 direcciones por nodo (datos & a continuación). Una lista doblemente enlazada requeriría 3 direcciones por nodo.

Vamos n ser el número real de hijos de un determinado nodo A:

• La matriz utiliza direcciones k memoria
• La lista simplemente enlazada utiliza 2 n direcciones
• La lista de doble enlace utiliza 3 n direcciones

El valor k le permite determinar si 2 n o 3 n direcciones promediarán a una ganancia o pérdida en comparación con simplemente almacenar las direcciones en una matriz.

Answer 2

... No veo cuándo sería más eficiente usar la matriz. ¿Es esta una pregunta con trampa?

No es una pregunta engañosa. Piense en la memoria overhead que tiene una lista vinculada. ¿Cómo se implementa una lista vinculada (frente a una matriz)?

Además (¡aunque esto está fuera del alcance de la pregunta!), El consumo de espacio no es el único factor decisivo en la práctica. El almacenamiento en memoria caché desempeña un papel importante en las CPU modernas y el almacenamiento de los nodos secundarios individuales en una matriz en lugar de una lista vinculada puede mejorar la localidad de la memoria caché (y en consecuencia el rendimiento del árbol) de manera drástica.

Answer 3

Me imagino que podría ser una muy buena idea y muy eficiente en muchos escenarios usar LinkedList si el elemento de datos que se usa tiene lógica intrínseca para un elemento anterior y siguiente, por ejemplo un TimeTableItem o cualquier cosa que de alguna manera relacionado al tiempo. Estos deberían implementar una interfaz, por lo que la implementación de LinkedList puede aprovechar eso y no tiene que envolver los elementos en sus propios objetos de nodo. Insertar y eliminar sería mucho más eficiente aquí que usar una implementación de List que hace juegos malabares con las matrices.

Answer 4

Las matrices deben preasignar el espacio pero podemos usarlas para acceder muy rápido a cualquier entrada.
Las listas asignan memoria cada vez que crean un nuevo nodo, y eso no es ideal porque
gastos de asignación de memoria en el tiempo de CPU.

Consejo: puede asignar todo el conjunto a la vez, si se quiere, pero por lo general nos asigne,
digamos, 4 entradas y cambiar su tamaño al duplicar el tamaño cuando se necesita más espacio.

Answer 5

Está asumiendo que la matriz no se puede reasignar dinámicamente. Si puede, la matriz gana, porque no debe ser mayor que k elementos (más una sobrecarga constante), y porque no necesita almacenamiento por puntero para cada elemento.