2

realicé un kata en codewars que a mi me satisface porque funciona. Ahora bien, por lo visto es ineficiente por su tiempo de ejecucion. Realiza 444 tests: ¨Execution Timed Out (12000 ms)¨ ¿Cómo refactorizaríais el código para que fuese más rápido? ¿Con una expresión regular?. Los parámetros son dos Strings. Uno, es la palabra a buscar, y el otro, las fichas en donde buscar la palabra. el método devuelve True si se puede crear la palabra, y False si no se puede generar. Un saludo a todos!!

def scramble(chips, word):
for w in word:
    # ..is the letter on the chips?
    result = chips.find(w)
    if result != (-1):
        # ...we take it off
        chips = chips.replace(w,"",1)
    else:
        return False
return True

2 respuestas 2

3

Veamos qué hace tu función originalmente:

Testado en Atom/Hydrogen con Python 3.6

mensaje1 = "Hola, esto es una prueba y quiero ver tu resultado"
mensaje2 = "esto"
print(scramble(mensaje1, mensaje2))
print(mensaje1)
print(mensaje2)

Al ejecutar estas 5 líneas en un script, no parece que aparentemente haga nada. mensaje1 está inalterado y mensaje2, también, y scramble() devuelve true. Todo correcto hasta ahí.

Al hacer un print tras chips = chips.replace(w,"",1), es decir, print(chips), ahí sí observo qué está ocurriendo, y según Hydrogen, sale lo siguiente:

Hola, sto es una prueba y quiero ver tu resultado

Hola, to es una prueba y quiero ver tu resultado

Hola, o es una prueba y quiero ver tu resultado

Hla, o es una prueba y quiero ver tu resultado

Ahora que ya sabemos qué hace tu kata, vamos a aclarar cómo meterle mano:

La función replace tiene, entre otras, la obligación de buscar. Así que no necesitas buscar primero para reemplazar después. De ese modo te eliminas el condicional y la función de búsqueda.

La función de búsqueda es más lenta que la función de comparación ( O(n^2) frente a O(n) )

Como se podría mejorar sería utilizando una copia del original en una variable temporal, reemplazo en chips y return con la comparación. De este modo, eliminas una función de búsqueda innecesaria por una copia y una comparación.

El código que he probado sería tal que así:

def scramble2 (chips,word):
    chips2 = chips
    for w in word:
        chips2 = chips2.replace(w,"",1)
    return chips != chips2

Como ves, en menos líneas, obtienes el resultado. Hace exactamente lo mismo que el original, es decir, chips no se modifica y wo, tampoco.

cProfile es una herramienta estupenda para saber cómo de bien o mal lo estás haciendo. En mi caso, me ha devuelto lo siguiente:

12 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <ipython-input-44-e2f4d0e83b80>:1(scramble)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        4    0.000    0.000    0.000    0.000 {method 'find' of 'str' objects}
        4    0.000    0.000    0.000    0.000 {method 'replace' of 'str' objects}


         8 function calls in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <ipython-input-45-15a49fb9ac5b>:1(scramble2)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        4    0.000    0.000    0.000    0.000 {method 'replace' of 'str' objects}

El código que he usado para comprobar que lo que haces y lo que hago son similares, es el siguiente:

import cProfile


def scramble(chips, word):
    for w in word:
        # ..is the leter on the chips?
        result = chips.find(w)
        if result != (-1):
            # ...we take it off
            chips = chips.replace(w, "", 1)
        else:
            return False
    return True


def scramble2(chips, word):
    chips2 = chips
    for w in word:
        chips2 = chips2.replace(w, "", 1)
    return chips != chips2


if __name__ == '__main__':
    ch = "Hola, esto es una prueba y quiero ver tu resultado"
    wo = "esto"
    # print(scramble(ch,wo))
    # print(scramble2(ch,wo))
    cProfile.run('scramble(ch,wo)')
    cProfile.run('scramble2(ch,wo)')
10
  • 1
    Gracias José, eres muy amable . No comprendo del todo porque copiar Chips. Substrayendo una única ficha ya se diferenciaría. Que te parece que se compare el tamaño? Si se substrae diez fichas, y la palabra es de diez caracteres, entonces tenemos la palabra completa, en caso contrario, no se podrá realizar la palabra. Commented el 19 oct. 2018 a las 10:40
  • Los tiempos a la hora de copiar son lineales según el tamaño. La búsqueda que tú estás haciendo, según veo, implica que veas, elemento a elemento, en toda la tabla. Si, además de la búsqueda, haces un reemplazo sobre la copia, mejoras la velocidad de ejecución, porque buscar te obliga a comparar elemento a elemento, y además lo haces tantas veces como letras haya en word Commented el 19 oct. 2018 a las 10:48
  • Creo que te he entendido. solo necesito copiar una vez y comparar. Aun así, codewars me dice que sigo siendo lento. def scramble(chips, word): for w in word: chips2 = chips chips = chips.replace(w,"",1) if chips2 == chips: return False return True Commented el 19 oct. 2018 a las 10:57
  • Prueba a no copiar chips, a ver qué ocurre... Commented el 19 oct. 2018 a las 11:08
  • Estoy en ello. Tu código me falla los test. El mío los supera, pero sigue siendo lento. Para que lo compruebes por ti mismo te paso el enlace: (codewars.com/kata/55c04b4cc56a697bb0000048/train/python) Commented el 19 oct. 2018 a las 11:15
1

realicé un kata en codewars que a mi me satisface porque funciona. Ahora bien, por lo visto es ineficiente por su tiempo de ejecucion. Realiza 444 tests: ¨Execution Timed Out (12000 ms)¨ ¿Cómo refactorizaríais el código para que fuese más rápido? ¿Con una expresión regular?. Los parámetros son dos Strings. Uno, es la palabra a buscar, y el otro, las fichas en donde buscar la palabra. el método devuelve True si se puede crear la palabra, y False si no se puede generar. Un saludo a todos!!

Siguiendo esa premisa y el ejemplo que ha puesto Jose Manuel

EDITO

Tras revisar mejor el kata en codewars veo que se hacen comparaciones de strings de 80.000 caracteres, la mejor forma de lidiar con ello es reducirlos al máximo en cada iteración.

En base a ello hago una comprobación diferente a la propuesta por ti y por Jose, en lugar de comprobar letra por letra y eliminarla compruebo que el string tiene bastantes letras de un tipo para formar la palabra acto seguido elimino la letra de AMBAS variables reduciendo la longitud de ambas y por tanto reduciendo el tiempo de iteración en cada iteración.

En caso de no haber suficientes letras compruebo si la longitud de word es 0 y por tanto no hay nada mas que comprobar (durante las pruebas esto me ha hecho ganar dos segundos)

Paso la prueba de stack con algo menos de 8 segundos ^_^

El Codigo:

def scramble(s1: str, s2: str):
    for letter in s2:
        if s2.count(letter) <= s1.count(letter):
            s2 = s2.replace(letter, '')
            s1 = s1.replace(letter, '')
        else:
            return False 
        if len(s2) == 0:
            return True  
    return True
1
  • Wow, que forma mas inteligente y elegante de resolver el problema... Muchísimas gracias por tu respuesta. También a @José Manuel Ramos, he aprendido mucho con vuestros comentarios, muchísimas gracias, reitero.. Es una maravilla tener acceso a un foro en castellano en programación, para los que no somos tan sueltos con el inglés. Felicidades a los Administradores de SOF... Commented el 20 oct. 2018 a las 16:24

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.