Programmation fonctionnelle en Perl

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 map plus à 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 :

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

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 ?

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 ;

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 à 20. 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.

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 grep simple (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.

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 :

Jean-Marc Ayrault, George W. Bush, François Fillon, François Hollande, Brice Hortefeux, Lionel Jospin, Lorie, Barack Obama, Ségolène Royal, Nicolas Sarkozy.

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.

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 :

['Le Figaro; 10/04/2007; titre1', 10, 04, 2007]

puis utiliser un bloc sort de la forme suivante :

sort { $a[3] <=> $b[3] || $a[2] <=> $b[2] || $a[1] <=> $b[1] }

Ce bloc sort compare d'abord l'année ($a[3] et $b[3]) ; si les années sont différentes, cela suffit à la comparaison, le reste du code de comparaison n'est pas exécuté (le || court-circuite le reste du code quand l'élément qui le précède est évalué à vrai) ; si les années sont identiques, la comparaison des années est évaluée à 0 (fausse), et le bloc de comparaison des mois est exécuté, puis, si besoin, celui des jours.

On peut cependant faire plus simple et plus rapide : reformater les enregistrements pour qu'ils aient la forme :

'20070410;Le Figaro; 10/04/2007; titre1'
'20031217;Le Monde; 17/12/2003; titre2' 
'20120228La Dépêche du Midi; 28/02/2012; titre3'
...

En plaçant en début d'enregistrement une chaîne de caractères représentant l'année, le mois et le jour (la clé de tri), on peut faire un simple tri lexicographique des enregistrements.

my @articles = (
     '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'
              );
