Problème à signaler:


Télécharger Support de formation complet du langage Perl pour débutant



★★★★★★★★★★3.5 étoiles sur 5 basé sur 1 votes.
Votez ce document:



Support de formation complet du langage Perl pour débutant

...

Trois d'entre eux sont particulièrement puissants et méritent que l'on s'y attarde quelque peu :

  • for (et son synonyme foreach) : cet opérateur prend une liste en entrée (à sa droite) et applique un bloc de code à chaque élément du tableau ou de la liste. Par exemple :

my @tableau = 1..10; # @tableau contient 1, 2, 3, … 10

for my $item (@tableau) { $item *= 2;}; # @tableau contient 2, 4, 6 … 20

À noter que la variable $item utilisée dans la boucle est un alias sur chaque élément successif du tableau ou de la liste ; en modifiant $item, on modifie bien le contenu du tableau ; si la variable $item n'est pas spécifiée, c'est la variable par défaut $_ qui sert d'alias sur les éléments du tableau ;

  • grep : cet opérateur est un filtre : il prend une liste en entrée (à sa droite), applique un bloc de code à chaque élément et renvoie (en contexte de liste) les éléments pour lesquels ce bloc de code est évalué à vrai ; voici une autre manière d'alimenter un tableau avec les nombres pairs de 2 à 20, en filtrant les nombres impairs d'une liste de nombres de 1 à 20 :

my @tableau = grep { $_ % 2 == 0} 1..20;

À noter que la variable spéciale $_ utilisée dans la boucle est un alias implicite sur chaque élément successif de la liste reçue en entrée et grep renvoie les éléments de la liste divisibles par 2 ; le nombre d'éléments renvoyés par un grep est inférieur ou égal au nombre d'éléments en entrée ;

  • map : cet opérateur prend une liste en entrée (à sa droite), applique un bloc de code à chaque élément et retourne les nouveaux éléments ainsi calculés ; voici une troisième manière d'alimenter un tableau avec les nombres pairs de

2 à 20, en multipliant par 2 les éléments d'une liste de nombres de 1 à 10 :

my @tableau = map { $_ * 2 } 1..10;

Ici encore, la variable spéciale $_ utilisée dans la boucle est un alias implicite sur chaque élément successif de la liste reçue en entrée et maprenvoie dans @tableau les éléments de la liste en entrée multipliés par 2 ; la fonction map peut retourner zéro, un ou plusieurs éléments pour chaque élément en entrée et peut donc renvoyer une liste plus longue ou plus courte que la liste en entrée. Par exemple, il est possible de renvoyer le double, le triple et le quadruple de chaque élément en entrée :

my @tableau = map { $_ * 2, $_ * 3, $_*4 } 1..5;

Ce qui donne la liste suivante dans @tableau : 2 3 4 4 6 8 6 9 12 8 12 16 10 15 20.

À noter que les fonctions grep et map admettent une autre syntaxe utilisant une expression et non un bloc de code (voir la documentation). Ainsi, l'exemple ci-dessus utilisant le grep pour générer une liste de nombres pairs peut être réécrit comme suit :

my @tableau = grep $_ % 2 == 0, 1..20;

Cette syntaxe nécessite une virgule pour séparer l'expression de la liste de valeurs. Mais cette autre syntaxe n'apporte rien à la présente discussion, je m'en tiendrai à la syntaxe avec un bloc de code présentée précédemment, d'usage bien plus général.

