Plongez au coeur de Python ,De débutant à expert

Il y a tellement de dangers liés à l'optimisation du code qu'il est difficile de savoir par quoi commencer.

Commençons par ceci :êtes-vous sûr que c'est vraiment nécessaire ? Votre code est-il si mauvais ? Cela vaut-il la peine de prendre le temps de l'ajuster ? Pendant la durée de vie de votre application, combien de temps sera passé à exécuter ce code, par rapport au temps passé à attendre un serveur de base de données distant ou à attendre une entrée utilisateur ?

Ensuite, êtes vous sûr que vous avez fini d'écrire le code ? L'optimisation prématurée, c'est comme mettre une cerise sur un gâteau à moitié cuit. Vous passez des heures ou des jours (ou plus) à optimiser les performances de votre code, simplement pour découvrir qu'il ne remplit pas sa tâche. C'est du temps perdu.

Cela ne veut pas dire que l'optimisation du code est inutile, mais vous devez considérer l'ensemble du système et décider si c'est la meilleure façon d'employer votre temps. Chaque minute que vous passez à optimiser votre code est une minute que vous n'utilisez pas pour ajouter des fonctionnalités, à écrire de la documentation, à jouer avec vos enfants ou à écrire des tests unitaires.

Ah oui, les tests unitaires. Cela va sans dire que vous devez avoir un jeu complet de tests unitaires avant de commencer les ajustements de performances. La dernière chose dont vous avez besoin est d'introduire des nouveaux bogues en modifiant vos algorithmes.

Ces mises en garde étant faites, examinons certaines techniques d'optimisation de code Python. Le code en question est une implémentation de l'algorithme Soundex. Soundex est une méthode utilisée au début du 20e siècle pour classer les patronymes pour le recensement aux Etats-Unis. Il groupe les noms dont la prononciation est semblable, de manière à ce que même si un nom était mal orthographié, il serait possible de le retrouver. Soundex est toujours utilisé pour la même raison, mais bien sûr nous utilisons maintenant des bases de données informatisées. La plupart des logiciels de base de données comprennent une fonction Soundex.

Il y a plusieurs variantes de l'algorithme Soundex. Voici celle que nous utiliserons dans ce chapitre.

• 1. La première lettre du nom n'est pas modifiée
• 2. Les lettres suivantes sont converties en chiffres, en fonction de la table suivante :
• B, F, P et V deviennent 1 C, G, J, K, Q, S, X et Z deviennent 2. D et T deviennent 3. L devient 4. M et N deviennent 5. R devient 6.
• 3. Les doublons consécutifs sont supprimés.
• 4. Les 9 sont supprimés.
• 5. Si le résultat fait moins de quatre caractères (la première lettre puis 3 chiffres), le résultat est complété de zéros.
• 6. Si le résultat fait plus de quatre caractères, tout ce qui suit le quatrième caractère est supprimé.

Par exemple, mon nom, Pilgrim, devient P942695. Il n'y a pas de doublons consécutifs, donc rien à faire à cette étape. Nous enlevons ensuite les 9, ce qui laisse P4265. C'est trop long, nous supprimons les caractères surnuméraires, ce qui laisse P426.

Un autre exemple : Woo devient W99, qui devient W9, qui devient W, qui est complété de zéros pour faire W000.

Voici une première tentative de fonction Soundex

Exemple 18.1. soundex/stage1/soundex1a.py▲

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):
"convert string to Soundex equivalent"

# Soundex requirements:
# source string must be at least 1 character
# and must consist entirely of letters
allChars = string.uppercase + string.lowercase
if not re.search('^[%s]+$' % allChars, source):
    return "0000"

# Soundex algorithm:
# 1. make first character uppercase
source = source[0].upper() + source[1:]

# 2. translate all other characters to Soundex digits
digits = source[0]
for s in source[1:]:
    s = s.upper()
    digits += charToSoundex[s]

# 3. remove consecutive duplicates
digits2 = digits[0]
for d in digits[1:]:
    if digits2[-1] != d:
        digits2 += d
    
# 4. remove all "9"s
digits3 = re.sub('9', '', digits2)

