Ich habe einen Quadtree in C # implementiert und bin auf ein merkwürdiges Vorkommnis gestoßen, bei dem die Rekursion besser abläuft als die Iteration, obwohl es aussieht, als müsste das Gegenteil der Fall sein.
Meine Knoten sehen so aus:
%Vor%Um den Baum zu durchlaufen, habe ich die folgende rekursive Methode benutzt, die ich auf dem Wurzelknoten aufruft:
%Vor%Meist aus Interesse habe ich versucht, eine iterative Methode zum Durchlaufen des Baumes zu erstellen.
Ich habe das folgende Feld zu jedem Knoten hinzugefügt: private QuadNode next , und wenn ich die Struktur erstelle, führe ich eine Breite-zuerst-Traversierung unter Verwendung einer Warteschlange durch, wobei das next -Feld jedes Knotens mit dem nächsten Knoten in der Zeile verknüpft wird. Im Wesentlichen habe ich eine einfach verknüpfte Liste von den Knoten des Baumes erstellt.
An dieser Stelle kann ich den Baum mit der folgenden Methode durchqueren:
Nachdem ich die Leistung jeder Methode getestet hatte, war ich sehr überrascht zu erfahren, dass die iterative Version konsistent und merklich langsamer ist als die rekursive Version. Ich habe das sowohl auf riesigen Bäumen als auch auf kleinen Bäumen getestet und die rekursive Methode ist immer schneller. (Ich habe eine Stopwatch für das Benchmarking verwendet)
Ich habe bestätigt, dass beide Methoden den gesamten Baum erfolgreich durchqueren und dass die iterative Version jeden Knoten genau wie geplant besucht , also ist es kein Problem mit der Verknüpfung zwischen ihnen.
Es scheint mir offensichtlich, dass die iterative Version besser funktionieren würde ... was könnte die Ursache dafür sein? Habe ich einen offensichtlichen Grund dafür übersehen, warum die rekursive Version schneller ist?
Ich verwende Visual Studio 2012 und Compiled unter Release, Any CPU (lieber 32-Bit deaktiviert).
Bearbeiten:
Ich habe ein neues Projekt eröffnet und einen einfachen Test erstellt, der auch meine Ergebnisse bestätigt.
Hier ist der vollständige Code: Ссылка
Der Code ist nicht kommentiert, aber ich denke, es ist ziemlich selbstdokumentierend.
Die Cache-Lokalität verbraucht Geschwindigkeit. Probieren Sie:
%Vor%Jetzt sollte die iterative Version 30/40% schneller sein als die rekursive Version.
Der Grund für die Langsamkeit ist, dass Ihr iterativer Algorithmus "Breite zuerst" statt "Tiefe zuerst" verwendet. Sie haben Ihre Elemente Tiefe zuerst erstellt, so dass sie Tiefe zuerst im Speicher sortiert sind. Mein Algorithmus erstellt die Traversierungsliste Depth First.
(Beachten Sie, dass ich eine Queue in LinkNodes() verwendet habe, um das Folgen zu vereinfachen, aber in Wahrheit könnten Sie es ohne) tun
Wenn Sie Ihren Code betrachten, scheinen beide Methoden gleich zu sein, ABER in der rekursiven Version besuchen Sie 4 Knoten in einer "Schleife", dh Sie "springen" nicht zwischen 3 Tests, während Sie iterativ "springen" "Zum Beginn der Schleife jeweils laufen. Ich würde sagen, wenn Sie fast ähnliches Verhalten sehen möchten, müssen Sie die iterative Schleife in etwas ausrollen wie:
%Vor%Tags und Links c# performance recursion complexity-theory iteration