Heute wollte ich eine Methode implementieren, um ein beliebig tiefes Diagramm zu durchlaufen und es zu einem einzelnen Aufzählungszeichen zu reduzieren. Stattdessen habe ich zuerst ein wenig gesucht und folgendes gefunden:
%Vor%Theoretisch sieht das gut aus, aber in der Praxis habe ich herausgefunden, dass es wesentlich schlechter funktioniert als die Verwendung von äquivalentem handgeschriebenem Code (wenn die Situation eintritt), um einen Graphen zu durchlaufen und alles Notwendige zu tun. Ich vermute, dass dies der Fall ist, weil der Stack bei jeder Methode, die er zurückgibt, auf ein beliebig tiefes Level abrollt.
Ich vermute auch, dass diese Methode viel effizienter laufen würde, wenn die Rekursion eliminiert würde. Ich bin auch nicht sehr gut in der Beseitigung von Rekursion.
Kann jemand diese Methode umschreiben, um die Rekursion zu beseitigen?
Danke für jede Hilfe.
BEARBEITEN: Vielen Dank für die ausführlichen Antworten. Ich habe versucht, Benchmarking der ursprünglichen Lösung gegen Erics Lösung vs nicht mit einer Aufzählungsmethode und stattdessen rekursiv mit einem a Lambda und traveling, die Lambda-Rekursion ist deutlich schneller als eine der beiden anderen Methoden.
%Vor%Wo TraverseOld die ursprüngliche Methode ist, ist TraverseNew Erics Methode, und offensichtlich ist das Lambda das Lambda.
Auf meiner Maschine dauert TraverseOld 10127 ms, TraverseNew dauert 3038 ms, die Lambda-Rekursion dauert 1181 ms.
Ist das typisch, dass Enumerator-Methoden (mit Rendite-Return) 3-mal länger dauern können als die sofortige Ausführung? Oder geht hier etwas anderes vor?
Zunächst einmal sind Sie absolut richtig; Wenn der Graph n Knoten mittlerer Tiefe d hat, dann ergeben die naiven geschachtelten Iteratoren eine Lösung, die O (n * d) in der Zeit und O (d) im Stapel ist. Wenn d ein großer Bruchteil von n ist, kann dies ein O (n 2) -Algorithmus werden, und wenn d groß ist, kann der Stapel vollständig durchgeblasen werden.
Wenn Sie an einer Leistungsanalyse verschachtelter Iteratoren interessiert sind, sehen Sie sich den Blog-Beitrag des ehemaligen C # -Compiler-Entwicklers Wes Dyer an:
dasblinkenlight's Lösung ist eine Variation des Standardansatzes. Ich würde das Programm normalerweise so schreiben:
%Vor%Und wenn Sie mehrere Wurzeln haben:
%Vor%Beachten Sie, dass eine Traversierung nicht ist, was Sie wünschen, wenn Sie einen stark miteinander verbundenen Graphen oder einen zyklischen Graphen haben! Wenn Sie ein Diagramm mit nach unten zeigenden Pfeilen haben:
%Vor%dann ist die Traversierung A, B, D, C, D, C, D. Wenn Sie einen zyklischen oder verbundenen Graphen haben, dann ist das transitive closure das, was Sie wollen.
%Vor%Diese Variation liefert nur Objekte, die vorher nicht zurückgegeben wurden.
Ich bin auch nicht sehr gut darin, die Rekursion zu eliminieren.
Ich habe eine Reihe von Artikeln über Wege zur Beseitigung von Rekursion und über rekursive Programmierung im Allgemeinen geschrieben. Wenn dieses Thema Sie interessiert, sehen Sie:
Insbesondere:
Sie haben Recht, Bäume und Graphen rekursiv in Code gehend, der yield return eine große Quelle von Ineffizienz ist.
Im Allgemeinen schreiben Sie rekursiven Code mit einem Stack neu - ähnlich wie er normalerweise in kompiliertem Code implementiert wird.
Ich hatte keine Chance, es auszuprobieren, aber das sollte funktionieren:
%Vor%Sie können Rekursionen immer eliminieren, indem Sie die Grundlagen der Funktionsweise von Rekursion mit einem Stapel replizieren.
Verrückte intelligente theoretische Antwort: Ссылка
Sie können eine Warteschlange in Ihrem Code verwenden. Die Warteschlange kann als Liste initialisiert werden, wobei ein Element dem obersten Knoten entspricht. Dann müssen Sie jedes Element der Liste durchlaufen, beginnend mit dem ersten. Wenn das erste Element untergeordnete Knoten enthält, hängen Sie sie alle an das Ende der Warteschlange an. Dann gehe zum nächsten Element. Ihr Diagramm wird vollständig flach, wenn Sie das Ende der Warteschlange erreichen.