Ich habe eine Methode wie folgt, die eine Sammlung durchsucht und eine Bedingung rekursiv auswertet:
%Vor%Alternativ kann dies unter Verwendung eines Stapels implementiert werden, um Rekursion wie folgt zu vermeiden:
%Vor%Meine Frage ist, bietet die Stack-Version irgendwelche Leistungsvorteile, wenn die Tiefe der Struktur im Vergleich zur rekursiven Version groß ist?
Meine Frage ist, bietet die Stack-Version irgendwelche Leistungsvorteile, wenn die Tiefe der Struktur im Vergleich zur rekursiven Version groß ist?
Ja. Die rekursive Version ist unendlich langsamer als die iterative Version, wenn die Tiefe des Baums groß ist. Das liegt daran, dass die rekursive Version den Aufrufstapel durchbrennt, eine nicht aufzuhaltende Ausnahme außerhalb des Stapelspeichers verursacht und das Programm vor der Rückgabe von bool beendet. Die iterative Version wird dies nicht tun, bis Heap-Speicherplatz erschöpft ist und der Heap-Speicher möglicherweise tausende Male größer ist als der Stack-Speicherplatz.
Es ist offensichtlich eine schlechtere Leistung, überhaupt kein Ergebnis zu geben, als ein Ergebnis in einer begrenzten Zeit zu geben.
Wenn Ihre Frage jedoch wirklich lautet: "Bietet die Stack-Version einen Vorteil, wenn der Baum tief ist, aber nicht so tief, dass er den Stack durchbrennt", lautet die Antwort:
Sie haben das Programm bereits in beide Richtungen geschrieben. Führen Sie es aus und finden Sie es heraus. Zeigen Sie keine zufälligen Fremden im Internet Bilder von zwei Pferden und fragen Sie, welche schneller ist; Rennen sie und dann wirst du es wissen.
Auch: Ich würde geneigt sein, Ihr Problem zu lösen, indem Sie Methoden schreiben, die Traversals und jedes Element ergeben. Wenn Sie die Methoden IEnumerable<INode> BreadthFirstTraversal(this INode node) und IEnumerable<INode> DepthFirstTraversal(this INode node) schreiben können, müssen Sie nicht Ihre eigene Suche schreiben. Sie können einfach node.DepthFirstTraversal().Where(predicate).FirstOrDefault() sagen, wenn Sie suchen möchten.
Lassen Sie uns das zuerst klarstellen: Rekursion ist nicht für Geschwindigkeit. Alles, was es tut, kann mindestens genauso schnell und oft schneller mit Iteration durchgeführt werden. Die Vorteile von Recursion liegen in der Klarheit des Codes.
Wenn Sie nicht unbedingt den schnellstmöglichen Code benötigen (und ehrlich gesagt, Sie tun dies fast nie), ist die zweite (datenrekursive) Version nicht einmal eine Überlegung wert, da sie die Komplexität ohne guten Grund erhöht. Es ist besonders wertlos in C #, da jede Stack -Operation einen Methodenaufruf beinhaltet, und die Beseitigung der Rekursion geht hauptsächlich darum, die Methodenaufrufe loszuwerden. Sie arbeiten fast sicher hinzufügen und erzwingen Methodenaufrufe für Dinge, die die Laufzeitumgebung viel effizienter mit dem integrierten Stapel verarbeiten kann.
Eric macht einen vernünftigen Punkt über Stack-Überläufe , aber damit dies ein Problem sein könnte, würden Sie brauchen ein Baum Tausende von Knoten tief, oder Sie müssten von einem bereits tiefen Call-Stack suchen, oder das Prädikat müsste rekursiv selbst sein (möglicherweise durch Auslösen anderer Suchen). Mit einem sogar leicht ausgeglichenen Baum und einem Prädikat, das keine weitere Rekursion verursacht, sollte die Stapeltiefe kein Problem sein. Der Standard-Stack ist bereits groß genug, um eine gewisse Rekursion zu bewältigen, und kann bei Bedarf vergrößert werden.
Mit allen das sagte jedoch: Ich vermute, wie Sie sind, wie jeder ist, der beide Versionen nicht wirklich implementiert und getestet hat. Wenn dir das so wichtig ist, tippe mal darauf.
Die zweite Version hat mehrere Vorteile:
Sie können problemlos von DFS zu BFS wechseln, indem Sie eine Warteschlange anstelle eines Stapels verwenden.
Wenn die Tiefe zu groß ist, wird eine OutOfMemoryException ausgelöst, die bearbeitet werden kann. (Ich glaube, dass eine StackOverflowException automatisch erneut ausgelöst wird).
Leistung und Speichernutzung sind möglicherweise besser, da die rekursive Methode alle lokalen Variablen (einschließlich des generierten Compilers) auf dem Aufruf-Stack speichert.
Tags und Links c#