Ordonner en Python

This entry was posted in Programmation and tagged lambda operator python sort on by

Python possède une manière de mettre les choses dans l’ordre qui est à la fois simple et puissante.

Tout est ordonnable

Pour comprendre comment marche le tri en Python, il faut comprendre que presque tout en Python est ordonnable car comparable :

>>> 1 > 0 # les nombres sont comparables
True
>>> 1 < 0
False
>>> "a" < "b" # les lettres, par ordre alphabetique
True
>>> True > False # les booléan (!)
True
>>> (1, 2) > (2, 1) # les iterables comparés, élément par élément dans l'ordre
False
>>> (1, 2) > [2, 1] # mais ils doivent être du même type
True
>>> {1:1} < {1:1, 0:0} # les dictionnaires, par nombre d'éléments
True
>>> "a" > 2 # si on mélange des types ça peut vide devenir bizarre
True
>>> 1j > 1 # j'ai dis PRESQUE tout est ordonnable
Traceback (most recent call last):
  File "<ipython-input-11-ed3c013d3df8>", line 1, in <module>
    1j > 1
TypeError: no ordering relation is defined for complex numbers

C’est ce qu’on appelle l’ordre naturel des éléments. Quand il n’y a pas d’ordre naturel évident (et que ce n’est pas une opération explicitement interdite comme avec les complexes), Python va comparer l’id (imaginez l’adresse en mémoire):

>>> class PersonnageDeLost(object):
...     pass
... 
>>> mort1 = PersonnageDeLost()
>>> mort2 = PersonnageDeLost()
>>> mort1 < mort2
True
>>> id(mort1) # son id est plus petit, donc il est inférieur
39611408
>>> id(mort2)
41720976

Mais on peut définir un ordre naturel pour un élément personnalisé en implémentant les méthodes suivantes:

  • object.__lt__(self, other)
  • object.__le__(self, other)
  • object.__eq__(self, other)
  • object.__ne__(self, other)
  • object.__gt__(self, other)
  • object.__ge__(self, other)

N’implémentez plus __cmp__, elle est dépréciée.

Par exemple:

class PersonnageDeCityHunter(object):
 
    def __init__(self, nom, erectopouvoir):
        self.nom = nom
        self.erectopouvoir = erectopouvoir
 
 
    def __lt__(self, other):
        # on doit retourner un booléan qui confirme ou infirme 
        # l'opération "lt" ("lower than", c'est à dire "plus petit que")
        return self.erectopouvoir < other.erectopouvoir
 
    def __gt__(self, other):
        # on doit retourner un booléan qui confirme ou infirme 
        # l'opération "gt" ("greater than", c'est à dire "plus grand que")
        return self.erectopouvoir > other.erectopouvoir
 
    # on peut faire la même chose pour les autres méthodes qui 
    # concernent les opérateurs <=, >=, == et !=
 
>>> PersonnageDeCityHunter('Ryo Saeba', 99999) > PersonnageDeCityHunter('Mamouth', 1)
True
>>> PersonnageDeCityHunter('Ryo Saeba', 99999) < PersonnageDeCityHunter('Mamouth', 1)
False

Ordonner une liste

Une liste est ce qu’on ordonne le plus souvent. Elle possède pour cela une méthode sort() qui est la méthode de tri la plus rapide qui existe avec la lib standard.

sort() trie une liste sur place (elle modifie donc la liste), et retourne None.

>>> l = [1, 7, 3, 8]
>>> res = l.sort()
>>> print res # n'assignez jamais le résultat de sort(), ça ne sert à rien !
None
>>> l
[1, 3, 7, 8]

Les éléments sont triés dans leur ordre naturel automatiquement, du plus petit au plus grand:

>>> l = ['b', 'a', 'c']
>>> l.sort()
>>> l
['a', 'b', 'c']
>>> l = [(2, 1), (1, 2), (7, 8), (2, 2), (2, 0), (2, 3)]
>>> l.sort()
>>> l # ordonne sur le premier élément, puis le second si il y a égalité
[(1, 2), (2, 0), (2, 1), (2, 2), (2, 3), (7, 8)]
>>> persos = [PersonnageDeCityHunter('Ryo Saeba', 99999), PersonnageDeCityHunter('Mamouth', 1), PersonnageDeCityHunter('Kaori', 0)]
>>> persos.sort()
>>> for perso in persos:
...     print perso.nom
...     
Kaori
Mamouth
Ryo Saeba

On peut demander à inverser l’odre de tri en passant l’argument reverse:

>>> l = [1, 7, 3, 8]
>>> l.sort(reverse=True)
>>> l
[8, 7, 3, 1]

Il n’y a pas que les listes dans la vie

Tout itérable est ordonnable, et la fonction sorted() permet justement d’ordonner n’importe quel itérable de taille finie.

