J'ai une très grande arborescence de nœuds de mémoire et j'ai besoin de traverser l'arbre. Passer les valeurs renvoyées de chaque nœud enfant à leur nœud parent. Cela doit être fait jusqu'à ce que tous les nœuds aient leur bulle de données jusqu'au nœud racine.
La traversée fonctionne comme ça.
private Data Execute(Node pNode)
{
Data[] values = new Data[pNode.Children.Count];
for(int i=0; i < pNode.Children.Count; i++)
{
values[i] = Execute(pNode.Children[i]); // recursive
}
return pNode.Process(values);
}
public void Start(Node pRoot)
{
Data result = Execute(pRoot);
}
Cela fonctionne bien, mais je crains que la pile d'appels limite la taille de l'arborescence des nœuds.
Comment le code peut-il être réécrit afin qu'aucun appel récursif ne Execute
soit effectué?
c#
optimization
trees
Reactgular
la source
la source
Réponses:
Voici une implémentation de traversée d'arbre à usage général qui n'utilise pas la récursivité:
Dans votre cas, vous pouvez l'appeler ainsi:
Utilisez une
Queue
au lieu d'unStack
pour respirer d'abord, plutôt que la profondeur d'abord. Utilisez unPriorityQueue
pour une meilleure première recherche.la source
Si vous avez au préalable une estimation de la profondeur de votre arbre, peut-être suffit-il que votre cas adapte la taille de la pile? En C # depuis la version 2.0, cela est possible chaque fois que vous démarrez un nouveau thread, voir ici:
http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx
De cette façon, vous pouvez conserver votre code récursif, sans avoir à implémenter quelque chose de plus complexe. Bien sûr, la création d'une solution non récursive avec votre propre pile peut être plus efficace en termes de temps et de mémoire, mais je suis sûr que le code ne sera pas aussi simple qu'il l'est pour l'instant.
la source
Vous ne pouvez pas traverser une structure de données sous la forme d'un arbre sans utiliser la récursivité - si vous n'utilisez pas les cadres de pile et les appels de fonction fournis par votre langage, vous devez essentiellement programmer votre propre pile et les appels de fonction, et c'est il est peu probable que vous parveniez à le faire dans le langage de manière plus efficace que les rédacteurs du compilateur sur la machine sur laquelle votre programme s'exécuterait.
Par conséquent, éviter la récursivité par crainte de rencontrer des limites de ressources est généralement malavisé. Certes, l'optimisation prématurée des ressources est toujours erronée, mais dans ce cas, il est probable que même si vous mesurez et confirmez que l'utilisation de la mémoire est le goulot d'étranglement, vous ne pourrez probablement pas l'améliorer sans descendre au niveau de la rédacteur du compilateur.
la source