Πώς να συνεργαστεί με πολύ μεγάλες χορδές σε Python;

ψήφοι
5

Είμαι αντιμετώπιση της Euler έργου πρόβλημα 220 (φαινόταν εύκολο, σε σχέση με ορισμένα από τα άλλα - σκέφτηκα ότι θα δοκιμάσετε ένα υψηλότερο αριθμημένο ένα για μια αλλαγή!)

Μέχρι στιγμής έχω:

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

Τώρα, αυτό λειτουργεί μια χαρά για χαμηλές τιμές, αλλά όταν βάζετε να επαναλάβει υψηλότερη τότε μπορείτε να πάρετε μόνο ένα «σφάλμα μνήμης». Μπορεί κανείς να προτείνει έναν τρόπο για να ξεπεραστεί αυτό; Θέλω πραγματικά ένα string / αρχείο που περιέχει οδηγίες για το επόμενο βήμα.

Δημοσιεύθηκε 09/12/2008 στις 16:35
πηγή χρήστη
Σε άλλες γλώσσες...                            


6 απαντήσεις

ψήφοι
3

Το κόλπο είναι ενδιαφέρον παρουσιάζει το οποίο σχέδια προκύπτουν, όπως μπορείτε να εκτελέσετε το κορδόνι μέσα από κάθε επανάληψη. Δοκιμάστε την αξιολόγηση iterate(D,n)για n μεταξύ 1 και 10 και δείτε αν μπορείτε να τους εντοπίσετε. Επίσης τροφοδοτούν το κορδόνι μέσα από μια συνάρτηση που υπολογίζει την τελική θέση και τον αριθμό των βημάτων, και να αναζητήσουν πρότυπα εκεί.

Στη συνέχεια, μπορείτε να χρησιμοποιήσετε αυτή τη γνώση για να απλοποιήσει τον αλγόριθμο σε κάτι που δεν χρησιμοποιεί αυτές τις χορδές καθόλου.

Απαντήθηκε 09/12/2008 στις 16:57
πηγή χρήστη

ψήφοι
2

χορδές Python δεν πρόκειται να είναι η απάντηση σε αυτό. Οι χορδές αποθηκεύονται ως αμετάβλητη πίνακες, έτσι ώστε κάθε μία από αυτές τις αντικαταστάσεις δημιουργεί μια εντελώς νέα σειρά σε μνήμη. Για να μην αναφέρουμε, το σύνολο των οδηγιών μετά από 10 ^ 12 βήματα θα πρέπει να είναι τουλάχιστον 1 TB σε μέγεθος εάν τα αποθηκεύσετε ως χαρακτήρες (και αυτό είναι με κάποιες μικρές συμπιέσεις).

Στην ιδανική περίπτωση, θα πρέπει να υπάρχει ένας τρόπος για να μαθηματικά (υπόδειξη, δεν υπάρχει) παράγουν την απάντηση σε ώρα πτήσης, έτσι ώστε να μην χρειάζεται να αποθηκεύσετε την ακολουθία.

Απλά χρησιμοποιήστε το string ως οδηγό για να καθορίσει μια μέθοδο η οποία δημιουργεί την πορεία σας.

Απαντήθηκε 09/12/2008 στις 18:42
πηγή χρήστη

ψήφοι
2

Αν το σκεφτείτε πόσα «Α» και «Β» χαρακτήρες υπάρχουν σε D (0), Δ (1), κλπ, θα δείτε ότι η σειρά παίρνει πολύ καιρό πολύ γρήγορα. Υπολογίστε πόσα χαρακτήρες υπάρχουν σε D (50), και τότε ίσως σκεφτείτε ξανά για το πού θα αποθηκεύσετε τόσο πολύ τα δεδομένα. Ι καθιστούν 4,5 * 10 ^ 15 χαρακτήρες, η οποία είναι 4500 ΤΒ κατά ένα byte ανά char.

Ελάτε να σκεφτείτε από το, δεν χρειάζεται να υπολογίσει - το πρόβλημα σας λέει ότι υπάρχουν 10 ^ 12 βήματα, τουλάχιστον, το οποίο είναι ένα terabyte δεδομένων σε ένα byte ανά χαρακτήρα, ή τρίμηνο του ότι εάν χρησιμοποιείτε κόλπα για να πιάσουμε σε 2 bits ανά χαρακτήρα. Νομίζω ότι αυτό θα μπορούσε να προκαλέσει προβλήματα με την προθεσμία του ενός λεπτού σε κάθε είδους μέσο αποθήκευσης έχω πρόσβαση στο :-)

Απαντήθηκε 09/12/2008 στις 16:51
πηγή χρήστη

ψήφοι
1

Ακριβώς όπως μια λέξη της προειδοποίησης πρέπει να είστε προσεκτικοί όταν χρησιμοποιείτε τη λειτουργία αντικαταστήσει (). Αν χορδές σας είναι πολύ μεγάλο (στην περίπτωσή μου ~ χαρακτήρες 5E6) η λειτουργία αντικαταστήσει θα επιστρέψει ένα υποσύνολο του string (περίπου ~ χαρακτήρες 4E6) χωρίς να ρίχνουν τυχόν λάθη.

Απαντήθηκε 08/11/2011 στις 21:02
πηγή χρήστη

ψήφοι
1

Από τη στιγμή που δεν μπορεί να υλοποιηθεί το string, θα πρέπει να το δημιουργήσει. Αν έχετε δώσει τα επιμέρους χαρακτήρες αντί να επιστρέψει το σύνολο εγχόρδων, ίσως να μπορεί να λειτουργήσει.

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

Κάτι τέτοιο θα κάνει την αντικατάσταση χωρίς να δημιουργεί μια νέα σειρά.

Τώρα, βέβαια, θα πρέπει να καλέσετε αναδρομικά, και στο κατάλληλο βάθος. Έτσι, κάθε απόδοση δεν είναι μόνο μια απόδοση, είναι κάτι λίγο πιο περίπλοκη.

Προσπαθώντας να μην λύσει αυτό για σας, γι 'αυτό θα το αφήσουμε εκεί.

Απαντήθηκε 09/12/2008 στις 16:56
πηγή χρήστη

ψήφοι
0

Θα μπορούσατε να αντιμετωπίζουν D ως αρχείο ροής byte.

Κάτι όπως:-

seedfile = ανοικτή ( 'D1.txt', 'νν')? seedfile.write ( "Fa")? seedfile.close ()? n = 0 ενώ (n

προειδοποίηση εντελώς αδοκίμαστες

Απαντήθηκε 09/12/2008 στις 17:40
πηγή χρήστη

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