>>> sorted([1, 7, 3, 8]) # une liste
[1, 3, 7, 8]
>>> sorted(set([1, 7, 3, 8])) # un set
[1, 3, 7, 8]
>>> sorted((1, 7, 3, 8)) # un tuple
[1, 3, 7, 8]
>>> sorted('Un clavier azerty en vaut deux') # une chaîne
[' ', ' ', ' ', ' ', ' ', 'U', 'a', 'a', 'a', 'c', 'd', 'e', 'e', 'e', 'e', 'i', 'l', 'n', 'n', 'r', 'r', 't', 't, 'u', 'u', 'v', 'v', 'x', 'y', 'z']
>>> sorted(open('/etc/fstab'))[:3] # un fichier
['#\n', '#\n', '# / was on /dev/sda5 during installation\n']
>>> import random # plus ou moins n'importe quoi
>>> sorted([random.randint(0, 100) for x in range(random.randint(0, 20)) if x * 2 not in (42, 69)])
[2, 4, 21, 35, 37, 41, 48, 48, 54, 58, 58, 59, 62, 76, 82, 94]

sort() et sorted() acceptent toutes les deux les mêmes arguments. Ce que vous apprenez pour l’un vaut pour l’autre. La seul différence est que sort() retourne None et modifie sur place, tandis que sorted() retourne une nouvelle liste. sorted() est un peu moins performant.

>>> sorted((1, 7, 3, 8), reverse=True)
[8, 7, 3, 1]

Tri personnalisé avec key

Parfois on a besoin de trier sur quelque chose de plus complexe qu’une lettre ou un chiffre. Par exemple, vous avez des scores dans un dictionnaires. Un dictionnaire n’est pas ordonné. Si vous imprimez un classement, il faut en faire une liste de tuples :

>>> scores = {'Robert': 2, 'Roger': 1, 'Gertrude': 4, 'Cunegonde': 3}
>>> scores.items()
[('Gertrude', 4), ('Cunegonde', 3), ('Robert', 2), ('Roger', 1)]

Et il faut maintenant ordonner ça sur le deuxième élément de chaque tuple : le score. Seulement si on appelle sorted(), il va trier sur l’ordre naturel, donc il va commencer par le premier élément, ça ne marchera pas :

>>> sorted(scores.items())
[('Cunegonde', 3), ('Gertrude', 4), ('Robert', 2), ('Roger', 1)]

C’est là qu’intervient le paramètre key. key est très particulier, c’est un paramètre qui attend qu’on lui passe un callback, donc key attend qu’on lui passe une fonction.

Pas le résultat d’une fonction. La fonction elle même.

Cette fonction doit attendre en paramètre un élément, et en extraire la partie sur laquelle on veut trier.

Par exemple dans le cas des scores, on doit passer à key une fonction qui attend un tuple en paramètre, et retourne le score :

>>> def get_score(nom_et_score):
...     return nom_et_score[1] # retourne le 2nd element du tuple
... 
>>> sorted(scores.items(), key=get_score) # on passe la fonction a key
[('Roger', 1), ('Robert', 2), ('Cunegonde', 3), ('Gertrude', 4)]

Et voilà, c’est trié dans le bon ordre car sorted() va utiliser get_score() pour récupérer la valeur de chaque élément un par un, sur laquelle on va trier la liste (selon l’ordre naturel de cette valeur).

On peut utiliser key pour faire des choses beaucoup plus complexes, comme comparer sur des valeurs qui n’existent pas, mais que l’on calcule :

>>> def carre(val): # on va ordonner par valeur de carré
...     return val * val 
... 
>>> sorted([-1, -2, 0, 3], key=carre)
[0, -1, -2, 3]

Ici, un carré est toujours positif, du coup on retrouve -1 et -2 devant 0, car leurs carrés 1 et 4 sont plus grands que le carré 0 de 0.

Ne vous embrouillez pas : la valeur retournée par carre() n’est pas MISE dans la liste, elle est juste utilisée pour choisir l’ordre d’un élément dans la liste.

On peut même faire des comparaisons très avancées, comme par exemple comparer sur plusieurs attributs d’un objet. Imaginez, je veux ordonner des objets voitures selon leur coût d’entretien d’abord, et ensuite par coût d’achat.

class Voiture(object):
 
    def __init__(self, cout_entretien, cout_achat):
        self.cout_entretien = cout_entretien
        self.cout_achat = cout_achat
 
    def __repr__(self):
        return "<Voiture E-{} / A-{}>".format(self.cout_entretien, self.cout_achat)
 
>>> voitures = [Voiture(10000, 10000), Voiture(50000, 10000), Voiture(10000, 60000)]
>>> voitures
[<Voiture E-10000 / A-10000>, <Voiture E-50000 / A-10000>, <Voiture E-10000 / A-60000>]
>>> def get_entretien_achat(voiture): 
...         return (voiture.cout_entretien, voiture.cout_achat)
... 
>>> sorted(voitures, key=get_entretien_achat)
[<Voiture E-10000 / A-10000>, <Voiture E-10000 / A-60000>, <Voiture E-50000 / A-10000>]

get_entretien_achat() retourne un tuple de deux valeurs. Python va donc ordonner sur ce tuple, dans l’odre naturel du tuple en prenant la première valeur comme point de comparaison (coût d’entretien), puis la seconde (coût d’achat) si les valeurs sont égales.

On peut donc comparer des objets arbitraires sur des critères arbitraires.

La plupart du temps, vous voudrez juste comparer sur un élément ou un attribut, donc dans ce cas le module operator (ou une lambda) est votre ami :

>>> from operator import attrgetter, itemgetter
>>> sorted(voitures, key=attrgetter('cout_achat')) # ordonner par cout d'achat
[<Voiture E-10000 / A-10000>, <Voiture E-50000 / A-10000>, <Voiture E-10000 / A-60000>]
>>> sorted(scores.items(), key=itemgetter(1)) # ordonner par score
[('Roger', 1), ('Robert', 2), ('Cunegonde', 3), ('Gertrude', 4)]
>>> sorted(scores.items(), key=itemgetter(1), reverse=True) 
[('Gertrude', 4), ('Cunegonde', 3), ('Robert', 2), ('Roger', 1)]

Pour finir, je vous invite à lire l’article sur le module heapq qui lui permet de faire des tris sur des flux de données sans taille définie.

21 thoughts on “Ordonner en Python”

  • Kontre

    ‘Un clavier azerty en vaux deux’ : en fait, il en vaut deux.

    Il serait bon de préciser qu’il n’y a pas besoin d’implémenter toutes les fonctions de comparaison. par exemple, si on donne object.__lt__(self, other), python sait comment faire object.__ge__(self, other). En gros il suffit de l’égalité et d’une comparaison pour avoir automatiquement toutes les autres.

    On peut faire des trucs rigolos : dans checkio.org, il y a un exercice qui demande de créer un objet qui est à la fois plus grand, plus petit, égal et inégal à lui-même.

  • Sam Post author

    Objection Kontre, car si tu implémente que juste lt, les comparaisons égales renverons False et ça ne veut pas dire ge.

  • Kontre

    Pire que ça, en vérifiant j’ai retrouvé que pour avoir les autres il faut utiliser functools.total_ordering. Avec ça, __eq__ et une inégalité suffit.

    Je pensais que comme __ge__ est l’inverse de __lt__ ça suffisait, j’aurais dû tester avant.

    Ça m’apprendra à faire le malin.

  • Sam Post author

    C’est génial ce truc total_ordering. Je connaissais pas, ça viande du diplodocus frigide à la tringle à rideau.

  • sil

    Perso, je ne comprends pas l’utilité des méthodes __le__ et __ge__. Pourquoi ne pas retourner le résultat des methodes (__lt__ or __eq__) et (__gt__ or __eq__).

  • Sam Post author

    Parce que ton implémentation de l’une peut être plus rapide que l’appel des deux autres.

    Parce que tu ne veux pas forcément definir __eq__ (parfois êtres plus grand ou égal a du sens, mais pas juste égal).

  • ayoub zahar

    bonsoir , s’il vous plait comment écrire une fonction qui renvoie le maximum d’une liste sans qu’elle soit ordonnée .
    merci

  • Sam Post author

    Pas de bol ! La bonne réponse était : “oui mais je n’y arrive pas. J’ai fais ça et ça, et ça me donne ça. Un indice” ?

    C’est pas grave, vous pouvez rejouez la semaine prochaine en changeant de pseudo !

  • Cucus

    Super post merci ! J’ai une question en revanche pour l’usage de key : si au lieu de la fonction carre() que tu utilises dans ton exemple, tu voulais une fonction qui multiplie par un nombre à renseigner en argument (soit deux arguments au lieu d’un dans ton exemple). Comment faut-il faire ? Voici l’erreur que j’obtiens en faisant le test :

    def mutplication(val, num):

    ...return val * num

    sorted([-2,-1,0,3],key = multiplication(-1))

    Original exception was:

    Traceback (most recent call last):

    File "", line 1, in

    TypeError: extract_num_in_str() takes exactly 2 arguments (1 given)

    Est-ce qu’il possible d’utiliser key dans ce cas là ? Ou bien est ce que je dois forcément créer ma liste multplier par -1 avant puis trier le résultat, puis remultiplier par -1 ?

    Merci !

  • mohercliffs

    Bonjour,

    j’ai une liste de listes (ie une matrice) que je veux trier. A chaque ligne, j’ai une liste avec 4 valeurs type float, puis une valeur type tuple, ou le tuple est un triplet de flottants.

    L’association de trois valeurs flottantes represente une combinaison, j’ai un nombre de combinaisons fini mais les combinaisons se repetent.

    Mon souci est d’obtenir une matrice triee de la sorte : [ [v1,v2,v3,v4,combi1]

    [v1,v2,v3,v4,combi1]

    [v1,v2,v3,v4,combi1]

    [v1,v2,v3,v4,combi2]

    [v1,v2,v3,v4,combi2]

    etc,etc.

    [v1,v2,v3,v4,combi_n] ]

    avec un tri selon la valeur du tuple.

    Merci d’avance pour vos reponses, ciao

Comments are closed.

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.