Faire disparaître les globales?

Question

J'ai une série d'objets d'arbre avec une profondeur quelque part dans les années 20. Chacun des noeuds de cette arborescence doit avoir accès à la racine de son arborescence.

Quelques solutions:

1. Chaque nœud peut stocker directement une référence à la racine (gaspille de la mémoire)
   • Je peux calculer la racine au moment de l'exécution en "remontant". (cycles de déchets)
   • Je peux utiliser des champs statiques (mais cela revient à des globales)

Quelqu'un peut-il proposer une conception qui n'utilise pas de configuration globale (quelle que soit sa variante) mais qui est plus efficace que le n ° 1 ou le n ° 2 en mémoire ou en cycle, respectivement?

Modifier: Étant donné que j'ai un ensemble d'arbres, je ne peux pas simplement le stocker dans un fichier statique car il serait difficile de différencier les arbres. (merci maccullt)

Answer 1

Transmettez la racine en tant que paramètre des fonctions du nœud qui en ont besoin.

Modifier: les options sont vraiment les suivantes:

1. Stockez la référence racine dans le noeud
2. Ne stockez pas la référence racine du tout
3. Stockez la référence racine dans un global
4. Stockez la référence racine sur la pile (ma suggestion, modèle de visiteur ou récursif)

Je pense que cela toutes les possibilités, il n'y a pas d'option 5.

Answer 2

Pourquoi devriez-vous vous passer des globals? Je comprends que la stigmatisation des globals soit mauvaise et tout, mais parfois, la solution la plus rapide est simplement de disposer d’une structure de données globale comprenant tous les éléments.

Vous faites un compromis: la clarté du code et moins de problèmes futurs pour la performance. C'est le sens d'être 'Ne pas optimiser encore'. Étant donné que vous êtes au stade d’optimisation, il est parfois nécessaire de réduire la lisibilité et les bonnes pratiques de programmation en faveur de la performance. Je veux dire, les bidouilles au niveau des bits ne sont pas lisibles, mais elles sont rapides.

Je ne sais pas combien d'arbres vous avez, mais je choisirais personnellement l'option 1. À moins que vous ne traitiez avec plus de milliers d'arbres, les pointeurs ne représentent pas beaucoup plus que quelques chaînes. Si la mémoire est vraiment un problème très important, essayez les deux méthodes (elles semblent assez simples à mettre en œuvre) et exécutez-la via un profileur. Vous pouvez également utiliser l'excellent Process Explorer .

Modifier: L’une des applications sur laquelle je travaille a une arborescence de nœuds contenant environ 55 000 nœuds. Nous construisons l’arborescence mais nous maintenons également un tableau pour les recherches O (1). Bien mieux que le O (m * n) que nous obtenions en utilisant une méthode récursive FindNodeByID.

Answer 3

Passer la racine en tant que paramètre est généralement préférable. Si vous utilisez une sorte d'itérateur pour naviguer dans l'arborescence, une autre solution consiste à stocker une référence à cette racine.

Answer 4

Le point 1 est une optimisation prématurée de la mémoire. # 2 est une optimisation prématurée de la performance. Avez-vous profilé votre application pour déterminer si les goulots d'étranglement liés à la mémoire ou au processeur vous posent problème? Sinon, pourquoi sacrifier une conception plus gérable pour une "optimisation"? cela n'aide pas vos utilisateurs?

Je vous recommande fortement de choisir le numéro 2. Chaque fois que vous stockez quelque chose que vous pouvez calculer, vous mettez en cache. Il y a quelques fois où la mise en cache est une bonne idée, mais c'est aussi un casse-tête de maintenance. (Par exemple, que se passe-t-il si vous déplacez un nœud d'un arbre à un autre en changeant son parent mais en oubliant de mettre également à jour le champ racine?) Ne mettez pas en cache si vous n'avez pas à le faire.

Answer 5

Vous pouvez dériver une classe de TreeView puis ajouter une propriété statique singleton. De cette façon, vous ajoutez effectivement un champ global qui fait référence à une instance unique de la classe mais présente l’avantage d’être couvert par un espace de noms étendu à cette classe.

Answer 6

Ignorant le dégoût des classes internes, je pourrais définir une classe Tree et définir les nœuds en tant que classes Inner. Chacun des nœuds aurait accès à l'état de son arbre, y compris sa racine.

Cela pourrait finir par être identique à # 1, selon la manière dont Java relie les nœuds à leurs parents. (Je ne suis pas sûr et je vais devoir le profiler)