Et justement, en relisant un célèbre post de Guido sur la réponse à la blague “comment trier un million d’entiers avec 2M de Ram”, j’ai réalisé 2 choses:

• Le contenu de l’article est génial.
• Le contenu de l’article est incompréhensible.

Or c’est un peu ma raison d’être, si vous voulez, de prendre les trucs cools mais imbitables et les rendre utilisables.

Aujourd’hui, donc, on va trier un CSV de 5Go en Python. Ça parle plus qu’un fichier de nombres, et puis ça évite d’expliquer le module array qui est juste une optimisation.

J’ai pris mes petites mimines, et j’ai pondu un CSV qui contient 63Mo de:

A,01/02/2016,2
A,13/07/2011,1
B,24/01/1996,3
C,30/12/1999,1
D,13/07/2011,3
D,01/02/2016,5
E,24/01/1996,4
F,30/12/1999,1
G,13/07/2011,4
H,01/02/2016,4
I,01/02/2016,5
I,13/07/2011,2
A,01/02/2016,2
A,13/07/2011,1

En copier/coller.

Puis j’ai lancé un script pour dupliquer le bébé et jusqu’à atteindre 5,9 Go de taille:

with open('data.csv') as infile:
    with open('data2.csv', 'w') as outfile:
        for x in range(100):
            outfile.write(infile.read())
            infile.seek(0)

Si jamais vous doutiez que je vous aime…

395366400 lignes. Jusqu’ici tout va bien.

Maintenant, supposons qu’on veuille trier sur la date. Si vos souvenirs en Python sont exacts (ou si vous avez lu notre super article sur Ordonner en Python), vous savez que la solution naïve est de loader le fichier cash pistache, puis d’appeler dessus sorted() avec le paramètre key.

D’abord, il faut choisir le callback à passer à key, c’est à dire la fonction qui va être exécutée pour chaque ligne pour extraire la date de la ligne et permettre ainsi à sorted() de comparer avec les autres dates.

>>> str_date = "A,01/02/2016,2".split(',')[1] # récupère la date uniquement
>>> str_date
'01/02/2016'
>>> ''.join(str_date.split('/')[::-1]) # on inverse la date avoir une valeur ordonnable
'20160201'

On en fait une fonction:

 
def extract_date(ligne):
    str_date = ligne.split(',')[1]
    return ''.join(str_date.split('/')[::-1])

Ensuite on a juste à ouvrir le fichier, trier les lignes, et sauvegarder tout ça dans l’autre fichier:

with open('data2.csv') as infile:
    with open('sorted_data.csv', 'w') as outfile:
        # on fait le tri
        sorted_lines = sorted(infile, key=extract_date)
        # on ecrit les lignes triées dans le nouveau fichier
        outfile.writelines(sorted_lines)

Easy money, double poney.

Enfin avec un fichier de quelques Mo. Parce que si vous faites ça dans un fichier de 5,9 Go, votre RAM va vomir comme une pom pom girl anorexique.

sorted() sur un disque complet, illustré

Comment résoudre ce problème ?

Et bien en faisant tout pareil, mais avec des petits morceaux !

import heapq

from tempfile import TemporaryFile
from itertools import islice

# On garde notre fonction key
def extract_date(ligne):
    str_date = ligne.split(',')[1]
    return ''.join(str_date.split('/')[::-1])

# Liste de tous les fichiers temporaires avec les lignes triées
sorted_temp_files = []

with open('data2.csv') as infile:
    progress = 0
    while True:
        # On lit seulement 3000000 lignes sur 395366400 à chaque tour de boucle
        lines = list(islice(infile, 3000000))

        if not lines:  # plus de ligne ? On sort
            break

        # On affiche où on en est
        print("{:.2f}%".format(progress))
        progress += (3000000 / 395366400 * 100)

        # On tri les lignes, comme avec sorted() mais sur place. 
        # Ça évite de dupliquer les données en mémoire.
        lines.sort(key=extract_date)

        # On crée un fichier temporaire qui va contenir les 3000000 lignes
        # triées
        f = TemporaryFile(mode="r+")
        f.writelines(lines)

        # On rembobine le fichier pour pouvoir relire le contenu plus tard
        f.seek(0)

        # On balance le fichier dans la liste des fichiers triés
        # L'objet fichier hein. Pas le chemin du fichier. C'est pour ça qu'on
        # a fait .seek(0) avant. On va en avoir besoin plus bas.
        sorted_temp_files.append(f)

    # Toute la magie se fait là.
    # On utilise heapq.merge(), qui prend en paramètre plein de trucs qu'on 
    # vient de trier, et permet de se balader dedans comme si c'était un seul
    # gros truc trié, mais sans tout charger en mémoire.
    # En gros il regarde les premières valeurs de tous les itérables, les compares,
    # puis fait retourne un générateur qui yield tout dans l'ordre 
    with open('sorted_data.csv', 'w') as outfile:
        for ligne in heapq.merge(*sorted_temp_files, key=extract_date):
            outfile.write(ligne)

