Ich habe seit ein paar Stunden versucht, eine Antwort auf diese Frage im Internet und auf dieser Seite zu finden, und ich bin nicht ganz da.
Ich verstehe, dass .NET 1MB Apps zuweist, und dass es am besten ist, einen Stapelüberlauf durch Neucodierung zu vermeiden, statt die Stapelgröße zu erzwingen.
Ich arbeite an einer "Shortest Path" -App, die bis zu etwa 3000 Knoten funktioniert und an dieser Stelle überläuft. Hier ist die Methode, die Probleme verursacht:
%Vor%Als Referenz hat die Node-Klasse ein Mitglied:
%Vor%graph [] ist:
%Vor%Ich habe versucht, den Code so zu optimieren, dass er nicht mehr Gepäck als nötig von einer Iteration (Rekursion?) zur nächsten transportiert, sondern mit einem 100K-Knoten-Graphen, wobei jeder Knoten zwischen 1-9 Kanten hat Es wird ziemlich schnell das Limit von 1 MB erreichen.
Wie auch immer, ich bin neu in C # und Code-Optimierung, wenn mir jemand einige Hinweise geben könnte (würde ich nicht so) schätze es.
Vor einiger Zeit habe ich dieses Problem in meinem Blog untersucht. Oder vielmehr, ich habe ein verwandtes Problem untersucht: Wie findet man die Tiefe eines binären Baums ohne Rekursion? Eine rekursive Baumtiefe Lösung ist trivial, aber bläst den Stapel, wenn der Baum sehr unausgeglichen ist.
Ich empfehle, Wege zu suchen, dieses einfachere Problem zu lösen, und dann zu entscheiden, welche von ihnen, wenn überhaupt, an Ihren etwas komplexeren Algorithmus angepasst werden könnte.
Beachten Sie, dass die Beispiele in diesen Artikeln vollständig in JScript angegeben sind. Es sollte jedoch nicht schwierig sein, sie an C # anzupassen.
Hier beginnen wir mit der Definition des Problems.
Der erste Lösungsversuch ist die klassische Technik, die Sie wahrscheinlich anwenden werden: Definieren Sie einen expliziten Stack; Verwenden Sie es, anstatt sich darauf zu verlassen, dass das Betriebssystem und der Compiler den Stack für Sie implementieren. Das tun die meisten Leute, wenn sie mit diesem Problem konfrontiert sind.
Das Problem mit dieser Lösung ist, dass es ein bisschen durcheinander ist. Wir können noch weiter gehen, als nur unseren eigenen Stack zu machen. Wir können unsere eigene kleine domänenspezifische virtuelle Maschine erstellen, die ihren eigenen Heap-zugewiesenen Stack hat, und dann das Problem lösen, indem Sie ein Programm schreiben, das auf diese Maschine abzielt! Das ist eigentlich einfacher als es klingt; Der Betrieb der Maschine kann extrem hoch sein.
Und schließlich, wenn Sie wirklich ein Vielfraß für Bestrafung sind (oder ein Compiler-Entwickler), können Sie Ihr Programm in Continuation Passing Style umschreiben, wodurch die Notwendigkeit eines Stapels überhaupt entfällt:
CPS ist eine besonders clevere Methode, die implizite Stack-Datenstruktur vom Systemstapel auf den Heap zu verschieben, indem sie in den Beziehungen zwischen einer Gruppe von Delegierten codiert wird.
Hier sind alle meine Artikel über Rekursion:
Die klassische Technik zur Vermeidung tiefer rekursiver Stack-Dives besteht darin, Rekursionen einfach zu vermeiden, indem Sie den Algorithmus iterativ schreiben und Ihren eigenen "Stack" mit einer geeigneten Listendatenstruktur verwalten. Wahrscheinlich werden Sie diesen Ansatz hier aufgrund der schieren Größe Ihres Input-Sets benötigen.
Sie könnten den Code so konvertieren, dass er eine Arbeitswarteschlange verwendet und nicht rekursiv ist. Etwas im folgenden Pseudocode:
%Vor%Ich weiß, das ist kryptisch, aber es ist das Grundkonzept dessen, was Sie tun müssen. Da Sie nur 3000 Knoten mit Ihrem aktuellen Code bekommen, werden Sie bestenfalls 12 ~ 15k ohne irgendwelche Parameter erreichen. Sie müssen also die Rekursion vollständig beenden.
Ist Ihr Knoten eine Struktur oder eine Klasse? Wenn es ersteres ist, machen Sie es zu einer Klasse, so dass es auf dem Heap statt auf dem Stack zugewiesen wird.
Ich würde zuerst überprüfen, ob Sie tatsächlich den Stack überlaufen: Sie sehen tatsächlich eine StackOverflowException wird von der Laufzeitumgebung ausgelöst.
Wenn dies tatsächlich der Fall ist, haben Sie einige Optionen:
Option 1 ist nicht immer möglich und geht davon aus, dass die Regeln, die die CLR zum Generieren tailrecursiver Aufrufe verwendet, auch in Zukunft stabil bleiben. Der Hauptvorteil ist, dass Tail-Rekursion, wenn möglich, tatsächlich eine bequeme Möglichkeit ist, um rekursive Algorithmen zu schreiben, ohne die Klarheit zu opfern.
Option 2 ist mehr Arbeit, aber ist nicht sensitiv für die Implementierung der CLR und kann für jeden rekursiven Algorithmus implementiert werden (wobei Tail-Rekursion nicht immer möglich ist). Im Allgemeinen müssen Sie Zustandsinformationen zwischen Iterationen einer Schleife erfassen und weiterleiten, zusammen mit Informationen darüber, wie die Datenstruktur, die die Orte des Stapels einnimmt (normalerweise eine List & lt; & gt; oder Stack & lt; & gt; & gt;), & ldquor; entrollt "wird. Eine Möglichkeit, die Rekursion in die Iteration zu zerlegen, besteht in der Fortsetzungsübergabe .
Weitere Ressourcen zur C # Tail-Rekursion:
Ich würde zuerst sicherstellen, dass ich weiß, warum ich einen Stapelüberlauf bekomme. Liegt es tatsächlich an der Rekursion? Die rekursive Methode legt nicht viel auf den Stapel. Vielleicht liegt es am Speicher der Knoten?
Auch, BTW, ich sehe nicht, dass sich der Parameter end jemals ändert. Das legt nahe, dass es kein Parameter sein muss, der auf jedem Stack-Frame ausgeführt wird.
Tags und Links c# stack-overflow