Wie mit sehr langen Zeichenfolgen in Python arbeiten?

Question

ich die Bekämpfung des Projekts euler problem 220 (sah einfach aus, im Vergleich zu einigen der anderen - dachte ich für eine Änderung eine höhere nummerierte man versuchen würde!)

Bisher habe ich:

D = "Fa" 

def iterate(D,num): 
    for i in range (0,num): 
     D = D.replace("a","A") 
     D = D.replace("b","B") 
     D = D.replace("A","aRbFR") 
     D = D.replace("B","LFaLb") 
    return D 

instructions = iterate("Fa",50) 

print instructions 

Jetzt funktioniert das gut für niedrige Werte, aber wenn Sie es höher wiederholen, dann erhalten Sie nur einen "Speicherfehler". Kann jemand einen Weg vorschlagen, dies zu überwinden? Ich möchte wirklich eine Zeichenfolge/Datei, die Anweisungen für den nächsten Schritt enthält.

Answer 1

Python Strings Warnung werden nicht auf diese eine die Antwort sein. Strings werden als unveränderliche Arrays gespeichert, so dass jeder dieser Ersatz schafft eine völlig neue Zeichenfolge In Erinnerung, ganz zu schweigen davon, dass die Menge der Anweisungen nach 10^12 Schritten mindestens 1 TB groß ist, wenn Sie sie als Zeichen speichern (und das mit einigen kleineren Komprimierungen).

Idealerweise sollte es einen Weg geben, mathematisch (Hinweis, es gibt) die Antwort im laufenden Betrieb zu generieren, so dass Sie nie die Sequenz speichern müssen.

Verwenden Sie einfach die Zeichenfolge als Richtlinie, um eine Methode zu bestimmen, die Ihren Pfad erstellt.

Answer 2

Wenn Sie darüber nachdenken, wie viele Zeichen "a" und "b" es in D (0), D (1) usw. gibt, werden Sie sehen, dass die Zeichenfolge sehr schnell sehr lang wird. Berechnen Sie, wie viele Zeichen es in D gibt (50), und denken Sie dann vielleicht noch einmal darüber nach, wo Sie so viele Daten speichern würden. Ich mache es 4,5 * 10^15 Zeichen, das ist 4500 TB bei einem Byte pro Zeichen.

Denken Sie daran, Sie müssen nicht berechnen - das Problem sagt Ihnen, es gibt mindestens 10^12 Schritte, das ist ein Terabyte Daten bei einem Byte pro Zeichen oder ein Viertel davon, wenn Sie verwenden Tricks um auf 2 Bits pro Charakter zu kommen. Ich denke, das würde Probleme mit dem Zeitlimit von einer Minute auf jedem Speichermedium verursachen, auf das ich Zugriff habe :-)

Answer 3

Da Sie die Zeichenfolge nicht materialisieren können, müssen Sie sie generieren. Wenn Sie die einzelnen Zeichen ausgeben, anstatt die ganze Zeichenfolge zurückzugeben, können Sie es zum Funktionieren bringen.

def repl220(string): 
    for c in string: 
     if c == 'a': yield "aRbFR" 
     elif c == 'b': yield "LFaLb" 
     else yield c 

So etwas wird Ersatz tun, ohne eine neue Zeichenfolge zu erstellen.

Jetzt müssen Sie es natürlich rekursiv aufrufen, und zwar mit der entsprechenden Tiefe. Jeder Ertrag ist also nicht nur ein Ertrag, sondern etwas komplexer.

Versuchen Sie nicht, das für Sie zu lösen, also werde ich es dabei belassen.

Answer 4

Der Trick besteht darin, festzustellen, welche Muster entstehen, wenn Sie die Zeichenfolge durch jede Iteration ausführen. Versuchen Sie, iterate(D,n) für n zwischen 1 und 10 zu bewerten und sehen Sie, ob Sie sie erkennen können. Geben Sie die Zeichenfolge auch über eine Funktion ein, die die Endposition und die Anzahl der Schritte berechnet, und suchen Sie dort auch nach Mustern.

Sie können dieses Wissen dann verwenden, um den Algorithmus auf etwas zu vereinfachen, das diese Zeichenfolgen überhaupt nicht verwendet.

Answer 5

Sie könnten D als Byte-Stream-Datei behandeln.

So etwas wie: -

Seedfile = open ('D1.txt', 'w'); seedfile.write ("Fa"); seedfile.close(); n = 0 während (n

völlig ungetestet

Answer 6

Wie ein Wort der Warnung vorsichtig sein, wenn Sie die Funktion replace() verwenden. Wenn Ihre Strings sehr groß sind (in meinem Fall ~ 5e6 Zeichen), würde die Replace-Funktion eine Teilmenge des Strings (um ~ 4e6 Zeichen) zurückgeben, ohne irgendwelche Fehler zu werfen.