Au lieu de charger les 5 Go en mémoire, on plafonne à 400 Mo. Une raison de plus d’apprendre à utiliser les générateurs.

Sametmax, c’est de la bombe

Alors évidemment, c’est long. Y a genre 40 minutes de traitement. Moins si on utilise pypy et qu’on accepte de up la conso RAM. On code pas en Rust :)

Si vous avez besoin de perfs et que Python reste votre outil de prédilections, 3 solutions restent à votre disposition:

– Prétraiter le fichier en lui rajoutant une première colonne qui contient un timestamp. Ca c’est super rapide à trier.
– Utiliser un truc de numpy ou pandas comme np.memmap().sort(kind=’merge’). C’est du C, donc ça speed.
– Acheter de la ram et tout trier en mémoire avec la solution 1.

EDIT:

Un lecteur m’a alpagué sur twitter pour me dire qu’on peut faire ça plus vite et plus facilement avec sort. Oui, évidement.

L’exercice est académique, il est simplifié pour vous permettre de comprendre heapq.merge(). En réalité, on aura vraiment besoin de ça que pour un cas complexe. Exemple, vous lisez un flux de log une socket et vous checkez les adresses IP d’abord pour filtrer celles de la liste noire, puis pour les faire matcher une zone géographique et vous triez tout ça et vous le passez à la suite du pipeline. Et le tout doit marcher sous Linux et Windows Server avec juste la lib standard parce que diab est de mauvais poil.

Évidement que si vous voulez juste trier un CSV vous n’allez pas coder un script python de 30 lignes.

Ceci est un post invité de Réchèr posté sous licence creative common 3.0 unported.

Kikoo amis matheux ou pas. Aujourd’hui, on va se faire un petit algo de derrière les fagots. Vous n’en aurez peut-être jamais besoin dans le monde réel, mais, qui a dit qu’on allait se contenter uniquement de ce dont on a besoin ? De plus, je présenterais, à la fin, une astuce générique d’algorithmiciens.

Pré-requis

• Connaître très vaguement la notion des O(n²), O(truc), … qui définissent le temps d’exécution d’un algorithme en fonction de la quantité de données à traiter. (Si ça vous parle pas c’est pas grave).
• Savoir que le pluriel d’intervalle n’est pas “intervaux”.

Petite précision : pour définir des intervalles d’entiers, j’emploierais la convention pythonienne : le dernier élément n’est pas inclus. C’est à dire que [2, 7] correspond à 5 éléments : 2, 3, 4, 5, 6.

Énoncé

Soit une liste de couple de nombres, représentant des intervalles. Ils sont tout en vrac, y’en a qui se chevauchent, d’autres qui s’inclusent, etc. Bref, l’ensemble fait penser à une partouse animale multi-espèces.

exemple : [ [2, 7], [3, 7], [1, 5], [9, 10], [8, 9] ]

Vous voulez une méthode pour rassembler tout ça, et obtenir une liste d’intervalles, triée, sans chevauchement, correspondant à la fusion de tous les intervalles de départ. En maths, on appelle cette opération une union. En partouse animale multi-espèces, on appelle aussi ça une union, mais ce n’est pas le sujet.

résultat souhaité : [ [1, 7], [8, 10] ]

Solutions auxquelles on pense en premier

Le bourrin pas-à-pas

On récupère le début d’intervalle le plus à gauche, et la fin la plus à droite. On boucle entre ces deux valeurs. À chaque itération, on effectue le traitement suivant :

• Vérifier si la valeur courante est dans au moins un intervalle.
• Si oui, et que juste avant on était dans aucun intervalle, alors on marque cette valeur comme un début d’intervalle.
• Si non, et que juste avant on était dans au moins un intervalle, alors on marque cette valeur comme une fin d’intervalle.

Désavantages

Si, au départ, on a deux intervalles très éloignés, par exemple [0, 2] et [1000000, 1000002] on va faire une boucle de 1000002 itérations. Pour traiter 2 intervalles, c’est un peu lourd.