Les trois exemples donnés avec les fonctions grep et map enchaînent en fait deux opérateurs de listes : en commençant à lire par la droite, il y a d'abord l'opérateur « .. » (par exemple 1..10) qui génère une liste de nombres (de 1 à 10 dans l'exemple ; cette liste est ensuite fournie en entrée à l'opérateur map (ou grep) qui retravaille cette liste de départ pour en faire ce dont on a besoin. Cette technique est extrêmement puissante et mérite d'être explorée plus en détail, c'est l'objet principal de ce tutoriel.

  1. Combiner les opérateurs de listes

La liste générée par le dernier map ci-dessus :

2 3 4 4 6 8 6 9 12 8 12 16 10 15 20,

est quelque peu désordonnée. Mais la magie des opérateurs de listes est que l'on peut les combiner pour faire des choses bien plus puissantes.

2-1. Enchaînements d'opérateurs

La fonction sort prend une liste ou un tableau en entrée et renvoie une liste triée. Utilisons-la sur le tableau généré précédemment :

my @tableau_trie = sort @tableau;

Oups, ça ne marche pas bien, car cela donne la liste suivante :

10 12 12 15 16 2 20 3 4 4 6 6 8 8 9.

Par défaut, la fonction sort fait un tri de type lexicographique (ou, en simplifiant un peu, alphabétique), et non numérique : les nombres commençant par 1 viennent avant ceux commençant par 2 et ainsi de suite. Pour remédier à ce problème, il est possible d'utiliser la fonction map pour remplacer les nombres n'ayant qu'un seul chiffre par un nombre à deux chiffres commençant par 0 (remplacer par exemple « 3 » par « 03 »).

@tableau = map { length $_ == 1 ? "0$_": $_ } @tableau;

Le map examine chaque élément du tableau à sa droite, il ajoute un zéro devant l'élément si c'est un nombre à un seul chiffre et renvoie vers le tableau à gauche de l'affectation une liste des éléments éventuellement modifiés. À noter que la variable @tableau se trouve à la fois en entrée (à droite) et en sortie (à gauche) de la fonction map. Perl gère très bien ce genre de situation. Le tableau contient maintenant :



02 03 04 04 06 08 06 09 12 08 12 16 10 15 20.

Il est maintenant possible de le trier correctement :

my @tableau_trie = sort @tableau;

Ce qui donne la liste suivante :

02 03 04 04 06 06 08 08 09 10 12 12 15 16 20.

Mais tout ceci est bien laborieux. Il est possible de combiner les différentes opérations de listes pour générer directement le tableau trié, sans passer par des tableaux intermédiaires :

my @tableau_trie = sort map { length $_ == 1 ? "0$_": $_ } map { $_ * 2, $_ * 3, $_*4 } 1..5;

Ceci me donne la liste suivante dans @tableau_trie :

02 03 04 04 06 06 08 08 09 10 12 12 15 16 20.

Ici, nous utilisons un modèle de programmation par flux de données (dataflow programming), nous avons réalisé une espèce de pipeline de commandes successives sur les données (c'est un peu l'équivalent des pipes en programmation sous le shell Unix). Pour comprendre une commande comme celle-ci, il faut la lire de droite à gauche (et de bas en haut si le code est réparti sur plusieurs lignes). L'opérateur de liste « .. » avec les arguments 1 et 5 génère une liste de cinq éléments, les nombres de 1 à 5. Cette liste est passée en argument au map sur sa gauche, qui génère les doubles, les triples et les quadruples des nombres de 1 à 5. Ces quinze nombres sont passés au mapplus à gauche, qui reformate les nombres n'ayant qu'un seul chiffre en une chaîne de caractères commençant par 0. La nouvelle liste ainsi produite est passée au sort qui trie les valeurs par ordre lexicographique. La liste triée résultante est renvoyée vers @tableau_trie.

Cette approche présente l'avantage de diviser un problème relativement complexe en une série de tâches plus simples. Cette stratégie s'appelle parfois « diviser pour régner » (divide and conquer). Les programmeurs Perl issus du monde de la programmation impérative procédurale classique mettent souvent pas mal de temps avant d'utiliser des fonctions comme grep et map. Le jour où ils décident de se l'approprier, ils se demandent comment ils ont pu s'en passer si longtemps.

Pour revenir à notre tâche, la liste obtenue n'est pas très satisfaisante : ces zéros au début des premiers nombres sont inélégants. Qu'à cela ne tienne ! Il suffit d'ajouter une nouvelle fonction map au pipeline pour éliminer ces zéros après le tri :

my @tableau_trie = map { s/^0//; $_ }

sort map { length $_ == 1 ? "0$_": $_ } map { $_ * 2, $_ * 3, $_*4 } 1..5;

Ce qui donne la liste suivante :

Dans ce nouveau map, le bloc de code utilise le fait que map fait un alias de chaque élément de la liste qui lui est passée dans $_ et que l'opérateur de substitution s/// travaille par défaut sur cette même variable $_. La commande s/^0// retire donc le zéro initial de chaque élément de la liste commençant par un 0. Mais comme, par défaut, la commande s/// retourne non la variable modifiée, mais le nombre de substitutions effectuées, il faut réévaluer $_ modifié avant la fin du bloc. Dans les versions récentes de Perl (à partir de 5.14), il existe un modificateur s///r permettant de renvoyer la variable modifiée. Sur ces versions, le bloc map {s/^O//r ;} produirait le même résultat que le bloc map { s/^0// ; $_

} employé ci-dessus.

Nous reviendrons plus loin assez longuement sur cet enchaînement map {…} sort map {…} qui est extrêmement utile dans de nombreux cas.

Le tableau obtenu présente encore l'inconvénient d'avoir des doublons (double 4, double 6, etc.) que l'on pourrait désirer supprimer. Rien de plus simple, il suffit d'ajouter un grep pour filtrer les doublons :

my ($dupl, $prev) = ("", "");

my @tableau_trie = grep {$dupl = ($_ == $prev ? 0: 1); $prev = $_; $dupl}

map { s/^0//g; $_ }

sort map { length $_ == 1 ? "0$_": $_ } map { $_ * 2, $_ * 3, $_*4 } 1..5;

Mon tableau est maintenant dédoublonné : 2 3 4 6 8 9 10 12 15 16 20. Le fonctionnement du dédoublonnage est le suivant : le bloc grep compare chaque élément ($_) à son prédécesseur (stocké dans $prev) et retourne faux (0) à grep s'il est identique et vrai (1) s'il est différent, si bien que le grep l'élimine s'il est identique ; le bloc stocke également $_ dans la variable $prev pour pouvoir faire la comparaison lors de l'examen de la valeur suivante de la liste fournie en entrée. Mais si le mécanisme de détection des doublons vous échappe, peu importe (pour une première lecture), l'important ici est que ce grep ajouté élimine les doublons de la liste.

À la réflexion, il n'y a pas vraiment besoin de la variable @tableau_trie si l'on désire juste afficher la liste à l'écran. Comme la fonction print est aussi un opérateur de liste, on peut juste ajouter un print devant le grep :

 print grep {$dupl = ($_ == $prev ? 0: 1); $prev = $_; $dupl} map { s/^0//g; $_ }

sort map { length $_ == 1 ? "0$_": $_ } map { $_ * 2, $_ * 3, $_*4 } 1..5;

Ce qui imprime : 2346891012151620. Ah, ce n'est pas l'affichage recherché, il faudrait des espaces ou des tirets entre les différentes valeurs pour les différencier. Ajoutons une fonction join qui va construire une chaîne de caractères avec les éléments de la liste séparés par des tirets :

print join '-', grep { $dupl = ($_ == $prev ? 0: 1); $prev = $_; $dupl}

map { s/^0//g; $_ }

sort map { length $_ == 1 ? "0$_": $_ }

map { $_ * 2, $_ * 3, $_*4 } 1..5;

Ce qui imprime à l'écran la liste de valeurs séparées par des tirets :

2-3-4-6-8-9-10-12-15-16-20.



Pour récapituler, on enchaîne maintenant dans le pipeline huit opérateurs de listes, dont six différents. Bon, j'ai peut-être un peu exagéré, il est assez rare de faire des constructions aussi complexes, mais j'espère avoir montré comment il était facile d'ajouter de nouvelles étapes de traitement dans ce genre de pipeline de données. On est très loin du C, non ?

Le genre de pipeline de données décrit ci-dessus est très efficace et très utile, mais il convient, comme pour beaucoup de bonnes choses, de ne pas en abuser et de veiller à ne pas obscurcir le code. Les exemples ci-dessus enchaînent jusqu'à huit opérateurs de listes (ce qui est déjà beaucoup), mais chaque opérateur ne faisant qu'une seule chose, il reste facile de comprendre pas à pas la succession des actions appliquées aux données en entrée. La mise en page du code en plusieurs lignes peut contribuer à clarifier l'enchaînement des tâches. Il ne faut pas hésiter, le cas échéant, à bien commenter le code, par exemple en donnant un échantillon des données en entrée et en sortie.

2-2. Retour sur la fonction sort

Faisons maintenant un aveu et révélons un point qui avait été provisoirement gardé sous le silence. Une partie de ce qui a été fait ci-dessus était en fait complètement inutile ; le but était purement pédagogique : montrer l'enchaînement naturel des traitements dans le pipeline. La fonction sort est fort heureusement tout à fait capable de trier une liste numériquement, sans avoir besoin de reformater les données comme nous l'avons fait ci-dessus. Il suffit de lui passer une fonction ou un bloc de code explicitant une comparaison numérique (et non lexicographique ou alphabétique). L'ajout du 0 initial et son retrait ultérieurement étaient en fait inutiles.

La fonction sort peut prendre un bloc de code, comme les fonctions map et grep, pour déterminer la façon dont sont faites les comparaisons entre les éléments du tableau à trier. En écrivant ceci :

my @tableau_trie = sort { $a <=> $b }

map { $_ * 2, $_ * 3, $_*4 } 1..5;

 on obtient directement un tableau trié contenant :

2 3 4 4 6 6 8 8 9 10 12 12 15 16 20.

Une fonction de tri doit généralement effectuer des comparaisons d'éléments deux à deux. La fonction sort de Perl n'échappe pas à cette règle, mais c'est à l'utilisateur de spécifier comment cette comparaison doit être effectuée. Le bloc {$a <=> $b} dit ceci : quand on compare deux éléments $a et $b, ce bloc retourne -1 si $a doit précéder $b dans la liste triée finale, 1 si $b doit précéder $a et 0 si les valeurs sont identiques. La fonction sort utilise les valeurs positive, négative ou nulle renvoyées par le bloc pour déterminer l'ordre dans lequel classer les éléments.

Nous pouvons donc simplifier le pipeline de commandes et supprimer les deux appels de map chargés du reformatage en modifiant le sort :

print join '-', grep { $a = $b == $_? 0: 1; $b = $_; $a;} sort {$a <=> $b}

map { $_ * 2, $_ * 3, $_*4 } 1..5 ;

2-3. Un minimum de réflexion ne nuit pas

En réalité, cette série de commandes est encore ridiculement compliquée, compte tenu des données en résultant. Le seul but était de montrer comment enchaîner une série d'opérateurs de listes pour manipuler un flux de données. Quel est le résultat final de cette série de commandes ? Une liste triée des multiples de 2, de 3 et de 4 inférieurs ou égaux à

  1. Comme les multiples de 4 sont aussi des multiples de 2, c'est en fait la liste triée des multiples de 2 et de 3 inférieurs ou égaux à 20.

Vous vous souvenez comment nous avons généré au tout début une série de nombres pairs de 0 à 20 avec la fonction grep ? Nous avons généré une liste de nombres de 1 à 20 et utilisé un filtre (divisible par 2) pour ne retenir que les nombres pairs. Il suffit ici de faire la même chose en utilisant deux filtres successifs : divisible par 2 ou divisible par 3 :

print join "-", grep { $_ % 2 == 0 || $_ % 3 == 0 } 1..20 ;

Cette commande imprime bien la liste de nombres suivants, séparés par des tirets :

2-3-4-6-8-9-10-12-14-15-16-18-20.

Le bloc de code dans le grep évalue d'abord si le nombre est pair et renvoie vrai si c'est le cas (l'élément est alors passé à la commande suivante, le join); si le nombre n'est pas pair, alors le bloc évalue si le nombre est divisible par 3 ; si c'est le cas, l'élément est passé à la suite du traitement ; si l'élément n'est ni pair ni divisible par 3, alors il est éliminé de la liste de sortie.

Cette suite de commandes est beaucoup plus simple que celle que nous avions vue antérieurement. Plus de sort, plus de map, seulement trois opérateurs de listes. Cela montre que, si le but n'avait pas été d'illustrer pas à pas la construction progressive d'un pipeline de données, j'aurais sans doute dû réfléchir un peu plus au résultat recherché avant de me lancer aveuglément dans un enchaînement beaucoup trop compliqué de commandes. La morale est que l'utilisation de cette technique de programmation des opérateurs de listes enchaînés permet des constructions extrêmement puissantes, mais ne dispense pas d'un minimum de réflexion.

En fait, il est possible de réduire un peu plus le nombre de caractères de la série de commandes en inversant le test de parité et de divisibilité par 3 :

print join "-", grep {not $_ % 2 && $_ % 3 } 1..20;

Mais le code résultat est sans doute nettement moins lisible ; la version précédente, qui dit plus clairement ce qu'elle fait, est certainement bien préférable.

2-4. Petite digression sur la question des performances



La simplicité du code est un objectif capital, mais, parfois, d'autres critères sont tout aussi cruciaux, voire plus, par exemple la rapidité d'exécution. On peut avoir besoin de créer une structure de données plus complexe pour améliorer les performances. Dans certains cas, la plupart des données en entrée ne sont pas utiles pour ce que l'on désire extraire ; filtrer dès le départ les données en entrée et garder les seules données utiles peut faire gagner beaucoup de temps. Je dois souvent, dans le cadre de ma profession, retraiter des fichiers de plusieurs dizaines ou même centaines de millions de lignes. Assez souvent, la première chose à faire est d'instaurer un filtre qui éliminera peut-être 90 % ou même 98 % des lignes et permettra de ne retraiter que les 10 % ou 2 % utiles. Le gain de temps peut dans certains cas être considérable.

Modifions un peu la recherche précédente de nombres divisibles par 2 et 3, en spécifiant que l'on désire cette fois garder les nombres entre 1 et 50 qui sont à la fois divisibles par 2 et par 3 (et non plus divisibles par 2 ou par 3). Ceci donne par exemple le code suivant :

print join "-",

grep { $_ % 2 == 0 && $_ % 3 == 0 }

1..50; # noter le && au lieu du ||

Ce qui affiche le résultat suivant : 6-12-18-24-30-36-42-48

Mais les nombres divisibles par 2 et par 3 sont les nombres divisibles par 6. Il est donc plus simple d'écrire :

print join "-", grep { $_ % 6 == 0 } 1..50; # affiche la même chose

Pour les nombres inférieurs à 50, le résultat est instantané, les performances n'ont aucune importance, on choisira la solution la plus simple ou la plus claire.

Mais si l'on désire les nombres inférieurs à dix millions, les performances ont peut-être de l'importance. Laquelle des deux solutions est-elle la plus rapide ? La seconde ne fait qu'une opération là ou la première en fait deux, mais, d'un autre côté, la division par 2 est peut-être très rapide en binaire et filtre d'entrée de jeu la moitié des nombres. Hum, difficile à dire. Faisons un petit benchmark rudimentaire. Sous Unix, la fonction time donne directement la durée d'exécution d'un programme. Essayons des scripts unilignes :

$ time perl -e '@c= grep { $_ % 6 == 0 } 1..10000000; print $#c +1;'

 1666666

real 0m2.837s

user 0m2.262s

sys 0m0.155s

$ time perl -e '@c= grep { $_ % 2 == 0 && $_ % 3 == 0 }

1..10000000; print $#c +1;'

1666666

real 0m2.987s

user 0m2.854s

sys 0m0.139s

La solution avec la divisibilité par 6 paraît légèrement meilleure, mais la différence est trop faible pour en être certain (et même trop faible pour qu'il soit vraiment utile de se poser la question). Il existe des modules Perl de benchmark bien plus avancés et plus précis (ils donnent un avantage un peu plus net au test de divisibilité par 6), mais il n'est pas utile de sortir ici de l'artillerie lourde pour chasser une simple mouche.

Peut-être que tester si le dernier chiffre est pair est plus rapide ? Voyons voir :

$ time perl -e '@c= grep { /[02468]$/ && $_ % 3 == 0 } 1..10000000; print $#c +1;'

1666666

real 0m15.215s

user 0m14.975s

sys 0m0.233s

Non, pas du tout, tester la parité du dernier chiffre avec une expression régulière donne un bien moins bon résultat. (La précompilation de l'expression régulière ou l'utilisation de l'option /o n'améliorent pas les choses.)

Et si l'on commençait par un map multipliant par 2 des nombres de 1 à 5 millions pour ne générer que des nombres pairs inférieurs à 10 millions et testait ensuite la seule divisibilité par 3 ?

$ time perl -e '@c= grep { $_ % 3 == 0 }

map { $_* 2} 1..5000000; print $#c +1;'

1666666

real 0m2.106s

user 0m2.058s

sys 0m0.046s

Ah, surprise (ou pas tant que cela, à vrai dire je m'y attendais un peu, mais je n'aurais pas parié dessus avant de tester), cette solution est meilleure que les précédentes : enchaîner le map (*2) et le grep (divisibilité par 3) donne des temps 35 % meilleurs que le grepsimple (divisibilité par 6). Mais, au fait, n'ai-je pas manqué de réflexion en faisant les opérations dans cet ordre ? Ne vaut-il pas mieux commencer par filtrer les multiples de 3 puis multiplier par 2 ? Voyons cela :

$ time perl -e '@c= map { $_* 2} grep { $_ % 3 == 0 } 1..5000000;

print $#c +1 ;'

1666666

 real 0m1.539s

user 0m1.450s

sys 0m0.077s

Nous obtenons un nouveau gain significatif. Nous laisserons au lecteur le soin de tester une dernière solution bien plus simple :

$ time perl -e '@c= map { $_* 6} 1..1666666; print $#c +1 ;'

Pour dire la vérité, les performances ne sont pas le but principal des pipelines de données. Dans un cas général, une boucle foreach sera assez souvent plus rapide, car elle ne copie pas les données plusieurs fois (de plus, dans certaines circonstances, il est possible d'arrêter une boucle foreach dès qu'elle a fourni le résultat désiré, alors que ce n'est pas possible avec les opérateurs de type map ou grep). Le but principal est de simplifier la programmation (une heure d'un développeur coûte bien plus cher qu'une heure de CPU). Mais il arrive assez fréquemment que le pipeline permette d'améliorer (parfois considérablement) les performances.



Dans le cas présent, entre 2,8 secondes et 2,1 secondes ou même 1,5 seconde, peu importe cette différence, mais il est intéressant de se poser la question et de réfléchir aux résultats et à leurs conséquences. Ici, la solution initialement la plus simple (un seul grep) n'était pas la meilleure, un map suivi d'un grep font assez nettement mieux. Finalement, un map différent fait encore mieux. Encore une fois, dans le cas de l'exemple, la solution la plus simple était bien suffisante, mais il est des situations où ajouter un peu de complexité apparente permet au programme (et à l'ordinateur) de mieux travailler. Parfois beaucoup mieux. C'est ce que nous allons voir avec certains algorithmes de tri.

  1. Opérateurs de listes et tris de données

Supposons que nous devions trier par ordre alphabétique du nom de famille la liste des personnalités suivantes : (François Hollande, Nicolas Sarkozy, François Fillon, Jean-Marc Ayrault, Ségolène Royal, Brice Hortefeux, Lionel Jospin, George W. Bush, Barack Obama, Lorie), et que la liste contienne plusieurs dizaines ou centaines de milliers de noms. Il s'agit de trier la liste selon le dernier « mot » (le nom de famille) apparaissant dans chaque élément de la liste.

3-1. Tri des noms de famille : version naïve

Il faut d'abord écrire une routine qui, recevant deux noms complets en entrée, extraira le dernier mot (le nom de famille), comparera les noms de famille, et renverra à la fonction sort les valeurs attendues (-1, 0, 1) selon l'ordre dans lequel les deux noms doivent apparaître dans la liste triée.

Voici une approche possible pour cette fonction de comparaison :

sub compare {

my $aa = $1 if $a =~ /(\w+)$/;

# extrait dans $aa le nom de famille du premier nom my $bb = $1 if $b =~ /(\w+)$/;

# extrait dans $bb le nom de famille du second nom return $aa cmp $bb};

# cmp renvoie à sort la valeur attendue (-1, 0, 1)

}

Nous pouvons maintenant construire le sort :

my @noms = ('François Hollande', 'Nicolas Sarkozy', 'François Fillon', 'Jean-Marc Ayrault', 'Ségolène Royal', 'Brice Hortefeux', 'Lionel Jospin', 'George W. Bush', 'Barack Obama', 'Lorie');

my @noms_tries = sort {compare($a, $b)} @noms; print join ' ,', @noms_tries;

La routine compare définie précédemment permet à la fonction sort de faire le travail attendu, trier la liste selon le dernier nom apparaissant dans chaque élément de la liste. Ce qui affiche la liste correctement triée :

….

3-2. Trier avec la transformation de Schwartz

La fonction compare définie précédemment marche bien, mais pose cependant un problème. Un algorithme de tri doit comparer chaque donnée en entrée avec une partie au moins des autres données ; il en résulte que chaque donnée est lue plusieurs fois. La liste ne possède ici que dix noms et la fonction compare est appelée 22 fois, à chaque fois avec deux noms, ce qui veut dire que l'extraction du nom de famille est effectuée 44 fois, soit en moyenne 4,4 fois pour chaque personnalité. Un essai avec 20 personnalités donne 63 appels à la fonction compare, soit 126 extractions de nom de famille, plus de 6 fois par personnalité. Avec 100 noms, on obtient 550 appels de la fonction compare, soit 1100 extractions de nom de famille, ou 11 fois par personnalité. Avec 1000 noms de personnalités, il y a 8677 appels de la fonction compare, soit environ 17 300 extractions de noms de famille, ou 17 fois par personnalité. Pour résumer :

  • 10 personnalités : 4,4 extractions de nom de famille par personnalité ;
  • 20 personnalités : 6 extractions de nom de famille par personnalité ;
  • 100 personnalités : 11 extractions de nom de famille par personnalité ;
  • 1000 personnalités : 17 extractions de nom de famille par personnalité.

Plus il y a de personnalités, plus le nombre d'appels par personnalité est élevé. La théorie de l'algorithmique dit que, pour N personnalités, le nombre d'appels à la fonction est à peu près proportionnel à N log N (pour l'algorithme de tri, réputé efficace, mis en œuvre par la fonction sort).

Ceci prendra beaucoup de temps quand il y aura des centaines, milliers ou des millions de noms. Ne peut-on pas faire en sorte de ne faire l'extraction du nom de famille qu'une seule fois ?

C'est essentiellement la question qui a été posée en décembre 1994, peu après la sortie de Perl 5, sur la liste de diffusion (ancêtre des forums actuels) comp.lang.perl : comment trier une telle liste sur le dernier nom (les noms étaient différents, bien sûr). Randal Schwartz, qui est depuis devenu une personnalité reconnue de la communauté Perl et un auteur prolifique sur ce langage, a répondu à l'époque avec le code suivant, en notant qu'il faisait essentiellement « du Lisp en Perl [5] » :

print map { $_->[0] }

sort { $a->[1] cmp $b->[1] }

map { [$_, /(\S+)$/] } @noms;

Cette construction est depuis connue dans la communauté Perl (et bien plus largement) sous le nom de Transformation de Schwartz (Schwartzian Transform). Nous retrouvons ici la construction « map sort map » utilisée précédemment. Ici encore, il faut lire ces enchaînements d'instructions de droite à gauche et de bas en haut. Le premier map (celui du bas) prend la liste de noms en entrée et crée une liste de tableaux anonymes de deux éléments contenant d'une part la donnée d'origine et d'autre par le dernier nom, celui sur lequel il faut trier. Ainsi, l'élément « François Hollande » de la liste d'origine est transformé en un tableau contenant deux éléments : ['François Hollande', 'Hollande'], de même pour les autres noms de la liste d'origine. Le sort reçoit en entrée cette liste de tableaux à deux éléments et fait le tri en basant ses comparaisons sur le deuxième élément de ces tableaux, le nom de famille. Une fois le tri terminé, le dernier map (celui du haut) renvoie à print le premier élément de ces tableaux, le nom complet.



L'avantage est que l'extraction du nom de famille n'est faite qu'une seule fois pour chaque nom. C'est une forme de la technique classique de la mise en cache, c'est-à-dire que l'on stocke une valeur en mémoire pour ne la calculer qu'une seule fois. Le tri peut être bien plus rapide s'il y a beaucoup de noms. Une fois la construction comprise, cette méthode est aussi plus concise et aussi probablement plus claire que la construction un peu laborieuse que nous avions présentée initialement avec la fonction compare.

3-3. La transformation de Guttman Rosler

La transformation de Guttman Rosler est une variante améliorée de la transformation de Schwartz applicable dans certains cas particuliers.

Supposons que nous ayons une série d'enregistrements concernant des articles parus dans la presse, avec le nom du journal, la date, le titre de l'article et peut-être d'autres informations que nous voulions les trier par ordre de date. Les enregistrements ont par exemple la forme suivante :

'Le Figaro; 10/04/2007; titre1'

'Le Monde; 17/12/2003; titre2'

'La Dépêche du Midi; 28/02/2012; titre3'

'Ouest-France; 14/06/2013; titre 4'

'Le Canard enchaîné; 18/10/2011; titre 5'

'La Voix du Nord; 14/11/2009; titre 6'

Nous pourrions utiliser la transformation de Schwartz et créer une série de tableaux anonymes à quatre éléments de la forme :



193