Mam bardzo duże drzewo węzłów pamięci i muszę je przechodzić. Przekazywanie zwróconych wartości każdego węzła podrzędnego do ich węzła nadrzędnego. Należy to zrobić, dopóki wszystkie węzły nie będą miały bąbelków danych aż do węzła głównego.
Traversal działa w ten sposób.
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);
}
Działa to dobrze, ale martwię się, że stos wywołań ogranicza rozmiar drzewa węzłów.
Jak można przepisać kod, aby nie było wywołań rekurencyjnych Execute
?
c#
optimization
trees
Reactgular
źródło
źródło
Odpowiedzi:
Oto implementacja przejścia drzewa ogólnego przeznaczenia, która nie korzysta z rekurencji:
W twoim przypadku możesz to tak nazwać:
Najpierw użyj
Queue
zamiastStack
oddechu zamiast głębokości. Użyj a,PriorityQueue
aby uzyskać najlepsze pierwsze wyszukiwanie.źródło
Jeśli masz wcześniej oszacowanie głębokości drzewa, może wystarczy, aby Twoja skrzynka dostosowała rozmiar stosu? W języku C # od wersji 2.0 jest to możliwe przy każdym uruchomieniu nowego wątku, patrz tutaj:
http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increase-the-size-of-your-stack-net-memory-management-part-3.aspx
W ten sposób możesz zachować swój kod rekurencyjny, bez konieczności implementowania czegoś bardziej złożonego. Oczywiście, tworzenie nierekurencyjnego rozwiązania z własnym stosem może wymagać więcej czasu i pamięci, ale jestem prawie pewien, że kod nie będzie tak prosty jak na razie.
źródło
Nie można przechodzić przez strukturę danych w kształcie drzewa bez użycia rekurencji - jeśli nie używasz ramek stosu i wywołań funkcji dostarczonych przez Twój język, zasadniczo musisz zaprogramować własne wywołania stosu i funkcji, i jest to jest mało prawdopodobne, że uda ci się to zrobić w języku w bardziej efektywny sposób niż autorzy kompilatora na komputerze, na którym działałby twój program.
Dlatego unikanie rekurencji z obawy przed przekroczeniem limitów zasobów jest zwykle mylące. Oczywiście, przedwczesna optymalizacja zasobów jest zawsze mylona, ale w tym przypadku prawdopodobne jest, że nawet jeśli zmierzysz i potwierdzisz, że użycie pamięci jest wąskim gardłem, prawdopodobnie nie będziesz w stanie poprawić jej bez zejścia do poziomu autor kompilatora.
źródło