Ça ne marche qu’avec des entiers. Si on a des intervalles de réels, on itère comment ? En avançant de 0.0000000001 en 0.0000000001 ? Même problème avec des intervalles de date-heure.

Le bourrin cumulatif

On crée une liste géante de booléens, tous à False, qui s’étend du premier début d’intervalle à la fin du dernier. Chaque booléen indiquera si le nombre correspondant se trouve dans au moins un intervalle. On met les bons booléens à True en parcourant les intervalles de la liste initiale. Puis, on construit la liste finale d’intervalles, en se basant sur les booléens.

Désavantages

Si on a en entrée un million de fois l’intervalle [10, 210], on va mettre un million de fois à True la même suite de 200 booléens. 200 millions d’opérations pour ressortir un unique intervalle [10, 210].

Même problème que précédemment. Ça ne marche qu’avec des nombres entiers.

L’enfileur de perles

On a d’un côté la liste finale des intervalles (initialisée à vide), et de l’autre, la liste initiale, en bordel. On passe les intervalles d’une liste à l’autre, un par un, en testant les cas suivants :

• Le début et la fin de l’intervalle en cours n’est dans aucun intervalle final -> ça fait un nouvel intervalle final.
• Le début est dans un intervalle final, mais pas la fin -> ça rallonge l’interval final existant.
• La fin est dans un intervalle final, mais pas le début -> ça rallonge l’intervalle final existant, mais par l’autre côté.
• La fin et le début sont dans le même intervalle final -> l’intervalle en cours ne sert à rien.
• La fin et le début sont dans deux intervalles finaux différents. -> il faut fusionner les deux intervalles finaux.

Et en plus de tout ça, il faut également tester s’il n’y a pas des intervalles finaux entièrement inclus dans l’intervalle en cours. Auquel cas, ils ne servent plus à rien, et doivent être enlevé de la liste.

Désavantages

Une bonne grosse prise de tête à coder tous les cas possibles, sans rien oublier, sans bug.

Le fait de chercher si un nombre se trouve dans une liste d’intervalles, fut-elle triée, est une opération qui prend un certain temps. Ça peut s’optimiser avec de la dichotomie ou des trucs du genre, mais quand même.

Par contre, cette algo marche avec des nombres réels et des date-heure. Youpi.

Et si on arrêtait les conneries ?

Dans ces premières solutions, on considère les intervalles comme des objets immuables. Il faut en traiter un entièrement avant de passer au suivant. Mais on peut aussi les voir comme deux événements distincts (un début et une fin), que l’on peut dissocier totalement, et traiter dans leur ordre d’arrivée. On ne sera plus capable de retrouver quel début correspond à quelle fin, mais ça on s’en fout, y’a rien qui ressemble plus à un intervalle qu’un autre intervalle.

Imaginez un petit bonhomme (ou une petite bonne femme, respectons la parité). Au départ, il est au niveau du sol. Il avance vers la droite. Quand il rencontre un début d’intervalle, il monte sur un mur d’un étage. Quand il rencontre une fin, il descend d’un étage. Il peut être sur plusieurs étages superposés. Au fur et à mesure qu’il se déplace, on note les endroits où il se retrouve sur le sol. Ces endroits correspondent à des zones sans aucun intervalle.

Le code

