Revue de code publique 17
mardi 7 avril 2015 à 10:13En faisant ma revue quotidienne, je suis tombé sur un code Python assez tarabiscoté que twitter s’est empressé de massacrer.
Néanmoins je ne pense pas que mettre l’affiche à l’auteur soit le meilleur moyen de l’amener à passer plus de temps à coder en Python et à participer à la communauté.
En effet, il me semble qu’il est prof de bio (si j’ai bien suivi l’histo), et personnellement, si on devait me demander de faire un schéma d’une méiose, je pense que le résultat serait du même niveau.
D’un autre côté laisser circuler une code dans ce format, surtout si il a une vocation pédagogique serait contre productif. Améliorons donc ce code pas à pas en justifiant des modifications.
D’abord, voici la fonction en question :
def tripositions(Ligne): #Tri a bulle ? l = [k for k in range(len(Ligne))] q = [Ligne, l] for i in range(len(Ligne)-1): for j in range(len(Ligne)-i-1): if q[0][j]>q[0][j+1]: for k in range(2): q[k][j], q[k][j+1]=q[k][j+1], q[k][j] while q[0][0]==0: q=[[q[i][j] for j in range(1, len(q[0]))] for i in range(2)] return(q) |
Elle effectue un bubble sort (un tri des éléments en faisant remonter les plus grands en fin de liste, comme des bulles), puis retire les zéros, et retourne deux ensembles : une liste des éléments triés, et une liste de la position des ces éléments dans la liste originale. Par exemple:
>>> tripositions([4, 0, 9, 0, 5, 17, 7]) [[4, 5, 7, 9, 17], [0, 4, 6, 2, 5]] |
D’abord, essayons de comprendre le fonctionnement de l’algo :
def tripositions(Ligne): #Tri a bulle ? # Ici on récupère une liste [0, 1, 2, 3...] qui contient les positions # des éléments dans la liste passée en paramètre l = [k for k in range(len(Ligne))] # Là on groupe la liste initiale et les positions en une liste q = [Ligne, l] # On fait un tour de boucle pour chaque élément de la liste for i in range(len(Ligne)-1): # Et à chaque tout de boucle, on refait une boucle qui fait elle-même # un tour de boucle pour tous les éléments de la liste, sauf le dernier for j in range(len(Ligne)-i-1): # Si l'élément de la liste à la position actuelle est plus grand # que l'élément de la liste à la prochaine position if q[0][j]>q[0][j+1]: # On change la place de cet élément dans la liste initiale, # la place de la position de cet élément dans la liste des # positions for k in range(2): q[k][j], q[k][j+1]=q[k][j+1], q[k][j] # Maintenant que tout est trié, si il y a des zéro, il sont tous en début # de liste. Tant qu'il y a un zéro en début de liste, on retire le premier # élément de la liste initiale et de la liste des positions. while q[0][0]==0: q=[[q[i][j] for j in range(1, len(q[0]))] for i in range(2)] return(q) |
Le style d’écriture en Python étant codifié par un document appelé le PEP8, reformatons le code afin qu’il soit plus facile à lire :
# Les noms des variables ne commencent pas par une majuscule. On réservera # les majuscules aux noms de classe. # On donne aussi un nom un peu plus explicite à la fonction def elements_tries_et_positions(ligne): """ Tri a bulle d'une liste retournant les valeurs triés et leurs positions""" # On met une doctstring pour documenter la fonction plutôt qu'un commentaire # On pourra ainsi appeler help(elements_tries_et_positions) l = [k for k in range(len(ligne))] q = [ligne, l] # On aère un peu le code en rajoutant des espaces autour des signes = et < for i in range(len(ligne)-1): for j in range(len(ligne)-i-1): if q[0][j] > q[0][j+1]: for k in range(2): q[k][j], q[k][j+1] = q[k][j+1], q[k][j] while q[0][0] == 0: q = [[q[i][j] for j in range(1, len(q[0]))] for i in range(2)] # "return" est un mot clé, pas une fonction, et n'a pas besoin de # parenthèses return q |
Le code utilise massivement des ranges() et len(), ce qui me laisse à penser que notre auteur a voulu reproduire un schéma qu’il a connu lors d’une expérience dans un autre langage tel que le C ou le Fortran. C’est très courant quand on passe à une nouvelle technologie, car on essaye de trouver ses repères.
Premier passage pour retirer quelques appels qui ne sont pas idiomatiques :
def elements_tries_et_positions(ligne): """ Tri a bulle d'une liste retournant les valeurs triés et leurs positions""" # range() va déjà retourner un itérable contenant les valeurs voulues donc # pas besoin de faire une liste en intension dessus q = [ligne, range(len(ligne))] # Il n'y a pas d'avantage de performance à itérer sur range() plutôt que # sur "ligne" directement : c'est toujours une itération # de même taille et seul le nombre de tours nous intéresse # puisqu'on utilise pas l'index dans notre code for e1 in ligne: # enumerate() retourne automatiquement un itérable [(index, element), # (index, element), ...], et permet de se passer du calcule manuel # de la position des éléments # ligne[:-1] est ce qu'on appelle un slicing, qui nous permet de # créer une copie de la liste sans le dernier élément. for j, e2 in enumerate(ligne[:-1]): # q[0] est la même chose que "ligne", donc pas besoin de faire # un indexing. if ligne[j] > ligne[j+1]: for k in (0, 1): q[k][j], q[k][j+1] = q[k][j+1], q[k][j] # Même chose puisque q[0] == ligne while ligne[0] == 0: q = [[q[i][j] for j in range(1, len(q[0]))] for i in range(2)] return q |
Le fait de manipuler la liste initiale et la liste d’indexes groupés dans une 3eme liste rend le code plus difficile à lire. Nous allons éviter ça en créant la liste finale à la fin.
def elements_tries_et_positions(ligne): """ Tri a bulle d'une liste retournant les valeurs triés et leurs positions""" # On supprime la création de la liste finale et on manipule # deux variables pendant toute la fonction ce qui rend plus clair sur # quelle partie des données on travaille. positions = range(len(ligne)) for e1 in ligne: for j, e2 in enumerate(ligne[:-1]): # On a déjà e2 gratuitement, pas besoin d'utiliser un index if e2 > ligne[j+1]: # Ici, on manipules les listes par leur nom, c'est # plus facile à comprendre que des indexes ligne[j], ligne[j+1] = ligne[j+1], ligne[j] positions[j], positions[j+1] = positions[j+1], positions[j] # Si ligne[0] == 0, alors bool(ligne(0)) == False. Python n'a pas besoin # de la comparaison numérique dans une condition, juste du contexte booléen. # En l'écrivant ainsi, on se rapproche du langage parlé. while not ligne[0]: # Encore une fois, inutile de grouper les deux variables dans une # liste. Les séparer rend l'action plus lisible. ligne = [ligne[i] for i in range(1, len(ligne))] positions = [positions[i] for i in range(1, len(ligne))] # On retourne les deux variables sous forme de liste à la fin return [ligne, positions] |
Enfin, et meme si les listes en intension sont une fonctionalité du langage qu’il faut toujours garder sous le code, ce sont des boucles et il est bon de se passer de boucles non nécessaires. A l’inverse, la compatibilité avec Python 3 va nous obliger à rajouter une boucle (implicite) de plus.
def elements_tries_et_positions(ligne): """ Tri a bulle d'une liste retournant les valeurs triés et leurs positions""" # range() retourne un générateur en Python 3, il faut donc le convertir # en liste pour que ça marche dans les 2 versions positions = list(range(len(ligne))) for e1 in ligne: for j, e2 in enumerate(ligne[:-1]): if e2 > ligne[j+1]: ligne[j], ligne[j+1] = ligne[j+1], ligne[j] positions[j], positions[j+1] = positions[j+1], positions[j] while not ligne[0]: # Il s'agit juste de retirer tous les éléments nuls de gauche, il # n'est pas nécessaire de parcourir toute la liste pour ça : pop(0) # retire l'élément en début de liste ligne.pop(0) positions.pop(0) return [ligne, positions] |
Rajoutons des commentaires techniques, car en première lecture, ce n’est pas évident de savoir quel bloc fait quoi (le retrait des zéros m’a demandé un certains temps avant que je le pige) :
def elements_tries_et_positions(ligne): """ Tri a bulle d'une liste retournant les valeurs triés et leurs positions""" # Liste des positions initiales des éléments positions = list(range(len(ligne))) # Bubble sort qui traite en parallèle les valeurs et leurs positions for e1 in ligne: for j, e2 in enumerate(ligne[:-1]): if e2 > ligne[j+1]: ligne[j], ligne[j+1] = ligne[j+1], ligne[j] positions[j], positions[j+1] = positions[j+1], positions[j] # Retrait des zéro (qui après le tri sont tous en début de liste) while not ligne[0]: ligne.pop(0) positions.pop(0) return [ligne, positions] |
En tout nous avons fait plusieurs choses, qui sont presque toujours les mêmes étapes pour toute revue de code :
- Formater le code pour qu’il soit plus lisible.
- Retirer des opérations non nécessaires.
- Utiliser des noms plus explicites pour nos conteneurs.
- Utiliser les fonctions déjà proposées par Python plutôt que faire les choses manuellement.
Python est un langage de haut niveau, qui favorise la productivité et met l’accent sur la lisibilité. Aussi il est bon de tirer parti le maximum du langage pour avoir le code le plus facile à lire possible. Ne pas hésiter à avoir des noms longs, des opérations sur deux lignes, des usages d’outils tout faits, etc.
J’imagine que le but de l’exercice était de faire coder un tri à bulle, donc j’ai modifié le code précédent. Néanmoins Python propose déjà des fonctions qui font tout ça automatiquement, et voici ce pourrait donner la fonction si on devait l’écrire en tirant parti du toute la puissance du langage :
# On met tout en anglais et on change le nom de paramètre pour montrer # qu'on accepte n'importe quel itérable. # On rajoute aussi deux paramètres avec des valeurs saines par défaut mais # qui permettent d'orienter le tri différemment si on le souhaite. def get_sorted_items_and_positions(iterable, key=lambda x: x[1], reverse=False): """ Sort an iterable and return a tuple (sorted_items, old_positions)""" # On récupère la liste de tous les éléments non nuls et leur position indexed_non_null_elements = [(i, e) for i, e in enumerate(iterable) if e] # On les tri avec un tim sort plutôt qu'un bubble sort indexed_non_null_elements.sort(key=key, reverse=reverse) # On sépare les indexes des élements avec une astuce de sioux indexes, elements = zip(*indexed_non_null_elements) # On retourne généralement un tuple quand on a peu de valeurs à retourner return elements, indexes |
La fonction va alors retourner un tuple de tuple au lieu d’une liste de liste, mais sinon fera les mêmes opérations :
>>> get_sorted_items_and_positions([4, 0, 9, 0, 5, 17, 7]) ((4, 5, 7, 9, 17), (0, 4, 6, 2, 5)) |
Néanmoins elle aura le double avantage de fonctionner avec n’importe quel itérable (get_sorted_items_and_positions acceptera alors en paramètre une liste, mais aussi un tuple, un set ou même un fichier) mais aussi d’être beaucoup plus rapide puisque sort() est codé en C sous le capot.
Comme ai-je pondu cette fonction ?
D’abord, j’ai observé l’algorithme, et j’ai noté que les zéros étaient retirés. Il est souvent plus facile de filtrer ses données avant le traitement, donc je retire les 0 tout au début. Python est un fantastique langage pour tout ce qui est filtre, et on peut non seulement le faire en une ligne, mais indexer les éléments restant dans la foulée.
Ensuite, j’utilise la fonction de tri intégrée au langage, qui est un algo non seulement plus efficace que le bubble sort mais en prime est codé en C par les auteurs de Python, donc qui sera beaucoup plus performant. La manière dont fonctionne le tri en Python permet de trier mes paires (position, valeur) comme un seul élément, mais en fonction de la valeur uniquement. Un autre avantage, c’est que cette fonction permet de changer le type de tri (par exemple trier du plus grand au plus petit), et donc je peux exposer ces paramètres supplémentaires dans ma fonction pour laisser plus de control à l’utilisateur. Grâce aux valeurs par défaut, ce contrôle supplémentaire ne rend pas l’usage plus complexe, puisque l’utilisateur peu juste ignorer ces paramètres.
Enfin, j’utilise une combinaison de slicing, d’unpacking (via l’opéateur splat l’opérateur splat) et une particularité de la fonction zip() qui permet de transposer un itérable de paires en deux itérables d’éléments seuls :
>>> paires = [(1, "a"), (2, "b"), (3, "c")] >>> zip(*paires) [(1, 2, 3), ('a', 'b', 'c')] >>> nombres, lettres = zip(*paires) >>> nombres (1, 2, 3) >>> lettres ('a', 'b', 'c') |
Notez bien que personne ne demande à quelqu’un qui commence à toucher du Python de trouver ce code. C’est juste comme ça qu’on finit par le faire, à l’usage.