Wie mit sehr langen Zeichenfolge in Python arbeiten?

stimmen
5

Ich bin der Bekämpfung Projekt Eulersche Problem 220 (sah einfach aus , im Vergleich zu einigen der anderen - dachte ich würde versuchen , einen höheren Nummer eins für eine Veränderung!)

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 dies für niedrige Werte in Ordnung, aber wenn man es höher zu wiederholen, dann Sie nur einen „Speicherfehler“ erhalten. Kann mir jemand eine Möglichkeit, dies zu überwinden vorschlagen? Ich möchte wirklich eine Zeichenfolge / Datei, die Anweisungen für den nächsten Schritt enthält.

Veröffentlicht am 09/12/2008 um 16:35
quelle vom benutzer
In anderen Sprachen...                            


6 antworten

stimmen
3

Der Trick ist , in Bemerken der Muster entstehen , wie Sie die Schnur durch jede Iteration ausgeführt werden . Versuchen Sie die Bewertung iterate(D,n)für n zwischen 1 und 10 und sehen , ob man sie erkennen kann. Auch füttern die Saite über eine Funktion, die die Endposition und die Anzahl der Schritte berechnet, und es auch nach Mustern suchen.

Anschließend können Sie dieses Wissen nutzen, um den Algorithmus zu etwas zu vereinfachen, dass diese Strings nicht überhaupt.

Beantwortet am 09/12/2008 um 16:57
quelle vom benutzer

stimmen
2

Python-Strings sind nicht die Antwort auf diese sein. Strings werden als unveränderlicher Arrays gespeichert, so dass jeder von diesen Ersetzungen schafft eine völlig neue Zeichenfolge in dem Speicher. Nicht zu vergessen, der Satz von Instruktionen nach 10 ^ 12 Schritten wird mindestens 1 TB groß sein, wenn man sich als Zeichen speichern (und das ist mit einigen kleineren Kompressionen).

Idealerweise sollte es eine Möglichkeit sein, mathematisch zu (Hinweis, es gibt), um die Antwort on the fly zu generieren, so dass Sie nie die Sequenz speichern müssen.

Verwenden Sie einfach die Zeichenfolge als Leitfaden eine Methode, um zu bestimmen, die Ihren Weg schafft.

Beantwortet am 09/12/2008 um 18:42
quelle vom benutzer

stimmen
2

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

Kommen Sie, daran zu denken, Sie müssen sich nicht berechnen - das Problem sagt Ihnen, es gibt 10 ^ 12 Stufen zumindest, was ein Terabyte Daten in einem Byte pro Zeichen ist, oder ein Viertel, wenn Sie Tricks nach unten bekommen auf 2 Bits pro Zeichen. Ich denke, diese Probleme mit dem einminütigen Zeitlimit für jede Art von Speichermedium verursachen würde ich den Zugang zu haben :-)

Beantwortet am 09/12/2008 um 16:51
quelle vom benutzer

stimmen
1

So wie ein Wort der Warnung vorsichtig sein, wenn die replace () Funktion. Wenn die Saiten sehr groß sind (in meinem Fall ~ 5E6 Zeichen) die Funktion ersetzen würde eine Teilmenge der Zeichenfolge zurück (um ~ 4E6 Zeichen) ohne Fehler zu werfen.

Beantwortet am 08/11/2011 um 21:02
quelle vom benutzer

stimmen
1

Da Sie nicht die Zeichenfolge materialisieren können, müssen Sie es erzeugen. Wenn Sie die einzelnen Zeichen anstelle der Rücksendung die gesamte Zeichenfolge ergeben, könnte bekommen Sie es zu arbeiten.

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

So etwas tut Ersatz ohne eine neue Zeichenfolge zu erstellen.

Nun, natürlich, müssen Sie es rekursiv nennen und auf die entsprechende Tiefe. So ist jede Ausbeute nicht nur eine Ausbeute, es ist etwas, ein wenig komplex.

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

Beantwortet am 09/12/2008 um 16:56
quelle vom benutzer

stimmen
0

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

Etwas wie:-

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

Warnung völlig ungetestet

Beantwortet am 09/12/2008 um 17:40
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more