def tri_bonhomme_sur_un_mur(list_intervalle_en_bordel):
    """ Effectue une union de tous les intervalles indiqués en paramètre.
    
    Données d'entrée : une liste de liste de deux éléments, représentant
    des intervalles.
     - Le type des éléments n'est pas imposé. Il faut juste qu'on puisse 
       les ordonner et les trier. 
     - Dans chaque liste de deux éléments, le premier doit être plus 
       petit que le second. 
    La fonction ne vérifie pas ces contraintes. Si elles ne sont pas 
    respectées, le comportement est indéterminé. Ça peut planter, 
    ça peut renvoyer un résultat faux sans avertissement, etc.
    
    Sortie : une liste de liste de deux éléments, unionnisée et triée
    comme il faut.
    """
    # On extrait tous les débuts d'intervalles, et toutes les fins.
    list_debut = [ interv[0] for interv in list_intervalle_en_bordel ]
    list_fin = [ interv[1] for interv in list_intervalle_en_bordel ]
    # On les trie, pour pouvoir les traiter de gauche à droite.
    list_debut.sort()
    list_fin.sort()
    # Cette liste contiendra les intervalles unionnisés et triés.
    list_intervalle_final = []
    # indique le nombre d'invervalle superposés dans lesquels on se trouve
    # actuellement. (C'est à dire : le nombre d'étages sur lequel
    # marche le bonhomme).
    nb_superposition = 0
    # Lorsqu'on est dans un ou plusieurs intervalles superposés, on doit
    # se souvenir à quelle position on est entré dans le premier.
    # Cela permettra de créer l'intervalle final, lorsqu'on sera 
    # complètement sorti de la superposition en cours.
    debut_intervalle_courant = 0
    
    # C'est parti ! Le petit bonhomme avance. On lui fait traiter les
    # événements d'entrée et de sortie d'intervalle au fur et à mesure 
    # qu'ils arrivent.
    while list_debut:
        # Le premier élément de list_debut, c'est le premier début 
        # d'intervalle qu'on rencontrera. Le premier élément de list_fin,
        # c'est la première fin d'intervalle qu'on rencontrera. On 
        # détermine, parmi ces deux événements, lequel on rencontrera en 
        # tout premier.
        #
        # La fonction cmp renvoie -1, 0, ou 1, selon la comparaison 
        # effectuée entre les deux valeurs passées en paramètre.
        # Faire un petit help(cmp) pour connaître les détails.
        ordre_debut_fin = cmp(list_debut[0], list_fin[0])
        if ordre_debut_fin == -1:
            # L'événement rencontré est un début d'intervalle.
            # On enlève l'événement de la liste, puisqu'on va le traiter,
            # là, tout de suite.
            pos_debut = list_debut.pop(0)
            if nb_superposition == 0:
                # On était dans aucun intervalle, et on vient d'en 
                # rencontrer un. Dans la liste finale d'intervalles, 
                # ça va donc compter comme un début. On retient 
                # cette info.
                debut_intervalle_courant = pos_debut
            # Dans tous les cas, on ajoute une superposition d'intervalle
            # (le bonhomme monte d'un étage).
            nb_superposition += 1
        elif ordre_debut_fin == +1:
            # L'événement rencontré est une fin d'intervalle.
            # On l'enlève de la liste.
            pos_fin = list_fin.pop(0)
            # On enlève une superposition d'intervalle.
            nb_superposition -= 1
            if nb_superposition == 0:
                # Après avoir enlevé la superposition, on se retrouve
                # avec 0 intervalle superposé. 
                # (Le bonhomme est redescendu jusqu'au niveau du sol).
                # Il faut donc enregistrer ça comme une fin d'intervalle 
                # final. Tant qu'on y est, on crée tout de suite ce nouvel
                # intervalle final et on le met dans la liste.
                nouvel_intervalle = (debut_intervalle_courant, pos_fin)
                list_intervalle_final.append(nouvel_intervalle)
        else:
            # On rencontre à la fois un début et une fin d'intervalle.
            # Rien de spécial à faire. Faut juste virer les 2 événements 
            # traités de leur liste respectives.
            list_debut.pop(0)
            list_fin.pop(0)
    
        # Durant toute cette boucle, la variable nb_superposition augmente
        # et diminue. Mais elle n'est jamais censée devenir négative.
        # Si ça arrive, c'est que les données d'entrées sont mal foutues.
        # On entre dans un cas d'indétermination. 
    
    # Arrivé à la fin de la boucle, il peut rester, ou pas des éléments
    # dans list_fin. Ce qui est sûr, c'est que list_debut se vide
    # avant list_fin. Si ce n'est pas le cas, c'est encore un cas
    # d'indétermination.
    
    if list_fin:
        # On a passé tous les débuts d'intervalle, mais il reste des
        # fins. Ça veut dire qu'on est encore dans un ou plusieurs
        # intervalles. On devrait normalement avoir :
        # len(list_fin) == nb_superposition. Si c'est pas le cas, c'est
        # un cas d'indétermination.
        #
        # On pourrait traiter les événements de fin d'intervalle un par un,
        # et diminuer progressivement nb_superposition. Mais on s'en fout,
        # c'est pas nécessaire. On prend juste la fin d'intervalle qui 
        # supprimera la dernière superposition (c'est à dire la dernière
        # fin d'intervalle), et on construit un dernier intervalle final
        # avec ça.
        pos_fin = list_fin[-1]
        nouvel_intervalle = (debut_intervalle_courant, pos_fin)
        list_intervalle_final.append(nouvel_intervalle)
    
    return list_intervalle_final

