Jak przemierzać drzewo bez korzystania z rekurencji?

19

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?

Reactgular
źródło
8
Będziesz musiał albo utrzymywać własny stos, aby śledzić węzły, albo zmienić kształt drzewa. Zobacz stackoverflow.com/q/5496464 i stackoverflow.com/q/4581576
Robert Harvey
1
Znalazłem też dużą pomoc w tej wyszukiwarce Google , szczególnie Morrisa Traversala .
Robert Harvey
@RobertHarvey dziękuję Rob, nie byłem pewien, jakie warunki by to poszło.
Reactgular
2
Możesz być zaskoczony wymaganiami dotyczącymi pamięci, jeśli wykonałeś matematykę. Na przykład idealnie zbalansowane drzewo binarne teranode wymaga jedynie stosu o głębokości 40 pozycji.
Karl Bielefeldt
@KarlBielefeldt Zakłada jednak, że drzewo jest idealnie zrównoważone. Czasami trzeba modelować drzewa, które nie są zrównoważone, w takim przypadku bardzo łatwo jest wysadzić stos.
Servy

Odpowiedzi:

27

Oto implementacja przejścia drzewa ogólnego przeznaczenia, która nie korzysta z rekurencji:

public static IEnumerable<T> Traverse<T>(T item, Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next))
            stack.Push(child);
    }
}

W twoim przypadku możesz to tak nazwać:

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

Najpierw użyj Queuezamiast Stackoddechu zamiast głębokości. Użyj a, PriorityQueueaby uzyskać najlepsze pierwsze wyszukiwanie.

Servy
źródło
Czy mam rację sądząc, że po prostu spłaszczy to drzewo do kolekcji?
Reactgular
1
@MathewFoscarini Tak, to jest jego cel. Oczywiście nie musi to koniecznie stać się rzeczywistą kolekcją. To tylko sekwencja. Możesz iterować nad nim, aby przesyłać strumieniowo dane, bez konieczności wciągania całego zestawu danych do pamięci.
Servy
Nie sądzę, że to rozwiązuje problem.
Reactgular
4
Nie tylko przemierza wykres wykonując niezależne operacje, takie jak wyszukiwanie, ale agreguje dane z węzłów potomnych. Spłaszczanie drzewa niszczy informacje o strukturze, których potrzebuje do przeprowadzenia agregacji.
Karl Bielefeldt
1
Do waszej informacji Myślę, że jest to poprawna odpowiedź, której szuka większość osób szukających w Google. +1
Anders Arpi,
4

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.

Doktor Brown
źródło
Właśnie zrobiłem szybki test. Na moim komputerze mogłem wykonać 14000 wywołań rekurencyjnych przed osiągnięciem przepełnienia stosu. Jeśli drzewo jest zrównoważone, potrzebne są tylko 32 połączenia do przechowywania 4 miliardów węzłów. Jeśli każdy węzeł ma 1 bajt (co nie będzie), potrzeba 4 GB pamięci RAM, aby przechowywać zrównoważone drzewo o wysokości 32.
Esben Skov Pedersen
Miałem użyć wszystkich 14000 wywołań na stosie. Drzewo zajęłoby 2,6x10 ^ 4214 bajtów, jeśli każdy węzeł ma jeden bajt (który nie będzie)
Esben Skov Pedersen
-3

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.

Kilian Foth
źródło
2
To jest po prostu nieprawda. Z pewnością możliwe jest przemierzanie drzewa bez użycia rekurencji. To nie jest nawet trudne . Możesz to również zrobić bardziej efektywnie, dość trywialnie, ponieważ możesz zawrzeć tylko tyle informacji w jawnym stosie, ile jesteś pewien, że potrzebujesz do konkretnego przejścia, podczas gdy za pomocą rekurencji kończy się przechowywanie większej ilości informacji, niż w rzeczywistości potrzebujesz w wielu skrzynie
Servy
2
Ta kontrowersja pojawia się tu od czasu do czasu. Niektórzy plakaty uważają, że zrzucanie własnego stosu nie jest rekurencją, podczas gdy inni podkreślają, że robią to samo wyraźnie, co środowisko wykonawcze zrobiłoby w sposób dorozumiany. Nie ma sensu kłócić się o takie definicje.
Kilian Foth
Jak zatem definiujesz rekurencję? Zdefiniowałbym to jako funkcję, która wywołuje się w ramach własnej definicji. Z pewnością możesz przemierzać drzewo, nigdy tego nie robiąc, jak wykazałem w mojej odpowiedzi.
Servy
2
Czy jestem zły za to, że lubię klikać głos głosowania na osobę z tak wysoką liczbą powtórzeń? To rzadka przyjemność na tej stronie.
Reactgular
2
Chodź @Mat, to dziecięce rzeczy. Możesz się nie zgodzić, na przykład jeśli boisz się bombardowania zbyt głębokiego drzewa, to uzasadniona obawa. Możesz tak powiedzieć.
Mike Dunlavey