# 5. pad end with "0"s to 4 characters
while len(digits3) < 4:
    digits3 += "0"
    
# 6. return first 4 characters
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())

La chose la plus importante que vous devez savoir à propos de l'optimisation de code Python est que vous ne devez pas écrire vos propres fonctions de chronométrage.

Le chronométrage de petits segments de code est incroyablement complexe. Combien de temps processeur est consacré par votre ordinateur à l'exécution de code ? Y-a-t-il des choses tournant en tâche de fond ? En êtes vous sûr ? Tous les ordinateurs récents ont des processus s'exécutant en tâche de fond, certains tout le temps, d'autres de manière intermittente. Des tâches cron s'exécutent à intervalles réguliers, des services en tâche de fond se «réveillent» pour accomplir des tâches comme relever votre courrier électronique, se connecter à des serveurs de messagerie instantanée, vérifier les mises à jour disponibles, rechercher des virus, regarder si un disque a été inséré dans votre lecteur CD dans les 100 dernières nanosecondes etc. Avant de démarrer vos tests de chronométrage, fermez tous ces services et déconnectez-vous du réseau. Ensuite, fermez tout ce que vous avez oublié de fermer la première fois, puis fermez le service qui vérifie de manière incessante si vous êtes connecté au réseau, puis...

Il y a aussi la question des variations introduites par le framework de chronométrage lui-même. L'interpréteur Python a-t-il un cache des tables de méthodes ? Un cache des blocs de code compilés ? Des expressions régulières ? Votre code produit-il des effets de bord si il est exécuté plus d'une fois ? N'oubliez pas qu'il s'agit de fractions de secondes et que des petites erreurs dans votre framework de chronométrage produirons des distorsions irréparables des résultats

La communauté Python a un proverbe : «Python est livré avec les piles.» N'écrivez pas votre propre framework de chronométrage. Python 2.3 est livré avec un très bon framework appelé timeit.

La communauté Python a un proverbe : «Python est livré avec les piles.» N'écrivez pas votre propre framework de chronométrage. Python 2.3 est livré avec un très bon framework appelé timeit.▲

>>> import timeit
>>> t = timeit.Timer("soundex.soundex('Pilgrim')",
...     "import soundex")   ***1***
>>> t.timeit()              ***2***
8.21683733547
>>> t.repeat(3, 2000000)    ***3***
[16.48319309109, 16.46128984923, 16.44203948912]

>>> min(t.repeat(3, 1000000))
8.22203948912

La première chose que la fonction Soundex vérifie est que l'entrée est une chaîne non-vide composée de lettres. Quelle est la meilleure manière de faire cela ?

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

Exemple 18.3. Le meilleur résultat jusqu'à maintenant : soundex/stage1/soundex1e.py▲

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

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

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

L'étape finale de l'algorithme Soundex est de compléter les résultats courts par des zéros et de tronquer les résultats long. Quelle est la meilleure manière de faire cela ?

Voici ce que nous avons pour l'instant, tiré de soundex/stage2/soundex2c.py :

   digits3 = re.sub('9', '', digits2)
    while len(digits3) < 4:
        digits3 += "0"
    return digits3[:4]

Voici les résultats pour 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 à essayer est de remplacer l'expression régulière par une boucle. Voici le code de soundex/stage4/soundex4a.py :

    digits3 = ''
    for d in digits2:
        if d != '9':
            digits3 += d

Est-ce que soundex4a.py est plus rapide ? Oui, il l'est :

C:\samples\soundex\stage4>python soundex4a.py
Woo             W000 6.62865531792
Pilgrim         P426 9.02247576158
Flingjingwaller F452 13.6328416042

Mais il y a quelque chose qui cloche, une boucle pour enlever des caractères d'une chaîne ? Nous pouvons utiliser une simple méthode de chaîne pour ça. Voici soundex/stage4/soundex4b.py :

    digits3 = digits2.replace('9', '')

Est-ce que soundex4b.py est plus rapide ? C'est une bonne question, ça dépend de l'entrée :

C:\samples\soundex\stage4>python soundex4b.py
Woo             W000 6.75477414029
Pilgrim         P426 7.56652144337
Flingjingwaller F452 10.8727729362