Les avantages (parce que y’a aucun désavantages)

Ça marche avec des réels, des dates, et de manière générale, tout ce qu’on peut trier.

>>>tri_bonhomme_sur_un_mur([ [2, 7], [3, 7], [1, 5], [9, 10], [8, 9] ])
[(1, 7), (8, 10)]

# Testez pas ça chez vous ! Ça prend trois plombes ! Mettez juste 1000.
>>>tri_bonhomme_sur_un_mur( [ [10, 210], ] * 1000000 )
[(10, 210)]

# Voyons voir ce que ça donne avec des réels 
# (dont certains sont négatifs, tant qu'à faire).
>>>tri_bonhomme_sur_un_mur([ 
    [-7.2, -6.9], [-8.4, -5.3], [-10.5, -5.25], 
    [-1.7, 0.01], [0.0, 4.0], 
    [12.125, 13.9, ], [13.9, 15.0]])
[(-10.5, -5.25), (-1.7, 4.0), (12.125, 15.0)]    
    
# et avec des dates
>>>from datetime import datetime
>>>tri_bonhomme_sur_un_mur([
    [datetime(2012, 12, 21, 16, 54), 
     datetime(2013, 02, 16, 12, 59)], 
    [datetime(2013, 02, 14, 2, 0), 
     datetime(2069, 01, 01, 13, 37), ] ] )
[(datetime.datetime(2012, 12, 21, 16, 54),
  datetime.datetime(2069, 1, 1, 13, 37))]                           

En ajoutant à peine 2-3 lignes de code à la fonction, on peut récupérer le nombre maximal d’intervalles superposés.

En re-ajoutant quelques autres lignes, on peut récupérer les zones dans lesquelles ce maximum est atteint. Ce qui pourrait servir pour effectuer l’opération mathématique d’intersection. (Je vous laisse chercher ça par vous mêmes).

L’algorithme est principalement constitué d’une bi-boucle, c’est à dire une boucle unique, qui avance dans deux listes différentes (je viens d’inventer ce terme, ne m’embêtez pas). C’est encore plus simple que deux boucles imbriquées. Le nombre d’itérations à effectuer est égal au nombre d’intervalle multiplié par deux, c’est tout. Dans tous les cas limites présentés ci-dessus, ça fait une solution acceptable, demandant un temps d’exécution peu pharaonique.

Mais ou est passé la complexité ?

Les premières solutions avaient l’air de demander énormément de temps d’exécution, surtout avec beaucoup d’intervalles en entrée. Ça ne semble pas être le cas pour la solution du “bonhomme sur un mur”. Pourtant, la complexité d’une tâche, ça ne disparaît pas comme par magie. Y’aurait-il une entourloupe quelque part ?

Il y en a une. Ce sont les deux opérations de tri effectuées au début de la fonction. Un tri, ce n’est pas anodin, et son temps d’exécution peut augmenter très beaucoup et très vite. La complexité n’a pas disparue, on n’a fait que la déplacer vers des tris. Alors finalement, ma solution n’est pas si bien que ça ?

Eh bien si. Parce que le tri, même s’il reste coûteux en temps et en ressource, est un problème archi-connu, archi-réglé, et archi-optimisé. Le python, comme beaucoup d’autres langages, profite pleinement du travail réalisé par des centaines de matheux algorithmologues, qui se sont masturbés l’esprit sur des centaines de méthodes de tri différentes.

Photo prise dans le bureau d'un chercheur en algorithmologie.

C’est ça l’astuce générique dont je vous parlais au début. Face à un nouveau problème, le matheux sort son zguègue tente de trouver des équivalents à un ou plusieurs problèmes connus, que lui et ses amis matheux ont déjà réglés. C’est souvent bien plus simple que de tenter de régler le problème directement, en partant de rien.

“Un nain éjacule bien plus loin lorsqu’il est perché sur les épaules d’un géant.” Et pour respecter la parité, j’ajouterais qu’une naine femme-fontainise bien plus loin lorqu’elle est perchée sur les épaules d’une géante.

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 "", line 1, in 
    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 "".format(self.cout_entretien, self.cout_achat)

>>> voitures = [Voiture(10000, 10000), Voiture(50000, 10000), Voiture(10000, 60000)]
>>> voitures
[, , ]
>>> def get_entretien_achat(voiture): 
...         return (voiture.cout_entretien, voiture.cout_achat)
... 
>>> sorted(voitures, key=get_entretien_achat)
[, , ]

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
[, , ]
>>> 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.