Speichereffiziente Rekursion

Question

Ich habe eine Anwendung in C# geschrieben, die alle Wörter generiert, die aus einer Kombination von Buchstaben, Zahlen und wenigen Sonderzeichen bestehen können.

Das Problem ist, dass es nicht speichereffizient ist, da es Rekursion und auch eine Sammlung wie List anpasst.

Gibt es eine Möglichkeit, das Programm in einer Umgebung mit begrenztem Speicher laufen zu lassen?

Umair

Answer 1

Konvertieren Sie es in eine iterative Funktion.

Answer 2

Nun, Sie können die Zwischenergebnisse natürlich nicht im Speicher ablegen (es sei denn, Sie haben einen absurden Computer zur Verfügung); Sie müssen die Ergebnisse auf die Festplatte schreiben.

Die Rekursionstiefe hängt nicht von der Anzahl der berücksichtigten Zeichen ab, sondern von der maximalen Länge der Zeichenfolge, die Sie in Betracht ziehen wollen.

Zum Beispiel, meine Installation von Python 2.6.2 hat es standardmäßig Rekursion Grenze auf 1000 gesetzt. Argumentieren, ich sollte in der Lage sein, alle möglichen 1-1000 Länge Zeichenfolgen gegeben einen Zeichensatz innerhalb dieser Begrenzung zu generieren (jetzt, ich denke, die Rekursion Grenze gilt für die gesamte Stapeltiefe, so dass die tatsächliche Grenze weniger als 1000 sein kann).

Bearbeiten (Python-Beispiel hinzugefügt): Das folgende Python-Snippet erzeugt das, wonach Sie fragen (und beschränkt sich dabei auf die angegebenen Laufzeit-Stack-Limits):

from string import ascii_lowercase

def generate(base="", charset=ascii_lowercase):
    for c in charset:
        next = base + c
        yield next
        try:
            for s in generate(next, charset):
                yield s
        except:
            continue

for s in generate():
    print s

Man könnte im Wesentlichen das gleiche in C# durch try/catching auf StackOverflowException produzieren. Während ich dieses Update schreibe, läuft das Skript und beansprucht einen meiner Kerne. Die Speichernutzung liegt jedoch konstant bei weniger als 7 MB. Nun, ich bin nur auf stdout drucken, da ich nicht daran interessiert bin, das Ergebnis zu erfassen, aber ich denke, es beweist den Punkt oben ;)

Nachtrag zum Beispiel: Interessante Anmerkung: Wenn man sich die laufenden Prozesse genauer ansieht, ist Python im obigen Beispiel tatsächlich I/O-gebunden. Es verwendet nur 7% meiner CPU, während der Rest des Kerns gebunden ist, die Ergebnisse in meinem Befehlsfenster wiederzugeben. Das Minimieren des Fensters lässt Python auf 40% der gesamten CPU-Auslastung ansteigen, und das auf einem 2-Kern-Rechner.

Answer 3

Leider führt der C#-Compiler keine Optimierung des Heckaufrufs Das ist etwas, das Sie in diesem Fall wollen. Die CLR unterstützt das, Irgendwie aber man sollte sich nicht darauf verlassen.

Vielleicht liegt das außerhalb des Bereichs, aber vielleicht können Sie den rekursiven Teil Ihres Programms in F# schreiben? Auf diese Weise können Sie die garantierte Tail-Call-Optimierung nutzen und Teile Ihres C#-Codes wiederverwenden. Auch wenn die Lernkurve steil ist, ist F# eine geeignetere Sprache für diese kombinatorischen Aufgaben.

Answer 4

Eine weitere Überlegung: Wenn Sie eine Zeichenkette in C# verketten oder eine andere Methode zur Erzeugung einer Zeichenkette verwenden, belegt diese Zeichenkette ihren eigenen Speicher und bleibt möglicherweise eine Weile bestehen. Wenn Sie Millionen von Zeichenketten generieren, werden Sie wahrscheinlich eine gewisse Leistungseinbuße feststellen.

Wenn du deine vielen Fäden nicht behalten musst, würde ich sehen, ob es eine Möglichkeit gibt, die Erzeugung der Fäden zu vermeiden. Zum Beispiel, vielleicht haben Sie ein Zeichen-Array, das Sie halten aktualisieren, wie Sie durch die Zeichenkombinationen zu bewegen, und wenn Sie sie in eine Datei ausgeben, würden Sie sie ein Zeichen zu einer Zeit ausgeben, so dass Sie nicht haben, um die Zeichenfolge zu bauen.

Answer 5

Nun ... Ich bin nicht sicher, mit wem ich unter Ihnen gehen, aber ich habe die Lösung. Ich verwende mehr als einen Prozess, einen, der mit dem Benutzer interagiert und einen anderen, der die Wortkombinationen findet. Der andere Prozess findet 5000 Wörter, speichert sie und beendet sie. Die Kommunikation wird durch WCF erreicht. Das sieht ziemlich gut aus, denn wenn der Prozess beendet wird, wird der Speicher freigegeben.