Plongez au coeur de Python

Si vous pensez que c'est avec une expression régulière, c'est que vous vous êtes laissé entrainer par vos bas instincts. Les expressions régulières ne sont presque jamais la bonne réponse, elles doivent être évitées à chaque fois que c'est possible. Pas seulement pour des raisons de performances, mais parce qu'elles sont difficiles à déboguer et à maintenir. Et aussi pour des raisons de performances.

Ce fragment de code tiré de soundex/stage1/soundex1a.py vérifie que l'argument de la fonction source est un mot constitué uniquement de lettres, long d'au moins une lettre (pas une chaîne vide) :

    allChars = string.uppercase + string.lowercase
    if not re.search('^[%s]+$' % allChars, source):
        return "0000"

Quelles sont les performances de soundex1a.py ? Pour rendre les choses plus simples, la section __main__ du scrupt contient le code suivant, qui appelle le module timeit, met en place un chronométrage avec trois différents noms et affiche le temps minimum de chaque test :

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

Alors, quelles sont les performances de soundex1a.py avec cette expression régulière ?

C:\samples\soundex\stage1>python soundex1a.py
Woo             W000 19.3356647283
Pilgrim         P426 24.0772053431
Flingjingwaller F452 35.0463220884

Comme nous pouvions nous y attendre, l'algorithme prend plus de temps lorsqu'on l'appelle avec un nom plus long. Il y a un certain nombre de choses que nous pouvons faire pour réduire cet écart, mais la nature de cet algorithme fait qu'il ne s'exécutera jamais en temps constant.

Une autre chose qu'il faut garder à l'esprit est que nous testons un échantillon représentatif de noms. Woo est un cas trivial puisqu'il est réduit à une seule lettre puis complété de zéros. Pilgrim est un cas normal, de longueur moyenne et composé d'un mélange de lettres significatives et ignorées. Flingjingwaller est extraordinairement long et contient des doublons consécutifs. D'autres tests pourraient être utiles, mais ceux-ci nous donnent déjà un bon échantillon de cas.

Et cette expression régulière ? Et bien, elle n'est pas efficiente. Puisque l'expression recherche un ensemble de caractères (A-Z en majuscules et a-z en minuscules), nous pouvons utiliser une syntaxe d'expression régulière abrégée. Voici soundex/stage1/soundex1b.py :

    if not re.search('^[A-Za-z]+$', source):
        return "0000"

timeit nous dit que soundex1b.py est un peu plus rapide que soundex1a.py, mais rien de transcendant :

C:\samples\soundex\stage1>python soundex1b.py
Woo             W000 17.1361133887
Pilgrim         P426 21.8201693232
Flingjingwaller F452 32.7262294509

Nous avons vu à la Section 15.3, «Refactorisation» que les expressions régulières peuvent être compilées et réutilisées pour avoir des résultats plus rapides. Puisque cette expression régulière ne change jamais d'un appel de la fonction à un autre, nous pouvons la compiler une fois pour toutes. Voici soundex/stage1/soundex1c.py :

isOnlyChars = re.compile('^[A-Za-z]+$').search
def soundex(source):
    if not isOnlyChars(source):
        return "0000"

L'utilisation d'une expression régulière compilée dans soundex1c.py est nettement plus rapide :

C:\samples\soundex\stage1>python soundex1c.py
Woo             W000 14.5348347346
Pilgrim         P426 19.2784703084
Flingjingwaller F452 30.0893873383

Mais est-ce la bonne manière ? La logique ici est simple : l'entrée source doit être non-vide et ne contenir que des lettres. Ne serait-il pas plus rapide d'écrire une boucle pour tester chaque caractère et de supprimer l'expression régulière ?

Voici soundex/stage1/soundex1d.py:

    if not source:
        return "0000"
    for c in source:
        if not ('A' <= c <= 'Z') and not ('a' <= c <= 'z'):
            return "0000"

En fait, cette technique dans soundex1d.py n'est pas plus rapide qu'avec une expression régulière compilée (bien qu'elle soit plus rapide qu'avec une expression régulière non-compilée) :

C:\samples\soundex\stage1>python soundex1d.py
Woo             W000 15.4065058548
Pilgrim         P426 22.2753567842
Flingjingwaller F452 37.5845122774

Pourquoi soundex1d.py n'est-il pas plus rapide ? La réponse est à trouver dans la nature interprétée de Python. Le moteur d'expressions régulières est écrit en C et compilé pour s'exécuter nativement sur votre ordinateur. Cette boucle, par contre, est écrite en Python et est exécutée par l'interpréteur Python. Même si cette boucle est relativement simple, elle n'est pas assez simple pour compenser la pénalité due à l'interprétation. Les expressions régulières ne sont jamais la bonne solution... sauf quand elles le sont.

Il se trouve que Python propose une méthode de chaîne peu connue. Vous pouvez être pardonné de ne pas la connaître car elle n'a jamais été mentionnée dans ce livre. Cette méthode est isalpha() et elle vérifie qu'une chaîne ne contient que des lettres.

Voici soundex/stage1/soundex1e.py:

    if (not source) and (not source.isalpha()):
        return "0000"

Quels gain de performances nous a apporté l'utilisation de cette méthode dans soundex1e.py ? Un gain assez important.

C:\samples\soundex\stage1>python soundex1e.py
Woo             W000 13.5069504644
Pilgrim         P426 18.2199394057
Flingjingwaller F452 28.9975225902

import string, re

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):
    if (not source) and (not source.isalpha()):
        return "0000"
    source = source[0].upper() + source[1:]
    digits = source[0]
    for s in source[1:]:
        s = s.upper()
        digits += charToSoundex[s]
    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())