Inmersión en Python

Éste es el código que hemos usado hasta ahora, en soundex/stage2/soundex2c.py:

    digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d

Éstos son los resultados de rendimiento de soundex2c.py:

C:\samples\soundex\stage2>python soundex2c.py
Woo             W000 12.6070768771
Pilgrim         P426 14.4033353401
Flingjingwaller F452 19.7774882003

Lo primero que debemos considerar es si es eficiente comprobar digits[-1] cada vez dentro del bucle. ¿Son costosos los índices de las listas? ¿Sería mejor mantener el último dígito en una variable aparte y mirar eso en su lugar?

La respuesta a esa pregunta está en soundex/stage3/soundex3a.py:

    digits2 = ''
    last_digit = ''
    for d in digits:
        if d != last_digit:
            digits2 += d
            last_digit = d

soundex3a.py no va nada más rápido que soundex2c.py, e incluso puede que vaya algo más lento (aunque no lo suficiente como para asegurarlo):

C:\samples\soundex\stage3>python soundex3a.py
Woo             W000 11.5346048171
Pilgrim         P426 13.3950636184
Flingjingwaller F452 18.6108927252

¿Por qué no es más rápido soundex3a.py? Resulta que los índices de las listas en Python son extremadamente eficientes. Acceder varias veces a digits2[-1] no es problema. Por otro lado, mantener el último dígito visto en una variable aparte significa que tenemos dos asignaciones de variables por cada dígito que almacenamos, lo que elimina cualquier pequeña ganancia que hubiéramos obtenido por eliminar la búsqueda en la lista.

Probemos algo totalmente diferente. Si es posible tratar una cadena como una lista de caracteres, debería ser posible usar una lista por comprensión para iterar sobre la lista. El problema es que el código necesita acceder al carácter previo en la lista, y no es fácil hacerlo con una lista por comprensión sencilla.

Sin embargo, es posible crear una lista de números índice usando la función range(), y usar esos números de índice para buscar progresivamente en la lista y extraer cada carácter que sea diferente del anterior. Esto nos dará una lista de caracteres y podemos usar el método de cadena join() para reconstruir una cadena partiendo de ella.

Éste es soundex/stage3/soundex3b.py:

    digits2 = "".join([digits[i] for i in range(len(digits))
                       if i == 0 or digits[i-1] != digits[i]])

¿Es más rápido? En una palabra, no.

C:\samples\soundex\stage3>python soundex3b.py
Woo             W000 14.2245271396
Pilgrim         P426 17.8337165757
Flingjingwaller F452 25.9954005327

Es posible que las técnicas hasta ahora hayan sido “centradas en la cadena”. Python puede convertir una cadena en una lista de caracteres con una sola orden: list('abc') devuelve ['a', 'b', 'c']. Más aún, las listas se pueden modificar muy rápidamente. En lugar de crear incrementalmente una nueva lista (o cadena) partiendo de la original, ¿por qué no trabajar con elementos dentro de una única lista?

Éste es soundex/stage3/soundex3c.py, que modifica una lista para eliminar elementos consecutivos duplicados:

    digits = list(source[0].upper() + source[1:].translate(charToSoundex))
    i=0
    for item in digits:
        if item==digits[i]: continue
        i+=1
        digits[i]=item
    del digits[i+1:]
    digits2 = "".join(digits)

¿Es más rápido que soundex3a.py o soundex3b.py? No, de hecho es el método más lento:

C:\samples\soundex\stage3>python soundex3c.py
Woo             W000 14.1662554878
Pilgrim         P426 16.0397885765
Flingjingwaller F452 22.1789341942

No hemos progresado nada aquí, excepto que hemos probado y eliminado varias técnicas “inteligentes”. El código más rápido que hemos visto hasta ahora fue el método original y más directo (soundex2c.py). Algunas veces ser inteligente no es una ventaja.

import string, re

allChar = string.uppercase + string.lowercase
charToSoundex = string.maketrans(allChar, "91239129922455912623919292" * 2)
isOnlyChars = re.compile('^[A-Za-z]+$').search

def soundex(source):
    if not isOnlyChars(source):
        return "0000"
    digits = source[0].upper() + source[1:].translate(charToSoundex)
    digits2 = digits[0]
    for d in digits[1:]:
        if digits2[-1] != d:
            digits2 += d
    digits3 = re.sub('9', '', digits2)
    while len(digits3) < 4:
        digits3 += "0"
    return digits3[:4]

if __name__ == '__main__':
    from timeit import Timer
    names = ('Woo', 'Pilgrim', 'Flingjingwaller')
    for name in names:
        statement = "soundex('%s')" % name
        t = Timer(statement, "from __main__ import soundex")
        print name.ljust(15), soundex(name), min(t.repeat())