print   map {s/^\d{8};//; $_."\n"} 
        sort
        map {my $date = "$3$2$1" if m[;(\d\d)/(\d\d)/(\d{4});]; 
             "$date;$_";}
        @articles;

Ce qui imprime la liste correctement triée par dates :

Le Monde; 17/12/2003; titre2
Le Figaro; 10/04/2007; titre1
La Voix du Nord; 14/11/2009; titre 6
Le Canard enchaîné; 18/10/2011; titre 5
La Dépêche du Midi; 28/02/2012; titre3
Ouest-France; 14/06/2013; titre 4

Le tri lexicographique simple, sans devoir extraire les éléments de chaque tableau anonyme, permet à la fonction sort de travailler à son maximum d'efficacité et offre donc des performances d'exécution supérieures.

Voici un autre exemple simple de cette transformation, que j'ai donné suite à une question posée sur un forum Perl en août 2013. Soit à trier une liste de fichiers de la forme suivante :

abcd1_abc_123456.abc1a_A.201307290800-0900-0.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-1.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-10.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-11.gz

Tous les fichiers ont un début de nom identique, suivi par une date et heure, suivi par une autre heure sur quatre chiffres, suivi par un numéro d'ordre à un ou deux chiffre(s). La seule difficulté est le numéro d'ordre final. Sans lui, un simple sort lexicographique convient. Il suffit donc de renommer provisoirement les noms de fichiers, de les trier, puis de leur redonner leur nom d'origine.

use strict;
use warnings; 

my @files =  map {s/-0(\d)(\.gz)$/-$1$2/; $_} 
             sort
             map { s/-(\d)(\.gz)$/-0$1$2/; $_ } <DATA>;

print $_ for @files; 

__DATA__ 
abcd1_abc_123456.abc1a_A.201307290800-0900-0.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-1.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-10.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-11.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-2.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-3.gz
abcd1_abc_123456.abc1a_A.201306290800-0900-0.gz
abcd1_abc_123456.abc1a_A.201306290800-0900-1.gz
abcd1_abc_123456.abc1a_A.201306290800-0900-10.gz
abcd1_abc_123456.abc1a_A.201305290800-0900-11.gz
abcd1_abc_123456.abc1a_A.201308290800-0900-2.gz
abcd1_abc_123456.abc1a_A.201302290800-0900-3.gz
abcd1_abc_123456.abc1a_A.201306290800-1000-1.gz
abcd1_abc_123456.abc1a_A.201306290800-1000-10.gz
abcd1_abc_123456.abc1a_A.201305290800-1000-11.gz
abcd1_abc_123456.abc1a_A.201308290800-1000-2.gz
abcd1_abc_123456.abc1a_A.201302290800-1000-3.gz

Les trois lignes de code du tri suffisent à trier correctement les noms de fichiers et le programme affiche le résultat :

abcd1_abc_123456.abc1a_A.201302290800-0900-3.gz
abcd1_abc_123456.abc1a_A.201302290800-1000-3.gz
abcd1_abc_123456.abc1a_A.201305290800-0900-11.gz
abcd1_abc_123456.abc1a_A.201305290800-1000-11.gz
abcd1_abc_123456.abc1a_A.201306290800-0900-0.gz
abcd1_abc_123456.abc1a_A.201306290800-0900-1.gz
abcd1_abc_123456.abc1a_A.201306290800-0900-10.gz
abcd1_abc_123456.abc1a_A.201306290800-1000-1.gz
abcd1_abc_123456.abc1a_A.201306290800-1000-10.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-0.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-1.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-2.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-3.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-10.gz
abcd1_abc_123456.abc1a_A.201307290800-0900-11.gz
abcd1_abc_123456.abc1a_A.201308290800-0900-2.gz
abcd1_abc_123456.abc1a_A.201308290800-1000-2.gz

Les exemples présentés jusqu'à maintenant, dans une large mesure numériques, n'ont pas permis de rendre justice à une fonction essentielle et très utilisée dans le genre de pipeline de données dont nous parlons, split. La fonction split prend en entrée une chaîne de caractères, par exemple une ligne d'un fichier texte ou un enregistrement renvoyé par une requête dans une base de données, et permet de transformer cette chaîne en une liste de « mots » (sous-chaînes) qui pourront être retraités par les autres opérateurs de listes. C'est donc une fonction très souvent utilisée en entrée d'un enchaînement de fonctions de listes, car elle permet de créer la liste à retravailler à partir de données textuelles.

La fonction split prend en entrée des arguments tous optionnels :

• un motif (souvent une expression régulière, mais peut être autre chose, par exemple un simple caractère) définissant le séparateur sur lequel découper la chaîne de caractères. En l'absence de tout argument, split découpe la variable par défaut $_ sur les espaces blancs ; si le motif est une chaîne vide ou une expression régulière vide, la chaîne de caractères entrée est découpée en caractères individuels ;
• la variable (chaîne de caractères) à découper en sous-chaînes (variable $_ par défaut) ;
• une limite définissant le nombre maximal de sous-chaînes à créer (la dernière contiendra la fin de la chaîne).

Par exemple :

$_ = "Maître corbeau, sur un arbre perché, tenait en son bec un fromage";
my @tableau = split;

La fonction split découpe la chaîne contenue dans $_ selon les espaces. La variable @tableau contient maintenant la liste de mots suivants : (« Maître », « Corbeau, », « sur », « un », etc.).

3-4-1. Exemples simples d'utilisation de la fonction split▲

$ perl -e 'print join "-", split / /, "Maître corbeau, sur un arbre perché, tenait..."'

Maître-corbeau,-sur-un-arbre-perché,-tenait...

$ perl -e 'print join "-", split /,/, "Maître corbeau, sur un arbre perché, tenait..."'

Maître corbeau- sur un arbre perché- tenait...

$ perl -e 'print join "-", split /, /, "Maître corbeau, sur un arbre perché, tenait..."'

Maître corbeau-sur un arbre perché-tenait...

$ perl -e 'print join "-", split /arbre/, "Maître corbeau, sur un arbre perché"'

Maître corbeau, sur un - perché

$ perl -e 'print join "-", split /a[br]+.e/, "Maître corbeau, sur un arbre perché"'

Maître corbeau, sur un - perché

$ perl -e 'print join "-", split //, "corbeau"'
c-o-r-b-e-a-u

$ perl -e 'print join "-", split / /, "Maître corbeau, sur un arbre perché, ...", 4'

Maître-corbeau,-sur-un arbre perché, ...

$ perl -e 'print join "-", (split / /, "Maître corbeau, sur un arbre perché")[4,0]'
arbre-Maître

3-4-2. Une analyse linguistique rudimentaire▲

my %mots;
my $phrase = "Maître Corbeau,   sur un arbre perché, tenait   en son bec un fromage.";
print join "-", split /[,. ]+/, $phrase;

print join "-", map { $_= lc; tr/éî/ei/; $_;} split /[,. ]+/, $phrase;

$mots{$_}++ foreach map { $_= lc; tr/éî/ei/; $_;} 
            split /[,. ]+/, $phrase;

0  HASH(0x80359c08)
   'arbre' => 1
   'bec' => 1
   'corbeau' => 1
   'en' => 1
   'fromage' => 1
   'maitre' => 1
   'perche' => 1
   'son' => 1
   'sur' => 1
   'tenait' => 1
   'un' => 2

print map {$mots{$_}, "\t$_\n"} 
      reverse sort {$mots{$a} <=> $mots{$b}} 
      keys %mots;

2       un
1       arbre
1       bec
1       en
1       fromage
1       maitre
1       perche
1       tenait
1       sur
1       son
1       corbeau

print map {$mots{$_}, "\t$_\n"} 
      sort {$mots{$b} <=> $mots{$a} || $a cmp $b} 
      keys %mots;

2       un
1       arbre
1       bec
1       corbeau
1       en
1       fromage
1       maitre
1       perche
1       son
1       sur
1       tenait

3-4-3. Analyse d'un texte plus long▲

#!/usr/bin/perl
use strict;
use warnings;

my %mots;
my $texte;
{
    local $/ = undef; # redéfinit localement le séparateur d'enregistrements en entrée
    $texte = <>; # charge tout dans la variable scalaire $texte
}

$mots{$_}++ foreach 
            map {$_= lc; tr/àâéèêëîôùûç/aaeeeeiouuc/; $_;} 
            split /[,.:;"?!'\n ]+/, $texte;

print map {$mots{$_}, "\t$_\n"} 
      sort {$mots{$b} <=> $mots{$a} || $a cmp $b} 
      keys %mots;

5       un
4       corbeau
4       le
3       a
3       de
3       et
3       l
3       que
3       vous
2       bec
2       ces
2       en
2       etes
2       fromage
2       maitre
2       monsieur
2       ne
2       peu
2       renard
2       sa
2       sans
2       se
2       votre
1       alleche
1       apprenez
1       arbre
1       aux
1       beau
1       belle
1       bien
1       bois
1       bon
1       bonjour
1       ce
1       celui
1       cette
1       confus
1       depens
1       des
1       dit
1       doute
1       du
1       ecoute
1       flatteur
[...]

3-4-4. Analyse de livres entiers▲

33093   de
31980   et
19813   la
18170   a
18132   l
17535   le
16774   les
12391   il
10103   qui
9844    des
9492    d
[...]

$mots{$_}++ foreach
            map { $_= lc; tr/àâéèêëïîôùûç/aaeeeeiiouuc/; $_;}
            grep {length > 2} 
            split /[,.:;"?!'\n ]+/, $texte;

16774   les
10103   qui
9844    des
9112    que
7350    est
6966    eternel
6826    dans
6336    vous
6284    pour
5931    ils
4546    pas
4272    sur
4176    dieu
4161    fils
4041    lui
3864    dit
3808    une
3510    son
3349    avec
3184    nous
3091    car
2993    par
2958    ses
2924    comme
2793    leur
2602    israel
2590    mais
2563    roi
2548    tous
2418    mon
2293    point
2255    ton
2120    tout
2069    sont
2046    elle
1949    maison
1910    leurs
1856    avait
1846    toi
1800    homme
1799    pays
1784    peuple
1773    etait
1736    moi
1668    ceux
1642    aux
1591    tes
1580    devant
1517    plus
1513    celui
1474    fait
1430    voici
1427    sera
1385    contre
1338    seigneur
1315    jour
1248    hommes
1243    terre
1241    ainsi
1231    ont
1211    ces
1191    enfants
1178    mes
1171    eux
1147    jusqu
1106    david
1093    toutes
1086    pere
1082    fut
1078    quand
1045    afin
1024    ete
1014    jesus
996     toute
984     apres
965     vers
946     aussi
936     cette
931     vos
916     etaient
900     main
882     deux
880     fit
864     suis
862     moise
840     juda
828     coeur
821     jerusalem
817     entre
812     ville
807     nom
806     parole
798     parle
796     femme
795     pourquoi
794     votre
791     selon
788     meme
780     alors
774     parce

2204    article
1999    des
1937    une
1912    les
1665    par
1614    est
928     ans
774     dans
770     pour
730     amende
652     emprisonnement
614     prevues
593     personne
533     euros
521     peines
512     aux
503     fait
490     puni
486     qui
477     sont
462     infraction
424     soit
415     peine
367     personnes
357     sur
339     que
334     interdiction
334     lorsque
321     son
293     infractions
291     exercice
283     ete
281     cas
280     peut
275     pas
270     lorsqu
267     articles
264     cinq
261     present
259     etre
254     elle
242     criminelle
240     duree
229     plus
223     modalites
219     publique
218     tout
216     reclusion
214     commise

Exemple de question sur le forum Perl de Developpez.com : « J'ai un fichier sous forme de tableau, et je veux lire ce tableau colonne par colonne et faire un traitement pour chaque colonne (calculer le nombre de champs contenant "OO" dans chaque colonne). » Suivaient une bonne vingtaine de lignes de code ne faisant apparemment pas ce que désirait le demandeur. Il suffit, si l'on y réfléchit, de transposer les lignes et les colonnes dans une structure interne du programme pour ensuite compter les occurrences de « OO » :

use strict;
use warnings;

my @transposed_array;
while (<DATA>) {
     print;
     my $i;
     map {$transposed_array[$i++] .= $_;} split;
}
print join "  ", 
      map {my $count = s/OO/00/g; $count? $count : 0;}
      @transposed_array;

__DATA__
A1 A2 A3 A4 A5
CC NA OO UV OO
NA OO OO OO CP
TR OO UU RR OO

Six lignes de code réel suffisent à afficher le résultat désiré :

A1 A2 A3 A4 A5
CC NA OO UV OO
NA OO OO OO CP
TR OO UU RR OO
0  2  2  1  2

En fait, on peut même le faire dans un script uniligne Perl :

$ perl -pe '$i = 0; map {@c[$i++] .= $_;} split; END {print join "  ", map {$d = s/OO/00/g; $d ? $d : 0;} @c}' data.txt

Ce qui affiche :

A1 A2 A3 A4 A5
CC NA OO UV OO
NA OO OO OO CP
TR OO UU RR OO
0  2  2  1  2

Voici un exemple professionnel (très simplifié, mais réel). J'ai en entrée un fichier de 35 millions d'enregistrements clients issu d'une base de données applicative (un enregistrement par client). Parmi les données, chaque client a une liste de 20 à 30 prestations actives en moyenne (sauf rares exceptions, chaque prestation n'apparaît qu'une seule fois, le catalogue de la société contient environ 9000 prestations).

Il faut effectuer une transcodification avec une autre application. On dispose pour ce faire d'une matrice de conversion qui, à une paire de prestations associe un rate plan (plan tarifaire) de l'autre application. Si plusieurs paires de prestations d'un client apparaissent dans la matrice, la matrice définit un ordre de priorité permettant de définir un seul rate plan.

Pour chacun des 35 millions de clients, il faudrait donc tester toutes les paires de prestations pour trouver la meilleure. Une simple analyse combinatoire montre que si un client possède disons 20 prestations, il existe 20 * 19 / 2 = 190 combinaisons possibles. (J'ai en fait beaucoup simplifié le problème. Dans la réalité, d'autres éléments que les prestations entrent en ligne de compte pour la détermination du plan tarifaire, on a au total plutôt de l'ordre de 1500 à 2000 combinaisons à tester, mais, compte tenu de l'explosion combinatoire, les paires de prestations expliquent l'essentiel de la lourdeur.)

Essentiellement, je dois, pour chaque client, lire la liste de prestations, constituer toutes les paires possibles de prestations et vérifier chaque paire dans la table de hachage dans laquelle j'ai chargé la matrice pour choisir finalement celle ayant la priorité la plus haute. Cela risque de prendre beaucoup de temps.

Mais, en fait, la matrice ne contient que les prestations d'un certain type (service TV). Sur les 9000 prestations du catalogue, seules environ 200 apparaissent dans la matrice. De plus, il s'avère qu'en moyenne, chaque client ne possède parmi ses 20 ou 30 prestations que 2 ou 3 (rarement plus) figurant dans la matrice.

Lors de la constitution de la table de hachage contenant les paires de prestations à tester à partir du fichier matrice, j'ai constitué une seconde table de hachage accessoire contenant juste une liste de toutes les prestations apparaissant au moins une fois dans la matrice (donc environ 200 prestations). Cette seconde table de hachage, fonctionnellement inutile pour l'algorithme de base du programme, permet de filtrer les prestations à tester par paires en ne gardant que celles susceptibles d'apparaître dans des paires réelles figurant dans la matrice.

Ceci donne le code suivant :

my @array_presta = grep { exists $liste_presta_a_garder{$_} }
                   split /,/, $tmp_liste_presta;

La variable $tmp_liste_presta contient la liste des prestations actives du client dans une chaîne de caractères (avec la virgule comme séparateur). Le split génère la liste des prestations. Le hachage %liste_presta_a_garder contient les seules prestations utiles. Le « grep { exists $liste_presta_a_garder{$_} } » n'a aucune utilité fonctionnelle, le code donnerait les mêmes résultats sans, mais il a permis de diviser par un facteur de l'ordre de 100 la durée d'exécution du programme en réduisant le nombre de paires de prestations à tester pour chaque client de 200 ou 300 à 1 à 3 en moyenne.

J'ai fait d'autres optimisations importantes à ce programme. Au total, j'ai divisé la durée d'exécution d'un facteur de 1400 environ (sa durée d'exécution est passée d'environ 59,5 jours quand on m'a demandé de l'optimiser à 1 heure quand j'ai livré le résultat). Je n'ai pas mesuré en détail la contribution de chaque optimisation, mais j'ai tout de même fait des tests au fur et à mesure de mes travaux, et il ne fait pas de doute dans mon esprit que le simple grep ci-dessus suffit à lui seul à expliquer le passage de près de 60 jours à peut-être 10 ou 15 heures. Les autres optimisations réalisées m'ont donné un gain additionnel loin d'être négligeable, mais pas comparable.

Soit un tableau d'employés et un tableau de salaires. Le premier nom reçoit le premier salaire, et ainsi de suite. Je désire trier les employés selon leur salaire.

La structure de données avec deux tableaux n'est pas vraiment appropriée. Il est préférable de commencer par construire une table de hachage :

my @noms = qw (marie nicolas isabelle yves);
my @salaires = qw (1500 1250 1700 2000);
my %noms_salaires;
@noms_sal{@noms} = @salaires;

La dernière ligne ci-dessus utilise une syntaxe de liste dont je n'ai pas parlé : les tranches de tables de hachage (hash slices). Elle permet d'affecter directement la liste des salaires à la liste de noms dans la table de hachage. J'ai maintenant la table de hachage %noms_sal suivante (il faut que les noms soient uniques) :

   'isabelle' => 1700
   'marie' => 1500
   'nicolas' => 1250
   'yves' => 2000

Il est dès lors très simple de trier la table de hachage en fonction des valeurs contenues dans le hash :

my @employes_tries = sort {$noms_sal{$a} <=> $noms_sal{$b} } 
                     keys %$noms_sal;

Ou, si l'on préfère imprimer les résultats :

print map {"$_: $noms_sal{$_} \n"} 
      sort {$noms_sal{$a} <=> $noms_sal{$b} } 
      keys  %noms_sal;

Ce qui imprime :

nicolas: 1250
marie: 1500
isabelle: 1700
yves: 2000

Si l'on préfère avoir les noms en ordre descendant de salaire, il suffit d'intervertir $a et $b :

print map {"$_: $noms_sal{$_} \n"} 
      sort {$noms_sal{$b} <=> $noms_sal{$a} } 
      keys  %noms_sal;

ou d'utiliser la fonction reverse :

print map {"$_: $noms_sal{$_} \n"} 
      reverse sort {$noms_sal{$a} <=> $noms_sal{$b} }
      keys  %noms_sal;

Un dernier exemple certainement exagéré, mais qui démontre cependant la puissance de ces constructions et l'excellente capacité du compilateur Perl à les gérer.

Soit le fichier en entrée suivant :

B5F3Y8##MF01624.15;13-125;900-950@MF05188.12;133-258@MF05192.13;273-562@MF05190.13;430-521@MF00488.16;569-801@
B5F414##MF01583.15;27-182@
B5F415##MF00009.22;25-246@MF03144.20;261-325@
B5F430##MF01077.17;172-331;425-559@MF03460.12;73-140;350-418@

Il faut trier selon les nombres dans le fichier pour obtenir ceci :

B5F3Y8##MF01624.15;MF05188.12;MF05192.13;MF05190.1 3;MF00488.16;MF01624.15;
B5F414##MF01583.15;
B5F415##MF00009.22;MF03144.20;
B5F430##MF03460.12;MF01077.17;MF03460.12;MF01077.1 7;

Je passe sur les détails fonctionnels (la demande est vraiment assez tordue) et donne la solution que j'ai proposée (et qui marchait) :

   while (my $line = <$FILE_IN>) {
        my ($start, $end) = split /##/, $line;
        my @fields =  map { my ($id, @values) = split /;/, $_;
                @values = map { (split /-/, $_)[0]} @values; 
                map {[$id, $_]}  @values;}
                split /@/, $end;
        my $out_line = $start . "##" . join ";",
            map {$_->[0]}
            sort {$a->[1] <=> $b->[1]} @fields
        # on peut  utiliser $outline pour faire ce que l'on veut
    }

La première instruction découpe la ligne. La deuxième construit le tableau @fields réorganisant les données selon les besoins. La troisième construit la ligne de sortie. La particularité ici est que la seconde instruction n'est plus un pipeline linéaire dans lequel les instructions sont enchaînées les unes derrière les autres de façon linéaire, comme tout ce que nous avons vu jusqu'ici, mais que le map extérieur contient lui-même deux splits et un map imbriqués et que ce dernier map contient à son tour un autre split et un autre map imbriqués à un second niveau. On arrive clairement à un niveau de complexité assez difficile à suivre. C'était juste une solution pour le fun, sur un forum, et aussi pour expérimenter si les fonctions de listes s'imbriquaient aisément ; oui, elles s'imbriquent bien et ne se prennent pas les pieds dans le tapis des multiples valeurs de $_ utilisées ici implicitement ou explicitement ; j'admire profondément les auteurs du compilateur Perl qui arrive à gérer un code aussi tordu, mais je ne mettrais certainement pas une construction pareille dans du code de production (je n'ai pas envie d'avoir à maintenir ce genre de choses).

Mais quitte à pousser le bouchon trop loin, une fois que l'on a écrit ce qui précède et que l'on sait que le tableau @fields contient bien la structure de données voulue, on peut se passer de ce tableau et enchaîner les instructions 2 et 3 :

while (my $line = <$FILE_IN>) { 
    my ($start, $end) = split /##/, $line;
    my $out_line = $start . "##" . join ";",
        map {$_->[0]}
        sort {$a->[1] <=> $b->[1]} 
        map { my ($id, @values) = split /;/, $_;
            @values = map { (split /-/, $_)[0]} @values;
            map {[$id, $_]} @values;}
        split /@/, $end;
}

Comme je l'ai déjà dit, je ne recommande pas vraiment des constructions aussi complexes, mais le fait de les avoir testées et d'avoir constaté leur bon fonctionnement me donne une grande confiance dans la capacité de Perl à gérer correctement des situations assez tordues.