18.6. Optimisation des manipulations de chaînes

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.