La méthode de chaîne dans soundex4b.py est plus rapide que la boucle pour la plupart des noms, mais elle est en fait un peu plus lente que soundex4a.py dans les cas triviaux (pour des noms très courts). Les optimisations de performances ne sont pas toujours uniformes, des réglages qui rendent un cas plus rapide peuvent rendre d'autres cas plus lent. Dans le cas présent, la majorité des cas bénéficiera de la modification, donc nous allons la conserver, mais rappelons nous de ce principe.

Pour finir, examinons les deux dernières étapes de l'algorithme : compléter les résultats courts avec des zéros et tronquer les résultats long à quatre caractères. Le code dans soundex4b.py fait cela, mais il est horriblement inefficace. Regardons soundex/stage4/soundex4c.py pour voir pourquoi :

    digits3 += '000'
    return digits3[:4]

Pourquoi utiliser une boucle while pour compléter le résultat ? Nous savons à l'avance que nous allons tronquer le résultat à quatre caractères et que nous avons au moins un caractère (la première lettre, qui est passée sans modification de la variable source d'origine). Cela signifie que nous pouvons simplement ajouter trois zéros à la sortie, puis la tronquer. Il ne faut pas se laisser enfermer par la formulation précise du problème, envisager le problème sous un angle un peu différent peut amener à une solution plus simple.

Quels gains de vitesse avons nous obtenus dans soundex4c.py en supprimant la boucle while ? Ils sont assez significatifs :

C:\samples\soundex\stage4>python soundex4c.py
Woo             W000 4.89129791636
Pilgrim         P426 7.30642134685
Flingjingwaller F452 10.689832367

Pour finir, il y a encore quelque chose que nous pouvons faire pour rendre ces trois lignes de code plus rapide : nous pouvons les combiner en une seule ligne. Regardons soundex/stage4/soundex4d.py :

    return (digits2.replace('9', '') + '000')[:4]

Mettre tout ce code sur une seule ligne dans soundex4d.py est à peine plus rapide que dans soundex4c.py :

C:\samples\soundex\stage4>python soundex4d.py
Woo             W000 4.93624105857
Pilgrim         P426 7.19747593619
Flingjingwaller F452 10.5490700634

C'est aussi bien moins lisible, pour des gains minimes. Est-ce que ça en vaut la peine ? Il vaudrait mieux avoir de bons commentaires, les performances ne sont pas tout. Il faut toujours équilibrer l'optimisation des performances et la lisibilité (et donc la maintenabilité) d'un programme.

Ce chapitre a illustré plusieurs aspects importants des réglages de performances en Python et en général.

• Si vous avez le choix entre une expression régulière et une boucle, choisissez l'expression régulière. Le moteur d'expressions régulières est écrit en C et est exécuté en mode natif par votre ordinateur, les boucles sont écrites en Python et sont exécutées par l'interpréteur Python.
• Si vous devez choisir entre une expression régulière et une méthode de chaîne, choisissez la méthode de chaîne. Les deux sont écrites en C, il faut donc choisir le plus simple.
• Les recherches dans les dictionnaires sont rapides, mais les fonctions spécialisées comme string.maketrans et les méthodes de chaînes comme isalpha() sont plus rapide. Si Python a une méthode spécialisée pour remplir une tâche, utilisez-la.
• Ne soyez pas trop astucieux. Parfois l'algorithme le plus évident est aussi le plus rapide.
• N'en faites pas trop. Les performances ne sont pas tout.

J'insiste sur ce dernier point. Au cours de ce chapitre, nous avons rendu la fonction trois fois plus rapide et gagné 20 secondes sur 1 million d'appel de fonction. C'est bien. Mais réfléchissez, pendant l'exécution de ce million d'appels de fonction, combien de secondes sont passées par notre application à attendre une connexion de base de données, la fin d'une écriture disque ou une entrée de l'utilisateur ? Ne passez pas trop de temps à optimiser une algorithme, ou vous raterez des améliorations dans d'autres parties de votre programme. Il faut développer un instinct permettant de savoir le genre de code que Python exécute rapidement, corriger les erreurs grossières si vous les trouvez et laisser le reste tranquille.