Original 11/12/96pc
 Back to the original |
|
Retour à l'index
|
Bienvenue au premier article d'une série destinée à démystifier quelques un des points les plus obscurs de la programmation en Perl. Nous nous attacherons plus à étudier ici des solutions concrètes à des problèmes communs plutôt qu'à présenter point par point les différents aspect du langage comme le ferait un cours.
Plusieurs articles ont été récemment postés dans
comp.lang.perl qui sont revenus sur un mécanisme de base peu connu de
l'utilisation en Perl de la fonction sort(). Le Camel Book [1]
consacre peu de place à sort() bien que ce soit une
fonction de base très puissante. Pour lui, sort() est
des plus simple : vous lui passez une liste et il vous la rend triée par
ordre alphabétique:
@list = (`how', `now', `brown', `cow');
@sorted = sort @laliste;
Si vous souhaitez un tri descendant, il vous suffit de passer la sortie de sort() à reverse() :
@ztoa = reverse sort @laliste;
Tout le monde suit ? Le point crucial de sort() est la
possibilité de définir son propre critère de tri en
passant en second paramètre à sort() le nom de la
fonction de tri à exécuter :
@sorted = sort mysort @list;
Chaque fois que sort() doit comparer 2 valeurs de
@list elle invoquera votre fonction ( mysort() dans
ce cas). Pour les tris ascendants,votre fonction doit retourner un entier
négatif quelconque, si la première valeur est inférieure
à la seconde, zéro si elles sont égales, un entier
positif si la première valeur est plus grande que la seconde. Un tri
descendant est obtenu en inversant les conditions. Les hackers UNIX
reconnaîtrons la similitude "fortuite" avec la fonction
qsort(3) de la libc.
Par souci de performance, le mécanisme normal d'appel fonctionnel de
Perl est court-circuité sur plusieurs aspects. Premièrement, les
valeurs à comparer son automatiquement passées dans les variables
$a et $b plutôt que dans la liste
d'arguments. Deuxièmement, ces valeurs sont passées par
référence. Si donc votre routine de tri bidouille ces valeurs vous
pouvez vous attendre à toutes sorte de choses désagréables dans le
reste de votre code. Troisièmenent, votre tri ne doit pas être
récursif.
Ceci étant posé, voici comment réaliser un tri ascendant :
@numbers = (3, 5, 4, 11, 1, 7);
@sorted = sort mysort @numbers;
sub mysort { $a <=> $b; }
Il suffit d'inverser l'ordre de $a et $b pour
obtenir un tri descendant (on peut aussi utiliser reverse() sur
la liste du résultat - ce ne serait pas un article sur Perl s'il n'y avait pas
la mention "Il y a plusieurs façons de procéder !"). Notez que la fonction
évite un appel explicite à return(). En l'absence de
return(), Perl retourne la valeur de la dernière expression évaluée.En fait, il n'est même pas nécessaire de créer une routine séparée - on peut utiliser directement un bloc à la place du nom de la fonction :
@sorted = sort { $a <=> $b; } @numbers;
Laissez vous guider ici par votre sense de l'estétique. Le personnes
particulièrement paresseuses feront remarquer que le point-virgule dans
le block est superflu si on utilise une version récente de Perl (pl35
ou plus). Toutefois, il y a tant de versions de Perl disséminées
dans le monde qui ne supporte pas cette, disons, possibilité,
pour que l'auteur se risque à recommander cette pratique.
Supposons que nous désirions sortir un rapport mensuel de l'utilisation
des disques durs. Nous disposons d'un tableau associatif, %usage
indexé par les noms des utilisateurs et contenant les tailles disques
consommées exprimées en méga-octets. Nous aimerions
obtenir une liste triée dans l'ordre décroissant des
consommations de façon à être en mesure d'envoyer un petit
mot aigre doux au "top ten" des consommateurs. Nous avons donc besoin de trier
la liste des clefs selon l'ordre des valeurs indexées :
@sorted = sort { $usage{$b} <=> $usage{$a}; } keys %usage;
Puisque la granularité de nos mesures est le méga-octet, nous
pouvons avoir plusieurs utilisateurs avec la même consommation. Nous
pouvons raffiner notre tri pour lister les ex-aequo dans l'ordre
alphabétique de leur nom :
@sorted = sort { $usage{$b} <=> $usage{$a} || $a <=> $b; } keys%usage;
Ceci est un exemple de tri multi-critère. Il repose sur l'optimisation
de l'évaluation du OU logique qui ne procède à la seconde
comparaison que si les premières valeurs comparées sont
égales (i.e, si l'opérateur <=> retourne
zéro).Supposons maintenant que nous ayons une liste formée du contenu d'un fichier et que nous voulions la trier sur plusieurs champs de chaque ligne. Par exemple, supposons que nous désirions trier le fichier des mots de passe dans l'ordre des parents des répertoires de login puis dans l'ordre du nom de login :
print sort psort @lines; sub psort {
($anm, $adr) = (split(/:/, $a))[0,5];
($bnm, $bdr) = (split(/:/, $b))[0,5];
$adr =~ s,/[^/]*,,; $bdr =~ s,/[^/]*,,;
$adr cmp $bdr || $anm cmp $bnm; }
La fonction utilise d'abord l'opérateur de segmentation pour
extraire le nom de login et le répertoire du fichier des mots de
passe. Elle utilise ensuite l'opérateur de substitution pour isoler le
nom du répertoire père du répertoire de login en
supprimant tous les caractères jusqu'au du dernier "/" inclus.
Malheureusement, cette approche a quelque chose d'inefficace. Une même ligne peut être comparée plusieurs fois (le quicksort est un tri en O(n log n). À chaque fois nous utilisons split() et recherchons l'expression régulière du père du répertoire de login. Nous pouvons améliorer les performances du tri en mémorisant cette information une fois pour toute, au prix d'un triplement de la mémoire consommée.
for (@lines) {
($nm{$_}, $dir{$_}) = (split(/: ))[0,5];
$dir{$_} =~ s,/[^/]*,,;
}
print sort { $dir{$a} cmp $dir{$b} || $nm{$a} cmp $nm{$b}; } @lines;
Cette approche est couramment 2 fois plus rapide que la
précédente.On peut également optimiser l'opération dans le cas d'un tri multi-critére sur des données numériques, par exemple les octets d'une adresse IP. En combinant les octets dans une seule donnée de type entier, le tri s'effectue en une seule opération de comparaison numérique :
for (@ipaddrs) {
$num{$_} = sprintf("%d%03d%03d%03d", split(/\./));
}
@sorted = sort { $num{$a} <=> $num{$b}; } @ipaddrs;
Une seule comparaison est généralement plus efficace qu'une conjontion
plusieurs comparaisons de chaînes de caractères.
Qu'avons nous appris ? Premièrement, que des concepts simples peuvent
avoir des applications complexes insoupçonnées. Dans le cas de
sort(), nous sommes passés d'un simple tri
alphabétique à des tri multi-critère et à des tris
sur des tableaux associatifs. Deuxièmement, un tri peut être
considérablement optimisé au prix d'un peu de réflexion et de
ressources mémoires supplémentaires. Troisièmement, les
données peuvent être regroupées pour minimiser le nombre de
comparaisons.
[1] Larry Wall and Randal Schwartz, Programming
Perl, O'Reilly and Associates, 1991.ISBN 0-937175-64-1.
Traduction de ;login: Vol. 18 No. 4, August 1993.
|
Dernière édition: 21 décembre 1997 phb Original 11/12/96pc |
|