¿Cómo trabajar con cadenas muy largas en Python?

votos
5

Estoy abordando el problema 220 del proyecto euler (parecía fácil, en comparación con algunos de los otros, ¡pensé que probaría un número más alto para variar!)

Hasta ahora tengo:

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

Ahora, esto funciona bien para valores bajos, pero cuando lo pones para repetir más alto, obtienes un Error de memoria. ¿Alguien puede sugerir una forma de superar esto? Realmente quiero una cadena / archivo que contenga instrucciones para el siguiente paso.

Publicado el 09/12/2008 a las 16:35
fuente por usuario
En otros idiomas...                            


6 respuestas

votos
3

El truco está en notar qué patrones surgen mientras ejecuta la cadena a través de cada iteración. Intente evaluar iterate(D,n)n entre 1 y 10 y vea si puede detectarlos. También alimente la cuerda a través de una función que calcula la posición final y el número de pasos, y busque patrones allí también.

A continuación, puede utilizar este conocimiento para simplificar el algoritmo a algo que no utiliza estas cadenas en absoluto.

Respondida el 09/12/2008 a las 16:57
fuente por usuario

votos
2

Las cadenas de Python no van a ser la respuesta a esta. Las cadenas se almacenan como matrices inmutables, por lo que cada una de esas sustituciones crea una cadena completamente nueva en la memoria. Sin mencionar que el conjunto de instrucciones después de 10 ^ 12 pasos tendrá al menos 1TB de tamaño si los almacena como caracteres (y eso con algunas compresiones menores).

Idealmente, debería haber una forma matemática (sugerencia, hay) de generar la respuesta sobre la marcha, para que nunca tenga que almacenar la secuencia.

Simplemente use la cadena como una guía para determinar un método que cree su camino.

Respondida el 09/12/2008 a las 18:42
fuente por usuario

votos
2

Si piensas cuántos personajes "a" y "b" hay en D (0), D (1), etc., verás que la cadena se hace muy larga muy rápidamente. Calcule cuántos personajes hay en D (50), y luego tal vez piense nuevamente dónde almacenará esa cantidad de datos. Lo hago con 4.5 * 10 ^ 15 caracteres, que es 4500 TB en un byte por char.

Ahora que lo pienso, no tienes que calcular: el problema te dice que hay 10 ^ 12 pasos por lo menos, que es un terabyte de datos en un byte por personaje, o un cuarto si usa trucos para bajar a 2 bits por personaje Creo que esto causaría problemas con el límite de tiempo de un minuto en cualquier tipo de medio de almacenamiento al que tenga acceso :-)

Respondida el 09/12/2008 a las 16:51
fuente por usuario

votos
1

Al igual que una palabra de advertencia tenga cuidado al utilizar la función replace (). Si las cuerdas son muy grandes (en mi caso ~ caracteres 5E6) la función de reemplazar volvería un subconjunto de la cadena (en torno a ~ caracteres 4E6) sin lanzar ningún error.

Respondida el 08/11/2011 a las 21:02
fuente por usuario

votos
1

Como no puedes materializar la cadena, debes generarla. Si cede los caracteres individuales en lugar de devolver toda la cadena, puede hacer que funcione.

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

Algo así hará el reemplazo sin crear una nueva cadena.

Ahora, por supuesto, debe llamarlo recursivamente y con la profundidad adecuada. Entonces, cada rendimiento no es solo un rendimiento, es algo un poco más complejo.

Tratando de no resolver esto por ti, así que lo dejo así.

Respondida el 09/12/2008 a las 16:56
fuente por usuario

votos
0

Puede tratar D como un archivo de flujo de bytes.

Algo como:-

seedfile = open ('D1.txt', 'w'); seedfile.write ("Fa"); seedfile.close (); n = 0 mientras (n

advertencia totalmente no probada

Respondida el 09/12/2008 a las 17:40
fuente por usuario

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