Как работать с очень длинными строками в Python?

Question

Я занимаюсь проектом проблемы Эйлера 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

Теперь, это работает хорошо для низких значений, но если вы установите его, чтобы повторить выше, то вы просто получите «Ошибка памяти». Кто-нибудь может предложить способ преодолеть это? Я действительно хочу строку / файл, который содержит инструкции для следующего шага.

Answer 1

Хитрость в том, чтобы заметить, какие шаблоны появляются, когда вы проходите строку через каждую итерацию. Попробуйте оценить iterate(D,n) для n от 1 до 10 и посмотрите, сможете ли вы их заметить. Также введите строку через функцию, которая вычисляет конечную позицию и количество шагов, и ищите там паттерны.

Затем вы можете использовать эти знания, чтобы упростить алгоритм до того, что вообще не использует эти строки.

Answer 2

Строки Python не будут ответом на этот вопрос. Строки хранятся в виде неизменяемых массивов, поэтому каждая из этих замен создает в памяти совершенно новую строку. Не говоря уже о том, что набор инструкций после 10 ^ 12 шагов будет иметь размер не менее 1 ТБ, если вы сохраните их как символы (и это с некоторыми незначительными компрессиями).

В идеале должен быть способ математически (подсказка есть) генерировать ответ на лету, чтобы вам никогда не нужно было сохранять последовательность.

Просто используйте строку в качестве руководства, чтобы определить метод, который создает ваш путь.

Answer 3

Если вы подумаете о том, сколько символов «a» и «b» имеется в D (0), D (1) и т. Д., Вы увидите, что строка очень быстро становится очень длинной. Подсчитайте, сколько символов в D (50), а затем, возможно, подумайте еще раз о том, где вы будете хранить такое количество данных. Я делаю это 4,5 * 10 ^ 15 символов, что составляет 4500 ТБ на один байт на символ.

Если подумать, вам не нужно вычислять - проблема в том, что вам нужно минимум 10 ^ 12 шагов, терабайт данных на один байт на символ или четверть этого, если вы используете трюки чтобы получить до 2 бит на символ. Я думаю, что это вызовет проблемы с ограничением времени в одну минуту на любом типе носителя, к которому у меня есть доступ: -)

Answer 4

Так же, как предупреждение, будьте осторожны при использовании функции replace (). Если ваши строки очень большие (в моем случае ~ 5e6 символов), функция replace вернет подмножество строки (около ~ 4e6 символов) без каких-либо ошибок.

Answer 5

Поскольку вы не можете материализовать строку, вы должны сгенерировать ее. Если вы возвращаете отдельные символы вместо того, чтобы возвращать всю строку, вы можете заставить ее работать.

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

Нечто подобное может заменить, не создавая новую строку.

Теперь, конечно, вам нужно вызывать его рекурсивно и с соответствующей глубиной. Таким образом, каждый урожай не просто урожай, это что-то более сложное.

Стараюсь не решать это за вас, поэтому я оставлю это на этом.

Answer 6

Вы можете рассматривать D как файл потока байтов.

Что-то вроде: -

seedfile = open ('D1.txt', 'w'); seedfile.write ( "Закон"); seedfile.close (); n = 0 в то время как

предупреждение полностью не проверено