Como trabalhar com cordas muito longas em Python?

votos
5

Estou abordando de Euler projeto problema 220 (parecia fácil, em comparação com alguns dos outros - pensei que eu ia tentar uma maior numerados de um para uma mudança!)

Até agora eu tenho:

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

Agora, isso funciona bem para valores baixos, mas quando você colocá-lo para repetir maior, então você acabou de receber um erro de memória. Alguém pode sugerir uma maneira de superar isso? Eu realmente quero uma string / arquivo que contém instruções para a próxima etapa.

Publicado 09/12/2008 em 16:35
fonte usuário
Em outras línguas...                            


6 respostas

votos
3

O truque está em perceber que padrões emergem como você correr a corda através de cada iteração. Tente avaliar iterate(D,n)para n entre 1 e 10 e veja se você pode identificá-los. Também alimentar a corda através de uma função que calcula a posição final e o número de passos, e procurar padrões lá também.

então você pode usar esse conhecimento para simplificar o algoritmo para algo que não usar essas seqüências em tudo.

Respondeu 09/12/2008 em 16:57
fonte usuário

votos
2

cordas Python não vai ser a resposta a esta. Cordas são armazenadas como matrizes imutáveis, de modo que cada uma dessas substituições cria uma string inteiramente novo na memória. Para não mencionar, o conjunto de instruções depois de 10 ^ 12 etapas será de pelo menos 1 TB em tamanho, se você armazená-los como personagens (e isso é com algumas compressões menores).

Idealmente, deve haver uma maneira de matematicamente (dica, há) gerar a resposta em tempo real, para que você nunca precisa armazenar a seqüência.

Basta usar a corda como um guia para determinar um método que cria seu caminho.

Respondeu 09/12/2008 em 18:42
fonte usuário

votos
2

Se você pensar sobre quantas "a" e "b" personagens não estão em D (0), D (1), etc, você verá que a cadeia fica muito longo muito rapidamente. Calcule quantos caracteres existem em D (50), e então talvez pense novamente sobre onde você iria armazenar que muitos dados. I tornam 4,5 * 10 ^ 15 caracteres, que é 4500 TB em um byte por carvão animal.

Venha para pensar sobre isso, você não tem que calcular - o problema diz-lhe há 10 ^ 12 passos, pelo menos, que é um terabyte de dados em um byte por caractere, ou um quarto de que se você usar truques para descer 2 bits por caractere. Eu acho que isso poderia causar problemas com o tempo limite de um minuto em qualquer tipo de meio de armazenamento eu tenho acesso a :-)

Respondeu 09/12/2008 em 16:51
fonte usuário

votos
1

Assim como uma palavra de advertência ter cuidado ao usar a função replace (). Se as cordas são muito grandes (no meu caso ~ caracteres 5E6) a função de substituir retornaria um subconjunto da string (em torno de ~ caracteres 4E6) sem lançar quaisquer erros.

Respondeu 08/11/2011 em 21:02
fonte usuário

votos
1

Desde que você não pode materializar a corda, você deve gerá-lo. Se você produzir os caracteres individuais em vez de retornar a corda toda, você pode fazê-lo funcionar.

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

Algo como isso vai fazer a substituição sem criar uma nova string.

Agora, é claro, você precisa chamá-lo de forma recursiva, e à profundidade apropriada. Então, cada um rendimento não é apenas um rendimento, é algo um pouco mais complexo.

Tentando não resolver isso para você, então eu vou deixar por isso mesmo.

Respondeu 09/12/2008 em 16:56
fonte usuário

votos
0

Você poderia tratar D como um arquivo de fluxo de bytes.

Algo como:-

seedfile = aberto ( 'D1.txt', 'w'); seedfile.write ( "FA"); seedfile.close (); n = 0 while (n

alertando totalmente testado

Respondeu 09/12/2008 em 17:40
fonte usuário

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