Outils pour utilisateurs

Outils du site


tri_python

Tri rapide de listes en utilisant les fonctions de tri intégrées (avec et sans indexation)

Objectif

Il existe 2 façons de trier une liste “L” en utilisant ce qui est déjà intégré dans Python:

  • la méthode L.sort([cmp[, key[, reverse]]])
  • la fonction sorted(L [, cmp[, key[, reverse]]])

Ces fonctions sont très efficaces, et il faut de très bonnes raisons pour programmer sa propre fonction de tri (même si c'est très amusant :-D). De plus, ces fonctions sont réputées être “stables”, et donc laisser les doublons dans l'ordre initial (ce qui permet les tris successifs selon plusieurs critères)

Il est manifestement facile de les utiliser pour trier une liste simple composée de nombres ou de chaines de caractères ascii. Mais il y a des cas où ce n'est pas simple du tout. Par exemple:

  • tri selon une partie de la chaine seulement (ex: selon L[][k1:k2])
  • tri d'une liste de liste selon l'un des membres de la sous-liste (ex: selon L[][k])
  • tri selon l'ordre numérique d'une liste de nombre exprimés sous forme de chaine (ex: L = ('5', '40', '9', '100', '0'))
  • tri selon l'ordre du dictionnaire français d'une liste de chaines avec majuscules et caractères accentués
  • tri d'une liste d'objets (classe) selon l'un de ses attributs
  • tri indexé d'une liste
  • tri indexé d'un fichier sur disque
  • etc…

Cette page est faite pour donner des solutions dans tous ces cas, sans pour autant obliger à créer sa propre fonction de tri!

Comme quoi les fonctions de tri de Python sont fichtrement bien foutues…;-)

Tri de listes simples

La méthode .sort() tri une liste de nombres ou de chaines de caractères “sur place”:

L = [5, 9, 4, 0, 8, 7, 3, 6, 2, 4]
L.sort()
print L
[0, 2, 3, 4, 4, 5, 6, 7, 8, 9]


Si on ne veut pas que la liste L soit modifiée par le tri, il suffit de faire une copie de la liste:

L = [5, 9, 4, 0, 8, 7, 3, 6, 2, 4]
R = list(L)
R.sort()
print R
print L
[0, 2, 3, 4, 4, 5, 6, 7, 8, 9]
[5, 9, 4, 0, 8, 7, 3, 6, 2, 4]


On peut aussi utiliser la fonction sorted() qui renvoie la liste triée. On peut donc l'affecter à une autre variable, ce qui ne change pas la liste initiale:

L = [5, 9, 4, 0, 8, 7, 3, 6, 2, 4]
R = sorted(L)
print R
[0, 2, 3, 4, 4, 5, 6, 7, 8, 9]
print L
[5, 9, 4, 0, 8, 7, 3, 6, 2, 4]


Ce qui a été fait ici pour une liste de nombres fonctionne de la même façon pour les chaines de caractères

L = ['Xavier', 'Alain', 'Martine', 'Julien', 'Christiane', 'Yves']
L.sort()
print L
['Alain', 'Christiane', 'Julien', 'Martine', 'Xavier', 'Yves']
 
L = ['Xavier', 'Alain', 'Martine', 'Julien', 'Christiane', 'Yves']
R = sorted(L)
print R
['Alain', 'Christiane', 'Julien', 'Martine', 'Xavier', 'Yves']


Malheureusement, avec un mélange de majuscules-minuscules et de caractères accentués, ça devient n'importe quoi, ceci parce que le tri se fait selon l'ordre des caractères dans l'encodage, et pas selon l'alphabet français.

L = ["toto","Xavier","Toto","résultat","précis","exécution","exemple", "élégant"]
R = sorted(L)
for x in R:
    print x.decode('utf-8')
 
Toto
Xavier
exemple
exécution
précis
résultat
toto
élégant

Vous voyez le résultat:

  • les majuscules se placent avant les minuscules (“Xavier” est avant “exemple”).
  • les minuscules accentuées se placent après les minuscules non-accentuées (“élégant” est après “toto”).

