Tengo un árbol de nodos de memoria muy grande y necesito atravesar el árbol. Pasar los valores devueltos de cada nodo secundario a su nodo primario. Esto debe hacerse hasta que todos los nodos tengan su burbuja de datos hasta el nodo raíz.
El recorrido funciona así.
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);
}
Esto funciona bien, pero me preocupa que la pila de llamadas limite el tamaño del árbol de nodos.
¿Cómo se puede reescribir el código para que no Execute
se realicen llamadas recursivas ?
c#
optimization
trees
Reactgular
fuente
fuente
Respuestas:
Aquí hay una implementación transversal del árbol de propósito general que no utiliza la recursividad:
En su caso, puede llamarlo así:
Use una en
Queue
lugar de unaStack
para respirar primero, en lugar de buscar primero la profundidad. Use aPriorityQueue
para una mejor primera búsqueda.fuente
Si tiene una estimación de la profundidad de su árbol de antemano, ¿tal vez sea suficiente para su caso adaptar el tamaño de la pila? En C # desde la versión 2.0 esto es posible siempre que inicie un nuevo hilo, vea aquí:
http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx
De esa manera puede mantener su código recursivo, sin tener que implementar algo más complejo. Por supuesto, crear una solución no recursiva con su propia pila puede ser más eficiente en cuanto a tiempo y memoria, pero estoy bastante seguro de que el código no será tan simple como lo es por ahora.
fuente
No puede atravesar una estructura de datos en forma de árbol sin usar la recursividad: si no usa los marcos de pila y las llamadas de función proporcionadas por su idioma, básicamente tiene que programar sus propias llamadas de pila y función, y es es poco probable que logre hacerlo dentro del lenguaje de una manera más eficiente que los escritores del compilador en la máquina en la que se ejecutaría su programa.
Por lo tanto, evitar la recursividad por temor a toparse con los límites de recursos suele ser erróneo. Sin duda, la optimización prematura de los recursos siempre está mal orientada, pero en este caso es probable que incluso si mide y confirma que el uso de la memoria es el cuello de botella, probablemente no podrá mejorarlo sin descender al nivel de escritor compilador
fuente