Arbres: Listes liées vs tableaux (efficacité)

Question

Il s'agit d'une question d'affectation à laquelle j'ai des difficultés à formuler une réponse. "Supposons qu'un arbre puisse avoir jusqu'à k enfants par nœud, soit v le nombre moyen d'enfants par nœud, pour quelle (s) valeur (s) de v est-il plus efficace (en termes d'espace utilisé) de stocker le les nœuds enfants dans une liste liée par rapport au stockage dans un tableau? Pourquoi? "

Je crois que je peux répondre au "pourquoi?" plus ou moins en anglais clair - il sera plus efficace d'utiliser la liste chaînée car plutôt que d'avoir un tas de nœuds vides (ie des index vides dans le tableau si votre moyenne est inférieure au maximum) pour un noeud dans une liste chaînée lorsque vous remplissez une valeur. Par conséquent, si vous avez une moyenne de 6 enfants lorsque votre maximum est de 200, le tableau créera de l'espace pour les 200 enfants de chaque nœud lors de la création de l'arborescence, mais la liste liée allouera uniquement de l'espace pour le nœuds au besoin. Ainsi, avec la liste chaînée, l'espace utilisé sera approximativement (?) La moyenne; avec le tableau, espacé utilisé sera le max.

... Je ne vois pas quand il serait plus efficace d'utiliser la baie. Est-ce une question piège? Est-ce que je dois prendre en compte le fait que le tableau doit avoir une limite sur le nombre total de nœuds quand il est créé?

Answer 1

Pour de nombreux langages couramment utilisés, le module RAID doit attribuer des adresses de mémoire k au stockage (des données). Une liste à liaison unique nécessitera 2 adresses par nœud (données & ensuite). Une liste doublement liée nécessiterait 3 adresses par nœud.

Let n soit le nombre d'enfants d'un noeud particulier A:

• Le réseau utilise des adresses mémoire k
• La liste des liaisons simples, lié utilise 2 n adresses
• La liste doublement chaînée utilise 3 n adresses

La valeur k vous permet de déterminer si 2 n ou 3 n adresses seront en moyenne à un gain ou une perte par rapport à simplement stocker les adresses dans un tableau.

Answer 2

... Je ne vois pas quand il serait plus efficace d'utiliser la baie. Est-ce une question piège?

Ce n'est pas une question piège. Pensez à la mémoire overhead qu'une liste liée a. Comment une liste chaînée est-elle implémentée (par rapport à un tableau)?

Aussi (bien que cela dépasse le cadre de la question!), La consommation d'espace n'est pas le seul facteur décisif dans la pratique. La mise en cache joue un rôle important dans les processeurs modernes et le stockage des nœuds enfants individuels dans un tableau au lieu d'une liste liée peut améliorer considérablement la localisation du cache (et par conséquent les performances de l'arborescence).

Answer 3

Je pense que cela pourrait être une très bonne idée et très efficace dans de nombreux scénarios d'utiliser un LinkedList si l'élément de données on utilise a une logique intrinsèque pour un élément précédent et suivant de toute façon, par exemple un TimeTableItem ou tout ce qui est en quelque sorte lié au temps. Ceux-ci doivent implémenter une interface, donc l'implémentation LinkedList peut tirer parti de cela et ne doit pas envelopper les éléments dans ses propres objets de noeud. Insérer et supprimer serait beaucoup plus efficace ici que d'utiliser une implémentation List qui jongle en interne autour des tableaux.

Answer 4

Les tableaux doivent pré-allouer de l'espace mais nous pouvons les utiliser pour accéder très rapidement à n'importe quelle entrée.
Les listes allouent de la mémoire chaque fois qu'elles créent un nouveau nœud, ce qui n'est pas idéal car l'allocation de mémoire coûte
. Astuce: vous pouvez allouer tout le tableau en une seule fois, si vous le souhaitez, mais habituellement nous allouons,
disons, 4 entrées et nous le redimensionnons en doublant la taille lorsque nous avons besoin de plus d'espace.

Answer 5

Vous supposez que le tableau ne peut pas être réaffecté dynamiquement. Si c'est possible, le tableau gagne, car il ne doit pas être plus grand que k éléments (plus une surcharge constante), et parce qu'il n'a pas besoin de stockage par item pour les pointeurs.