Bref, les fonctions de tri sort() et sorted() ne peuvent pas être utilisées telles quelles pour trier des mots français.

Heureusement, on peut modifier l'ordre de tri en ajoutant des fonctions supplémentaires: voir chapitre suivant. Il y a aussi sur ce site une page qui ne traite que de ça!

Tri de listes complexes avec fonctions de comparaison et fonction de conversion

Présentation générale des arguments cmp et key

Il se trouve que les fonctions de tri sort() et sorted() ont des arguments que nous n'avons pas encore utilisés: cmp et key.

  • pour la méthode sort: L.sort(cmp=cmp, key=None, reverse=False)
  • pour la fonction sorted: sorted(L, cmp=cmp, key=None, reverse=False)

L'argument cmp, initialisé par défaut à cmp (c'est à dire la fonction intégrée cmp(v1,v2)), définit la fonction à utiliser pour comparer 2 valeurs v1 et v2 dans le déroulement du tri.

Cette fonction prend 2 arguments (=2 des élements de la liste à trier pendant le tri) et doit renvoyer comme résultat:

  • une valeur négative si v1<v2
  • une valeur positive si v1>v2
  • zéro si v1==v2

C'est comme ça que fonctionne la fonction intégrée cmp(v1,v2), mais on peut la recréer pour vérifier qu'on a bien compris:

def comp(v1, v2):
    if v1<v2:
        return -1
    elif v1>v2:
        return 1
    else:
        return 0

Avec cette fonction, on peut trier de nouveau les listes précédentes pour obtenir, bien entendu, les même résultats:

L = [5, 9, 4, 0, 8, 7, 3, 6, 2, 4]
L.sort(cmp=comp)
print L
[0, 2, 3, 4, 4, 5, 6, 7, 8, 9]

Il y a un 2ème argument, key, initialisé à None. On peut affecter à cet argument une fonction qui va modifier la valeur à trier AVANT de rentrer dans les comparaisons.

Par exemple, au lieu de None, on va définir la fonction suivante, qui ne fait que renvoyer la valeur passée en paramètre:

def conv(v):
    return v

Avec cette fonction et la précédente, on peut encore trier en obtenant les même résultats qu'avant:

L = [5, 9, 4, 0, 8, 7, 3, 6, 2, 4]
L.sort(cmp=comp, key=conv)
print L
[0, 2, 3, 4, 4, 5, 6, 7, 8, 9]

En fait, les comparaisons entre 2 des éléments de la liste, v1 et v2, sont désormais faites avec: comp(conv(v1), conv(v2)).

Dernier argument: reverse, initialisé à False. Quand reverse=True, la liste est restituée triée à l'envers.

Maintenant qu'on a bien compris comment fonctionnent les 2 arguments cmp et key, on va passer aux choses sérieuses!!!

Tri d'une liste de chaines selon une sous-chaine

Considérons la liste suivante:

L = ["Xavier    Dupont    ",
     "Alain     Dupond    ",
     "Martine   Durand    ",
     "Julien    Toto      ",
     "ChristianeMeyer     ",
     "Yves      Machin    "]

On veut trier cette liste selon les noms, mais ce sont les prénoms qui sont en début de chaque chaine.

Comme les prénoms prennent 10 caractères, suivi par les noms qui prennent aussi 10 caractères, et si la chaine s'appelle x, on peut extraire les noms seuls par x[10:21].

On va donc définir une nouvelle fonction de comparaison:

def comp(v1, v2):
    if v1[10:21]<v2[10:21]:
        return -1
    elif v1[10:21]>v2[10:21]:
        return 1
    else:
        return 0

Et on va trier la liste par:

L.sort(cmp=comp)

Ce qui donnera:

['Alain     Dupond    ', 
 'Xavier    Dupont    ', 
 'Martine   Durand    ', 
 'Yves      Machin    ', 
 'ChristianeMeyer     ', 
 'Julien    Toto      ']

Ce qui est un résultat correct: la liste est bien triée selon les noms (et pas les prénoms).

