18.4. Optimisation de la lecture d'un dictionnaire

La deuxième étape de l'algorithme Soundex est de convertir les caractères en chiffres suivant des règles précises. Quelle est la meilleure manière de procéder ?

La solution la plus évidente est de définir un dictionnaire ayant les caractères comme clés et le chiffre leur correspondant comme valeurs et de faire une lecture du dictionnaire pour chaque caractère. C'est cette méthode qui est employée dans soundex/stage1/soundex1c.py (la version la plus performante jusqu'à maintenant) :

charToSoundex = {"A": "9",
                 "B": "1",
                 "C": "2",
                 "D": "3",
                 "E": "9",
                 "F": "1",
                 "G": "2",
                 "H": "9",
                 "I": "9",
                 "J": "2",
                 "K": "2",
                 "L": "4",
                 "M": "5",
                 "N": "5",
                 "O": "9",
                 "P": "1",
                 "Q": "2",
                 "R": "6",
                 "S": "2",
                 "T": "3",
                 "U": "9",
                 "V": "1",
                 "W": "9",
                 "X": "2",
                 "Y": "9",
                 "Z": "2"}

def soundex(source):
    # ... input check omitted for brevity ...
    source = source[0].upper() + source[1:]
    digits = source[0]
    for s in source[1:]:
        s = s.upper()
        digits += charToSoundex[s]

Nous avons déjà chronométré soundex1c.py, voici le résultat que nous avions obtenu :

C:\samples\soundex\stage1>python soundex1c.py
Woo             W000 14.5341678901
Pilgrim         P426 19.2650071448
Flingjingwaller F452 30.1003563302

Ce code évident, mais est-ce la meilleure solution ? L'appel de upper() pour chaque caractère semble peu efficient, il vaudrait sans doute mieux appeler upper() une seule fois pour la chaîne entière.

Il y a aussi le fait de construire la chaîne digits de manière incrémentale. Construire des chaînes de cette manière est peu efficient car Python crée une nouvelle chaîne à chaque itération et efface l'ancienne.

Python est meilleur pour manipuler des liste et il peut traiter une chaîne comme une liste de caractères automatiquement. Les listes sont facilement transformables en chaînes grâce à la méthode de chaîne join().

Voici soundex/stage2/soundex2a.py, qui convertit les lettres en chiffres à l'aide de ↦ et lambda:


def soundex(source):
    # ...
    source = source.upper()
    digits = source[0] + "".join(map(lambda c: charToSoundex[c], source[1:]))

Ce qui est surprenant, c'est que soundex2a.py n'est pas plus rapide :

C:\samples\soundex\stage2>python soundex2a.py
Woo             W000 15.0097526362
Pilgrim         P426 19.254806407
Flingjingwaller F452 29.3790847719

Le coût de l'appel de la fonction lambda efface tous les gains de performances obtenus en considérant la chaîne comme une liste de caractères.

soundex/stage2/soundex2b.py utilise une list comprehension au lieu de ↦ et lambda:

    source = source.upper()
    digits = source[0] + "".join([charToSoundex[c] for c in source[1:]])

L'emploi d'une list comprehension dans soundex2b.py est plus rapide qu'utiliser ↦ et lambda dans soundex2a.py, mais toujours pas plus rapide que le code originel (la construction incrémentale d'une chaîne dans soundex1c.py) :

C:\samples\soundex\stage2>python soundex2b.py
Woo             W000 13.4221324219
Pilgrim         P426 16.4901234654
Flingjingwaller F452 25.8186157738

Il est temps d'essayer une approche radicalement différente. La lecture de dictionnaire est un outil générique. Les clés de dictionnaire peuvent être des chaînes de taille variable (ou beaucoup d'autres types de données), mais dans le cas présent, nous n'utilisons que des clés d'un seul caractère et des valeurs d'un seul caractère. Il se trouve que Python a une fonction spécialisée pour ce genre de situations : la fonction string.maketrans.

Voici soundex/stage2/soundex2c.py :

allChar = string.uppercase + string.lowercase
charToSoundex = string.maketrans(allChar, "91239129922455912623919292" * 2)
def soundex(source):
    # ...
    digits = source[0].upper() + source[1:].translate(charToSoundex)

Que se passe-t-il exactement ici ? string.maketrans crée une matrice de traduction entre deux chaînes : le premier argument et le second. Dans le cas présent, le premier argument est la chaîne ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz et le second la chaîne 9123912992245591262391929291239129922455912623919292. C'est exactement le motif de conversion que nous avions mis en place avec le dictionnaire. A correspond à 9, B à 1, C à 2 et ainsi de suite. Mais ce n'est pas un dictionnaire, c'est une structure de données spécialisée à laquelle on accède à l'aide de la méthode de chaîne translate, qui traduit chaque caractère vers le chiffre correspondant, selon la matrice définie par string.maketrans.

timeit montre que soundex2c.py est plus rapide que de définir un dictionnaire et construire la chaîne de manière incrémentale dans une boucle :

C:\samples\soundex\stage2>python soundex2c.py
Woo             W000 11.437645008
Pilgrim         P426 13.2825062962
Flingjingwaller F452 18.5570110168

Nous n'obtiendrons pas grand chose de mieux que ça. Python a une fonction spécialisée qui fait exactement ce que nous souhaitons, utilisons-là et passons à la suite.

Exemple 18.4. 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())