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)]))