Une fois qu'on sait faire cela, vous voyez qu'on pourrait trier ce genre de liste sur la base d'une sous-chaine extraite par d'autres moyens, par exemple grâce à un séparateur, ou même à l'aide d'une expression régulière.

Tri d'une liste de sous-liste selon l'un des éléments de la sous-liste

On veut trier la liste suivante selon le 2ème élement de chaque sous-liste:

L = [[9,4,7],[6,1,4],[2,7,4],[0,9,8],[4,3,7],[2,1,0],[3,7,9]]

On définit une nouvelle fonction de comparaison: les arguments v1 et v2 étant les éléments de la liste L, seront en fait ses sous-listes. Il est alors facile d'identifier le 2ème élément (indice=1).

def comp(v1, v2):
    if v1[1]<v2[1]:
        return -1
    elif v1[1]>v2[1]:
        return 1
    else:
        return 0

Et on tri comme d'habitude:

L.sort(cmp=comp)

Ce qui donne:

[[6, 1, 4], [2, 1, 0], [4, 3, 7], [9, 4, 7], [2, 7, 4], [3, 7, 9], [0, 9, 8]]

Ce qui est un résultat correct!

Tri numérique d'une liste de nombres stockés sous forme de chaine

Voilà un cas où nous aurons besoin de l'argument “key”.

Considérons la liste suivante:

L = ["20","135","5","72","800","10","35","2000"]

Il s'agit de nombres entiers stockés sous forme de chaine de caractère. Un peu comme ce qu'on pourrait obtenir de la lecture d'un fichier disque sans conversion.

Le problème du tri d'une telle liste, c'est que l'ordre de tri de chaine ne sera pas le même que l'ordre de tri des nombres. Par exemple:

  • tri chaine: “135” est avant “20”
  • tri nombre: 20 est avant 135

Pour trier cette liste de chaine selon l'ordre des nombres, il suffit de définir une fonction de conversion:

def conv(v):
    return int(v)

On pourrait d'ailleurs faire cela sous forme de fonction lambda:

conv = lambda x: int(x)

Et donner la référence de cette fonction à la fonction de tri:

print sorted(L, key=conv)

Et comme c'est une fonction simple, on peut même faire:

print sorted(L, key=int)

Ce qui donnera:

['5', '10', '20', '35', '72', '135', '800', '2000']

ce qui est correct, alors que le tri selon l'ordre des chaines aurait donné:

['10', '135', '20', '2000', '35', '5', '72', '800']

Bien entendu, si les nombres sont flottants, ou un mélange entier-flottant, il faudra utiliser float pour la conversion au lieu de int. Par exemple:

print sorted(L, key=float)

A noter qu'avec cette même technique, on pourrait trier une liste de nombres complexes selon le critère voulu (longueur du vecteur, angle, …).

Tri d'une liste de chaines avec majuscules et caractères accentués

Le principe est simple: on définit la liste des caractères (majuscule, minuscule, accentués, caractères spéciaux, …) dans l'ordre où on les veut, et on définit la fonction de conversion qui pourra comparer 2 mots selon cette liste de caractères. On peut faire vraiment tout ce qu'on veut, y compris, par exemple, mettre le symbole de l'Euros juste après le “E”!

Voir la page dédiée à cette question sur ce site:

http://python.jpvweb.com/mesrecettespython/tris_alpha

Tri d'une liste d'objets selon un des attributs

On peut regrouper des valeurs comme attributs d'objets créés sous forme d'une classe, et les stocker dans une liste. Par exemple:

class Objet(object):
    def __init__(self, n1, n2, n3):
        self.n1 = n1
        self.n2 = n2
        self.n3 = n3
 
L = []
L.append(Objet(9,4,7))
L.append(Objet(6,1,4))
L.append(Objet(2,7,4))
L.append(Objet(0,9,8))
L.append(Objet(4,3,7))
L.append(Objet(2,1,0))
L.append(Objet(3,7,9))

Ce qui donne:

for x in R:
    print x.n1, x.n2, x.n3
 
