You are here: Sommaire > Plongez au coeur de Python > Ajustements des performances > Optimisation des opérations sur les listes | << >> | ||||
Plongez au coeur de PythonDe débutant à expert |
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.
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())
<< Optimisation de la lecture d'un dictionnaire |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
Optimisation des manipulations de chaînes >> |