Как работать с очень длинными строками в Python?
Я занимаюсь проектом 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
Теперь это отлично работает для низких значений, но когда вы устанавливаете повторение выше, вы просто получаете «Ошибка памяти». Может ли кто-нибудь предложить способ преодолеть это? Мне действительно нужна строка / файл, содержащий инструкции для следующего шага.
Я думал, что целью Project Euler было найти решения самостоятельно (по крайней мере, насколько это возможно). Ясно, что суть этого вопроса в том, чтобы заставить вас использовать свой мозг, а не компилятор / интерпретатор. :)
Мне просто было интересно, как преодолеть некоторые ограничения точности в python, а не как полностью решить проблему.
Ответы 6
Если вы подумаете о том, сколько символов «a» и «b» содержится в D (0), D (1) и т.д., вы увидите, что строка очень быстро становится очень длинной. Подсчитайте, сколько символов в D (50), а затем, возможно, подумайте еще раз о том, где бы вы могли хранить это количество данных. Я делаю это 4,5 * 10 ^ 15 символов, что составляет 4500 ТБ на один байт на символ.
Если подумать, вам не нужно вычислять - проблема говорит вам, что есть как минимум 10 ^ 12 шагов, что составляет терабайт данных по одному байту на символ, или четверть этого, если вы используете трюки, чтобы спуститься до 2 бит на символ. Я думаю, что это вызовет проблемы с ограничением времени в одну минуту на любом носителе, к которому у меня есть доступ :-)
Поскольку вы не можете материализовать строку, вы должны ее сгенерировать. Если вы отдаете отдельные символы вместо того, чтобы возвращать всю строку, вы можете заставить ее работать.
def repl220( string ):
for c in string:
if c == 'a': yield "aRbFR"
elif c == 'b': yield "LFaLb"
else yield c
Что-то вроде этого сделает замену без создания новой строки.
Теперь, конечно, вам нужно вызвать его рекурсивно и с соответствующей глубиной. Итак, каждый доход - это не просто доход, это нечто более сложное.
Пытаюсь не решать это за вас, поэтому я оставлю все как есть.
Хитрость заключается в том, чтобы заметить, какие закономерности возникают при прохождении строки через каждую итерацию. Попробуйте оценить iterate(D,n) для n от 1 до 10 и посмотрите, сможете ли вы их обнаружить. Также пропустите строку через функцию, которая вычисляет конечную позицию и количество шагов, и ищите там шаблоны.
Затем вы можете использовать эти знания, чтобы упростить алгоритм до того, что вообще не использует эти строки.
Вы можете рассматривать D как файл с байтовым потоком.
Что-то вроде:-
seedfile = open('D1.txt', 'w'); seedfile.write("Fa"); seedfile.close(); n = 0 while (nпредупреждение полностью непроверено
Строки Python не будут ответом на этот вопрос. Строки хранятся как неизменяемые массивы, поэтому каждая из этих замен создает в памяти совершенно новую строку. Не говоря уже о том, что набор инструкций после 10 ^ 12 шагов будет иметь размер не менее 1 ТБ, если вы сохраните их как символы (и это с некоторыми незначительными сжатиями).
В идеале должен быть способ математически (подсказка, есть) генерировать ответ на лету, чтобы вам никогда не приходилось сохранять последовательность.
Просто используйте строку как руководство для определения метода, который создает ваш путь.
В качестве предупреждения будьте осторожны при использовании функции replace (). Если ваши строки очень большие (в моем случае ~ 5e6 символов), функция замены вернет подмножество строки (около ~ 4e6 символов) без каких-либо ошибок.
+1, чтобы компенсировать совершенно ненужный (ИМХО) голос против.