9 4 7
6 1 4
2 7 4
0 9 8
4 3 7
2 1 0
3 7 9

Si on veut trier ces objets selon le 2ème attribut (.n2), on va créer une fonction de comparaison:

def comp(v1, v2):
    if v1.n2<v2.n2:
        return -1
    elif v1.n2>v2.n2:
        return 1
    else:
        return 0

Et pour trier:

R = sorted(L, comp)

Ce qui donnera:

for x in R:
    print x.n1, x.n2, x.n3
 
6 1 4
2 1 0
4 3 7
9 4 7
2 7 4
3 7 9
0 9 8

Ce qui est le bon résultat.

A noter que rien ne nous empêche de combiner les fonction de comparaison (cmp=) et de conversion (key=).

Tri indexés de listes ou de fichiers

Tri indexé de listes

On a une liste qu'on veut trier, mais on ne veut pas la modifier ni avoir une 2ème liste de même contenu en mémoire (liste trop grande).

On va donc utiliser une liste d'index, et c'est avec cette liste qu'on va pouvoir retrouver triée la liste initiale sans la modifier.

Par exemple:

L = ["Xavier","Alain","Martine","Julien","Christiane","Yves"]

On fabrique la liste d'index qui doit contenir au départ [0,1,2,3,…] et avoir la même longueur que L:

IND = [i for i in range(0,len(L))]

Et c'est le fichier d'index IND que nous allons “trier”, mais avec une fonction de conversion qui dira qu'au lieu de considérer l'index i, on considérera la valeur L[i]:

conv = lambda i: L[i]
IND.sort(key=conv)

Ce qui fait qu'une fois trié, le fichier d'index permettra de retrouver les valeurs de L dans l'ordre du tri!

print IND
 
[1, 4, 3, 2, 0, 5]
 
for i in range(0,len(L)):
    print L[IND[i]]
 
Alain
Christiane
Julien
Martine
Xavier
Yves

Tri indexé de fichiers

On va considérer un fichier en accès direct sur disque, caractérisé par une longueur d'enregistrement fixe. Vous trouverez sur ce site une page web dédiée à ce genre de fichiers ici: http://python.jpvweb.com/mesrecettespython/fichier_acces_direct. Veuillez vous y reporter pour les détails concernant ce genre de gestion.

On va prendre un exemple.

On va créer d'abord un fichier en accès direct, contenant des valeurs numériques au hasard:

import random
 
L = [str(random.randint(100,9999)) for i in range(0,10)]
 
fichier = "datas.fad"
lge = 5
 
f = open(fichier, 'wb')
for i in range(0, len(L)):
    f.seek(i*lge)
    f.write(L[i] + "     "[0:lge-len(L[i])])
f.close()

On va donc avoir dans ce fichier les valeurs (par exemple):

['2087', '7412', '5131', '3478', '9366', '4468', '3697', '6548', '577', '5509']

On va ensuite créer une fonction simple de récupération d'un enregistrement du disque en fonction de son indice:

def litdata(i):
    global f, lge
    f.seek(i*lge)
    return int(f.read(lge).strip())

Vous noterez que l'enregistrement lu est ici transformé en entier (int), ce qui veut dire que nous voulons ici un tri numérique.

Nous créons maintenant le code pour trier ce fichier disque avec une liste d'index:

f = open(fichier, 'rb')
 
IND = [i for i in range(0,len(L))]
 
IND.sort(key=litdata)
 
for i in range(0,len(L)):
    print litdata(IND[i])
 
f.close()

Ce qui affichera (par exemple):

577
2087
3478
3697
4468
5131
5509
6548
7412
9366

Et on voit bien que le fichier disque est relu, grâce au fichier index, dans l'ordre numérique voulu!

Ce tri indexé aura, entre autres, un grand avantage: celui de permettre des recherches très rapides (par dichotomie) dans de très grands fichiers.


Amusez-vous bien!

tri_python.txt · Dernière modification: 2008/12/21 07:52 de tyrtamos

Outils de la page