У меня очень большое в памяти дерево узлов и мне нужно пройти по дереву. Передача возвращенных значений каждого дочернего узла их родительскому узлу. Это должно быть сделано до тех пор, пока все узлы не получат свои пузырьки данных до корневого узла.
Обход работает так.
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);
}
Это работает нормально, но я беспокоюсь, что стек вызовов ограничивает размер дерева узлов.
Как можно переписать код, чтобы не было рекурсивных вызовов Execute
?
c#
optimization
trees
Reactgular
источник
источник
Ответы:
Вот реализация общего обхода дерева, которая не использует рекурсию:
В вашем случае вы можете назвать это так:
Сначала используйте
Queue
вместо aStack
поиск в дыхании, а не в глубину. ИспользуйтеPriorityQueue
для лучшего первого поиска.источник
Если у вас есть предварительная оценка глубины вашего дерева, может быть, для вашего случая достаточно адаптировать размер стека? В C # начиная с версии 2.0 это возможно, когда вы начинаете новый поток, смотрите здесь:
http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx
Таким образом, вы можете сохранить свой рекурсивный код без необходимости реализовывать что-то более сложное. Конечно, создание нерекурсивного решения с вашим собственным стеком может потребовать больше времени и памяти, но я уверен, что код не будет таким простым, как сейчас.
источник
Вы не можете просмотреть структуру данных в форме дерева без использования рекурсии - если вы не используете стековые фреймы и вызовы функций, предоставляемые вашим языком, вам, в основном, нужно программировать свой собственный стек и вызовы функций, и это маловероятно, что вам удастся сделать это в языке более эффективным способом, чем разработчики компилятора на компьютере, на котором будет работать ваша программа.
Поэтому избегание рекурсии из-за боязни ограничить ресурсы обычно ошибочно. Конечно, преждевременная оптимизация ресурсов всегда ошибочна, но в этом случае вполне вероятно, что даже если вы измеряете и подтверждаете, что использование памяти является узким местом, вы, вероятно, не сможете улучшить ее, не опустившись до уровня автор компилятора.
источник