18.5. Optimisation des opérations sur les listes

La troisième étape de l'algorithme Soundex est l'élimination des doublons successifs. Quelle est la meilleure manière de faire cela ?

Voici le code que nous avons pour l'instant dans soundex/stage2/soundex2c.py :

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

Voici les résultats du chronométrage de soundex2c.py :

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

La première chose à considérer est l'efficience de vérifier digits[-1] à chaque itération de la boucle. Est-ce que les index de listes sont coûteux ? Vaudrait-il mieux garder le dernier chiffre dans une variable et vérifier cette variable ?

Pour répondre à cette question, voici soundex/stage3/soundex3a.py :

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

soundex3a.py n'est pas plus rapide que soundex2c.py et peut-être même un peu plus lent (bien que la différence ne soit pas assez importante pour être sûr) :

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

Pourquoi soundex3a.py n'est-il pas plus rapide ? Il se trouve que les index de listes en Python sont extrêmement efficient. Accéder à digits2[-1] de manière répétée n'est pas du tout un problème. Par contre, maintenir manuellement une variable pour le dernier chiffre fait que nous avons deux affectations de variables pour chaque chiffre que nous stockons, ce qui supprime les petits bénéfices que nous pourrions avoir reçu de l'élimination de l'accès à la liste.

Essayons quelque chose de radicalement différent. S'il est possible de traiter une chaîne comme une liste de caractères, il devrait être possible d'utiliser une list comprehension pour parcourir la liste. Le problème est que notre code a besoin d'accéder au caractère précédent dans la liste et ce n'est pas facile à faire avec une simple list comprehension.

Cependant, il est possible de créer une liste d'index à l'aide de la fonction prédéfinie range() et d'utiliser cette liste pour chercher dans la liste chaque caractère qui diffère de celui qui le précède. Cela nous donnera une liste de caractères que nous pourrons convertir en chaîne avec la méthode de chaîne join().

Voici soundex/stage3/soundex3b.py :

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

Est-ce plus rapide ? En un mot, non.

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

Peut-être que les techniques employées jusqu'à maintenant sont un peu trop centrées sur les chaînes. Python peut convertir une chaîne en liste de caractères en une seule commande : list('abc') retourne ['a', 'b', 'c']. De plus, les listes peuvent être modifiée sur place très rapidement. Au lieu de construire une nouvelle liste (ou une nouvelle chaîne) de manière incrémentale, nous pourrions déplacer les éléments à l'intérieur de la liste.

Voici soundex/stage3/soundex3c.py, qui modifie une liste sur place et en supprime les doublons successifs :

    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)

Est-ce plus rapide que soundex3a.py ou soundex3b.py ? Non, en fait c'est la méthode la plus lente jusqu'à présent :

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

Nous n'avons fais aucun progrès du tout, à part essayer et rejeter plusieurs techniques «astucieuses». Le code le plus rapide que nous avons vu jusque là est celui de la méthode originelle, la plus évidente (soundex2c.py). Parfois, l'astuce ne paie pas.

Exemple 18.5. Meilleur résultat jusqu'à maintenant : soundex/stage2/soundex2c.py


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