2

estoy muy lejos de saber resolver este ejercicio ¿alguien sabe como resolverlo?

Este es el ejercicio en cuestión: 4 kyu Sum Strings as Numbers

El ejercicio consiste en hacer una función que sume dos números en formato string, pero los números pueden tener más de 2 millones de cifras.

El código que tengo hecho simplemente suma cifra a cifra, porque pensé que python no podría convertir el string en un entero, pero parece que sí es capaz, por lo que creo que tardo más en hacer la suma con mi código que si los transformara directamente por separado he hiciera la suma después.

Así que, lo único que se me ocurre es dividir el problema en trozos, pero, aparte de no saber hacerlo, o si es posible hacer en la web ¿alguien sabe si es esa la solución?

No pretendo que alguien me lo resuelva, pero si algo de orientación.

Os dejo mí código, pero como comento, eso y nada, todo es nada:

def sum_strings(x, y):
    nx=x.lstrip("0")
    ny=y.lstrip("0")
    lx=len(nx)
    ly=len(ny)
    
    if lx==0:
        if ly==0: return "0"
        else: return ny
    elif ly==0: return nx

    if lx>ly: ny=("0"*(lx-ly))+ny       
    if ly>lx: nx=("0"*(ly-lx))+nx 
        
    carry=0
    sum=0
    aux=""
    for i in range(len(nx)-1,-1,-1):
        sum=int(nx[i])+int(ny[i])+carry
        carry=sum//10
        aux=str(sum%10)+aux
    if carry: aux="1"+aux
    return aux
4
  • No queda claro. ¿Tu código funciona?
    – Lobos
    Commented el 23 ene. 2023 a las 19:27
  • Sí, funcionar funciona perfectamente. Pero es demasiaaaaaaaaado lento. Resuelve todos los números menos las sumas con números gigantes (los que tienen 2 millones de cifras).
    – DPM
    Commented el 23 ene. 2023 a las 19:29
  • Puedes ver las soluciones de los demás si lo deseas.
    – Mateo
    Commented el 1 feb. 2023 a las 20:05
  • Puedes ver las soluciones de los demás de dos formas: una es resolviendo el acertijo; y la otra es desbloqueando la solución y que ya no te cuente la kata como resuelta.
    – DPM
    Commented el 2 feb. 2023 a las 10:21

1 respuesta 1

6

La lentitud de tu código se debe a esta línea:

        aux=str(sum%10)+aux

Eso es una concatenación de cadenas. Pero en python la concatenación es una operación muy ineficiente debido a que en realidad el intéprete debe hacer lo siguiente:

  • Crear una nueva cadena para guardar el resultado
  • Rellenar esa cadena con la concatenación de las dos que has sumado
  • Asignar la variable aux a la nueva cadena (con lo que la cadena a la que previamente "apuntaba" aux deja de tener referencias)
  • Liberar la memoria ocupada por la cadena a la que previamente apuntaba aux (esto lo hace el recolector de basura de Python al detectar que esa cadena ya no tiene referencias)

Es decir, por cada iteración de tu bucle es necesario hacer el alloc de una nueva cadena, copia de la cadena antigua, y dealloc de la vieja. Además del tiempo extra requierido por los alloc/dealloc (que no es nada desdeñable), ya que la cadena va creciendo en cada iteración, la copia va tomando cada vez más tiempo.

El código se puede hacer mucho más eficiente si en lugar de ir concatenando resultados sobre la variable aux, simplemente vas metiendo en una lista las cifras que vas computando. Añadir elementos a una lista es mucho más eficiente para Python porque lo hace sobre la misma lista, en lugar de tener que crear otra y copiar como le sucede con las cadenas (esto es porque las listas son mutables, pero las cadenas son inmutables).

Una vez has terminado de crear la lista, la función usará "".join(lista) para concatenar todos los resultados en una sola cadena. Esta concatenación es muy eficiente porque está implementada en una sola instrucción python (que el intérprete ejecuta mediante código especialmente optimizado para este caso).

Además, puedes hacer la inserción de los caracteres en la lista por detrás en lugar de por delante. Esto también es más eficiente, pues insertar un caracter al inicio de una lista implica mover (y por tanto copiar) todos los demás una posición más adelante, mientras que insertar por el final no requiere movimiento ni copia alguna. Naturalmente al final podrás usar reversed() para recorrer esa lista en orden inverso.

Es decir, retocando tu código con estas ideas quedaría así:

def sum_strings(x, y):
    nx=x.lstrip("0")
    ny=y.lstrip("0")
    lx=len(nx)
    ly=len(ny)
    
    if lx==0:
        if ly==0: return "0"
        else: return ny
    elif ly==0: return nx

    if lx>ly: ny=("0"*(lx-ly))+ny       
    if ly>lx: nx=("0"*(ly-lx))+nx 
        
    carry=0
    sum=0
    aux=[]
    for i in range(len(nx)-1,-1,-1):
        sum=int(nx[i])+int(ny[i])+carry
        carry=sum//10
        aux.append(str(sum%10))
    if carry: aux.append("1")
    return "".join(reversed(aux))

Otra implementación

Esta es la primera que intenté yo, tras leer el enunciado del reto y antes de ver tu respuesta. Resulta que es básicamente equivalente a la tuya (con la mejora de usar listas en vez de cadenas), pero implementada usando una función generadora auxiliar. No creo que esto la haga más eficiente. Al principio creí que sí, pues el generador no necesita ir almacenando sus resultados, pero al final, al tratar de aplicar reversed() sobre esos resultados necesité convertirlo de todas formas en una lista, por lo que no se gana nada con la versión generadora. La dejo aquí de todas formas como curiosidad y por si no conocías esta faceta de python. Esta versión también tiene de novedoso el uso de zip_longest() que me pareció apropiada para este problema.

from itertools import zip_longest

def sum_generator(x,y):
    # Esta función devuelve los dígitos de la respuesta, uno
    # a uno y en orden inverso, sin necesidad de almacenarlos
    carry = 0
    for d_x, d_y in zip_longest(reversed(x), reversed(y), fillvalue="0"):
        s = int(d_x) + int(d_y) + carry
        carry = s // 10
        yield str(s%10)
    if carry:
        yield "1"
        
# Esta es la función "principal", que hace uso de la anterior
def sum_strings(x, y):
    # Ocuparse de espacios al inicio
    x = x.lstrip()
    y = y.lstrip()
    # Ocuparse de ceros al inicio
    x = x.lstrip("0")
    y = y.lstrip("0")
    # Ocuparse de cadenas vacías
    if not x: x="0"
    if not y: y="0"
    # Optimizar algunos casos triviales
    if x=="0": return y
    if y=="0": return x
    
    # La verdadera computación está aqui
    return "".join(reversed([c for c in sum_generator(x, y)]))
9
  • Muchas gracias por tu respuesta y solución. Me ha parecido increíble ver cuan ineficaz es trabajar con strings, siempre había pensado que no se diferenciaría de las listas (supongo que porque las utilizo prácticamente igual). He probado ambos métodos y los dos pasan el ejercicio. También, he medido el tiempo de ejecución y he visto que con números pequeños apenas hay diferencia con mi código, pero que cuanto más grande es el número, menos tiempo ocupan tus códigos. Con números muy grandes llega a ser 15 veces más rápido, aunque no he podido medirlo con números de millones de cifras. ¡Gracias!
    – DPM
    Commented el 24 ene. 2023 a las 0:05
  • @DPM concatenar listas hace lo mismo que las cadenas. Cuando haces lista1 + lista2, se crea una tercera lista con los contenidos de ambas. Por lo que supongo que son igual de ineficases las sumas de listas.
    – Dante S.
    Commented el 24 ene. 2023 a las 14:15
  • 1
    Efectivamente, como dice @DanteS. si para añadir elementos a una lista haces lista = lista + otra_lista estarías incurriendo en el mismo problema que con cadenas. Para ese caso la versión eficiente es lista.extend(otra_lista). Y curiosamente la sintaxis lista += otra_lista es convertida a la segunda versión (la eficiente) en vez de la primera (la ineficiente). En general, en python, es falso que a+=b sea equivalente a a=a+b, aunque en algunos casos lo es (por ejemplo, si a y b son cadenas u otros tipos inmutables).
    – abulafia
    Commented el 24 ene. 2023 a las 14:25
  • @abulafia wow, no sabía que Python transformaba esa expresión en otra cosa. Interesante!
    – Dante S.
    Commented el 24 ene. 2023 a las 14:34
  • 1
    @DanteS. No es exactamente que la transforme, es que tiene su propio "dunder method". Cuando haces a+=b python intentará ejecutar el método a.__iadd__(b), pero si a no define ese método entonces hará a = a.__add__(b). Esto te da la oportunidad de definir en tus clases el operador += de forma diferente al operador + , oportunidad que las listas aprovechan (y probablemente los arrays numpy, pandas, etc)
    – abulafia
    Commented el 24 ene. 2023 a las 14:37

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.