Programmation fonctionnelle en Perl

Partie 1 : Les opérateurs de listes

Laurent Rosenfeld

Ce document est le premier d'une série de tutoriels visant à montrer comment utiliser certaines techniques de la programmation fonctionnelle en Perl et acquérir ainsi une bien meilleure expressivité. Cette première partie aborde en particulier les opérateurs de listes (grep, map, for, sort, etc.) et montre comment il est possible d'enchaîner certains d'entre eux pour former une espèce de « pipeline » dans lequel les données transitent et subissent une série de transformations successives permettant de résoudre simplement et élégamment des problèmes assez complexes.

Une discussion sur ce tutoriel est ouverte sur le forum Perl à l'adresse suivante : Commentez .

- Titre : Programmation fonctionnelle en Perl

- Auteur : Laurent Rosenfeld

- Parution : 8 octobre 2013

- Mise à jour : 3 août 2015

- Public visé :

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2013 Laurent Rosenfeld. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Voir également :

- La programmation fonctionnelle en Perl - Partie 2: les fonctions d'ordre supérieur

- La programmation fonctionnelle en Perl - Partie 3: étendre le langage

- Vidéo: présentation sur la programmation fonctionnelle en Perl, aux Journées Perl 2015, à Paris

Sommaire

- 1. Introduction

- 2. Combiner les opérateurs de listes

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

- 2-2. Retour sur la fonction sort

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

- 2-4. Petite digression sur la question des performances

- 3. Opérateurs de listes et tris de données

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

- 3-2. Trier avec la transformation de Schwartz

- 3-3. La transformation de Guttman Rosler

- 3-4. Transformer une chaîne de caractères en liste de mots avec la fonction split

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

- 3-4-2. Une analyse linguistique rudimentaire

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

- 3-4-4. Analyse de livres entiers

- 4. Quelques autres exemples

- 4-1. Transposition lignes-colonnes

- 4-2. Filtrer les données pour améliorer les performances

- 4-3. Trier un tableau en se basant sur l'ordre de tri d'un autre tableau

- 4-4. Un exemple exagéré ?

- 5. En guise de conclusion de cette partie

- 6. Remerciements

1 - Introduction

Ce tutoriel n'est pas destiné à enseigner la programmation Perl à des débutants, mais à introduire des techniques de programmation Perl relativement avancées qui supposent une assez bonne connaissance et une certaine expérience de la syntaxe de base de Perl. Les fonctions un peu avancées font l'objet de rappels de base permettant la compréhension des techniques employées, mais ne dispensent pas de consulter la documentation officielle.

Dans la préface de son excellent livre Higher Order Perl (HOP), Mark-Jason Dominus remarque que les développeurs Perl tendent à « écrire du code C en Perl » (c'est-à-dire écrire du Perl comme si c'était du C). C'est une honte, ajoute-t-il, car Perl est bien plus expressif que le C. Nous pourrions faire bien mieux et utiliser Perl d'une façon dont les programmeurs C n'oseraient même pas rêver, mais nous ne le faisons pas la plupart du temps.

Perl possède de nombreux concepts et paradigmes avancés empruntés à la programmation fonctionnelle (notamment au langage Lisp) permettant bien souvent d'écrire facilement des programmes bien plus courts, bien plus expressifs, moins bogués et souvent plus lisibles que leurs équivalents en programmation procédurale ou orientée objet. En fait, Perl est sémantiquement bien plus proche du Lisp que du C, même si sa syntaxe de base est plus proche du C.

Je comptais au départ aborder dans ce tutoriel deux sujets principaux que l'on peut considérer comme des emprunts de Perl à Lisp : les « opérateurs de listes » et les « fonctions d'ordre supérieur ». Ce tutoriel s'avérant finalement plus long que prévu initialement, j'ai préféré le scinder en plusieurs parties, les deux sujets principaux pouvant être abordés de façon indépendante. Ce texte est donc le premier d'une série, consacré aux opérateurs de listes.

Cette partie ne traite pas directement des concepts avancés de la programmation fonctionnelle proprement dite, mais elle rejoint cependant une caractéristique de beaucoup de langages fonctionnels, en particulier des différents dialectes de Lisp : la capacité d'appliquer une fonction à une liste ou un tableau, et, éventuellement de retourner une liste modifiée ou même une liste complètement différente.

Perl possède de très nombreux opérateurs de listes (le mot opérateur désigne ici une fonction prédéfinie dans le langage). Certains, bien connus, permettent d'ajouter ou de retirer un (ou plusieurs) élément(s) à un tableau (push, pop, shift, unshift, splice, etc.). Mais ce document s'intéresse surtout aux opérateurs qui permettent d'appliquer une transformation à tous les éléments d'une liste, d'utiliser une liste, de retourner une liste. Parmi ceux-ci, on peut citer map, grep, sort, join, split, print, printf, sprintf, die, exec, kill, system, warn, my, our, state, reverse, chomp, chop, scalar, keys, values, each, chmod, chown, unlink, utime, etc.

Le tableau suivant rappelle rapidement la fonction de ceux qui nous intéresseront le plus dans le présent tutoriel (ce tableau est un résumé très bref et ne constitue en aucun cas une documentation de référence, il convient de lire celle-ci pour les détails précis) :

Fonction ou opérateur

Syntaxe de base

Fonctionnalité

..

1..10

Renvoie une liste des nombres compris entre 1 et 10 (inclus).

join

join expr, liste

Renvoie la chaîne de caractères formée par l'insertion de expr entre les éléments de la liste et la concaténation du résultat.

split

split [motif [,expr]]

Utilise motif pour diviser expr (une chaîne) en une liste de chaînes. On peut également spécifier un nombre limite d'éléments renvoyés en résultat.

print

print [fh] liste

Imprime les éléments de liste. Si le descripteur de fichier fh est omis, imprime généralement sur la sortie standard (à l'écran).

reverse

reverse liste

Renvoie la liste en ordre inverse (en contexte de liste).

sort

sort [sous-routine] liste

Renvoie la liste triée. sous-routine doit renvoyer un nombre inférieur à 0, nul ou supérieur à 0 selon la façon dont deux éléments comparés doivent être ordonnés. Voir le chapitre sur sort.

foreach, for

for var (liste) bloc

Applique bloc à chaque élément de la liste. var (ou par défaut $_) est un alias sur les éléments successifs de la liste, les modifications sont faites sur les éléments de la liste. Voir ci-dessous.

grep

grep bloc liste

Évalue bloc pour chaque élément de la liste et renvoie (en contexte de liste) les éléments pour lesquels bloc a renvoyé vrai. Voir ci-dessous.

map

map bloc liste

Évalue bloc pour chaque élément de la liste et renvoie une liste d'éléments retournés par bloc. Voir ci-dessous.

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 map renvoie 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.

2 - 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 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 ?

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

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

3 - 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 :

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.

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 :

['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

3-4 - Transformer une chaîne de caractères en liste de mots avec la fonction split

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

Pour illustrer les possibilités variées d'utilisation, voici quelques scripts unilignes affichant le résultat du split sous la forme d'une chaîne dans laquelle les éléments de la liste créée par split sont séparés par des tirets :

$ 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é, ...

Il existe même une syntaxe encore plus puissante permettant, en mettant toute le commande split entre parenthèses, d'utiliser le tout comme un tableau dont on peut récupérer directement seulement certains champs :

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

3-4-2 - Une analyse linguistique rudimentaire

Pour illustrer la fonction split sur un pipeline de données, supposons que nous voulions utiliser la phrase utilisée ci-dessus pour une analyse linguistique (je n'ai aucune compétence en la matière, la vision d'une analyse linguistique est certainement et volontairement très rudimentaire). Je désire par exemple : normaliser les données en entrée en éliminant les accents, les signes de ponctuation et les majuscules, et, pour chaque mot, donner son nombre d'occurrences et le trier selon ce critère.

Comme un pipeline de données n'est pas toujours facile à déboguer, il est souvent souhaitable, lorsque les choses se compliquent un peu, de le construire assez progressivement (en commençant par la droite), afin de vérifier que les premières opérations effectuées fournissent le résultat intermédiaire escompté (comme nous l'avons fait précédemment avec les nombres doubles, triples et quadruples).

Commençons par définir une table de hachage pour contenir les mots et leur occurrence et la phrase à utiliser et par supprimer les accents, les ponctuations et les majuscules. Pour ne pas compliquer l'exemple, on ne tiendra compte que des ponctuations et des lettres accentuées existant réellement dans la phrase utilisée, il faudra bien sûr compléter dans un cas réel. De même, dans un cas réel, on pourrait sans doute utiliser d'abord une série d'expressions régulières et autres mécanismes pour normaliser les mots dans la phrase entière, avant de découper en mots. Ici, pour illustrer plus explicitement le thème de cet article, je vais utiliser le split pour éliminer les espaces et les signes de ponctuation, et ne normaliserai les mots qu'ensuite. Le « print join » ne sert qu'à afficher les résultats intermédiaires.

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

Ce qui donne : «Maître-Corbeau-sur-un-arbre-perché-tenait-en-son-bec-un-fromage». La phrase est bien découpée, et le motif de séparation employé a bien permis de se débarrasser des signes de ponctuation et espaces surnuméraires.

Passons aux majuscules et lettres accentuées :

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

On a maintenant : «maitre-corbeau-sur-un-arbre-perche-tenait-en-son-bec-un-fromage».

On peut maintenant remplir la table de hachage %mots :

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

Le module Data::Dumper ou la commande x du débogueur Perl permet de visualiser le hash %mots :

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

Le hash %mots est correct : tous les mots n'apparaissent qu'une seule fois, à l'exception de 'un' qui apparaît deux fois. Il ne me reste plus qu'à trier les éléments du hash par ordre d'occurrence et à afficher le tout. Le sort doit recevoir les clés du hash et les trier selon les valeurs associées. Le tri par défaut étant ascendant, j'ajoute un reverse pour obtenir en premier les mots revenant le plus souvent.

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

Ce qui affiche :

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

Ou, si l'on préfère afficher par ordre alphabétique les mots de même occurrence, on élimine le reverse et trie les occurrences par ordre numérique descendant et les mots de même occurrence par ordre lexicographique ascendant (en utilisant $a et $b dans l'ordre adéquat à chaque situation) :

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

Ce qui donne :

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

Une version à peu près finale du programme permettant de traiter correctement la fable complète de La Fontaine tient en onze lignes, dont seulement deux de code réel, une pour calculer les occurrences et l'autre pour afficher le résultat :

1. #!/usr/bin/perl

2. use strict;

3. use warnings;

5. my %mots;

6. my $texte;

7. {

8. local $/ = undef; # redéfinit localement le séparateur d'enregistrements en entrée

9. $texte = <>; # charge tout dans la variable scalaire $texte

10. }

12. $mots{$_}++ foreach

13. map {$_= lc; tr/àâéèêëîôùûç/aaeeeeiouuc/; $_;}

14. split /[,.:;"?!'\n ]+/, $texte;

16. print map {$mots{$_}, "\t$_\n"}

17. sort {$mots{$b} <=> $mots{$a} || $a cmp $b}

18. keys %mots;

Ce qui donne le début d'histogramme suivant :

Cliquer sur l'icône à droite pour voir l'histogramme

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

Ce miniprogramme fonctionne très bien avec un texte bien plus long que la fable de La Fontaine ci-dessus. En l'appliquant au texte de la Bible (texte intégral, Ancien et Nouveau Testaments, d'une traduction française de Louis Second téléchargée sur Internet), on obtient le début d'histogramme suivant :

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

Comme tous ces mots très courts n'ont sans doute pas beaucoup d'intérêt pour une analyse linguistique (ou historique ou théologique d'ailleurs) du texte, ajoutons un grep pour ne garder que les mots de plus de deux lettres :

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

Utilisée sans argument, la fonction length travaille sur la variable par défaut $_ qui est justement ce que grep utilise comme alias pour les valeurs reçues. Inutile donc de la spécifier.

Ceci donne l'histogramme suivant (limité ci-dessous aux 100 mots les plus fréquents) :

Cliquer sur l'icône à droite pour voir l'histogramme

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

Pour ce texte comprenant environ 32 000 versets et un peu plus de 710 000 mots, le programme prend moins de deux secondes à s'exécuter sur un simple PC portable. À noter que le nouveau grep éliminant les mots de deux lettres ou moins accélère l'exécution d'environ 20 %, ce qui confirme l'intérêt (dans certains cas) de filtrer les données tôt dans le traitement.

Dans un style littéraire un peu différent, voici les 50 mots de plus de deux lettres les plus fréquents du Code pénal français :

Cliquer sur l'icône à droite pour voir l'histogramme

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

Les mots significatifs les plus fréquents sont évidemment différents, mais le type de distribution l'est également. La taille moyenne des mots aussi. Comme nous l'avons dit au début de ce chapitre, l'analyse linguistique proposée ci-dessus est particulièrement rudimentaire, uniquement destinée à montrer quelques possibilités du langage Perl. Nous encourageons le lecteur intéressé par les questions linguistiques à ne pas utiliser les techniques simplistes décrites ci-dessus à titre d'exemple, mais à explorer en particulier le domaine Lingua du CPAN.

4 - Quelques autres exemples

Une fois que l'on commence à maîtriser ce modèle de programmation par flux de données, on lui trouve des applications très fréquentes et variées.

4-1 - Transposition lignes-colonnes

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 » :

1. use strict;

2. use warnings;

4. my @transposed_array;

5. while (<DATA>) {

6. print;

7. my $i;

8. map {$transposed_array[$i++] .= $_;} split;

9. }

10. print join "  ",

11. map {my $count = s/OO/00/g; $count? $count : 0;}

12. @transposed_array;

14. __DATA__

15. A1 A2 A3 A4 A5

16. CC NA OO UV OO

17. NA OO OO OO CP

18. 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

4-2 - Filtrer les données pour améliorer les performances

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.

4-3 - Trier un tableau en se basant sur l'ordre de tri d'un autre tableau

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;

4-4 - Un exemple exagéré ?

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.

5 - En guise de conclusion de cette partie

La programmation consiste bien souvent à réorganiser les données en entrée de façon à pouvoir en extraire facilement les informations utiles. Le modèle de programmation en flux de données proposé par Perl grâce à l'enchaînement des opérateurs de listes est particulièrement expressif et offre une manière extrêmement puissante de réaliser ce genre d'opérations complexes en seulement quelques lignes de code, sans pour autant tomber dans le travers du code illisible. Les trois lignes de code utile d'une transformation de Schwartz en Perl sont finalement bien plus lisibles et faciles à maintenir que les 30 à 50 lignes de code qui seraient nécessaires avec un modèle procédural pur ou un langage orienté objet.

Il ne s'agit en aucun cas de critiquer les modèles procéduraux ou OO, mais seulement de constater qu'il existe de nombreux cas où les outils issus de la programmation fonctionnelle, ou plus précisément d'un langage comme Lisp, sont parfois plus efficaces. Autant les utiliser quand c'est le cas.

Parmi les fonctions que nous avons utilisées, quatre tiennent une place à part parce que l'utilisateur doit définir le code qui leur sera passé pour définir leur comportement, ce qui leur donne toute leur puissance et leur souplesse : for/foreach, grep, map et sort.

La fonction for/foreach est immensément utile (c'est peut-être la plus fréquemment utilisée des quatre), mais elle est un petit peu à part (dans l'optique du présent document), dans la mesure où elle s'intègre un peu moins facilement dans un pipeline de données parce qu'elle ne renvoie pas une liste de données comme les autres.

La fonction grep est de même très utile et très pratique d'utilisation, mais on peut la considérer comme du « sucre syntaxique » dans la mesure où l'on peut aisément la simuler avec un map. Par exemple, l'instruction suivante :

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

peut s'écrire également :

my @impairs = map {$_ % 2 ? $_ : ()} 1..20;

(À noter cependant que la version grep est sans doute un peu plus rapide que map dans un tel cas (environ 20 % dans nos essais très succincts). À la vérité, on peut aussi trouver moyen de simuler map avec un grep, mais c'est moins naturel et il peut y avoir des effets de bord indésirables.)

Les fonctions for (et foreach), map, sort et grep de Perl ont cette particularité qu'on leur passe une fonction ou un bloc de code en argument. Ce sont des fonctions qui acceptent une fonction comme paramètre. Quand une fonction peut être le paramètre ou la valeur de retour d'une autre fonction, on parle de fonctions d'ordre supérieur (ou parfois de fonctions première classe). Cela offre une expressivité très largement supérieure aux modèles de programmation plus traditionnels. Par exemple, la puissance de la fonction sort provient en partie du fait qu'elle met en œuvre un (ou plusieurs) algorithme(s) de tri très efficace(s), mais surtout du fait que son utilisateur peut définir à sa guise dans un bloc de code la fonction de comparaison des données qui déterminera dans quel ordre la fonction sort doit classer les données à trier, comme nous en avons vu plusieurs exemples. De même, les fonctions map et grep ne font finalement que quelque chose de très simple : elles prennent en entrée une liste de données, appliquent à chacune de ces données un bloc de code et renvoient une liste de données modifiées par ce bloc de code. On peut dire que map et grep sont des fonctions génériques abstraites effectuant une simple opération technique, tout le contenu sémantique ou fonctionnel de ce qu'elles font se trouve dans le bloc de code défini par l'utilisateur.

L'article suivant de cette série (La programmation fonctionnelle en Perl ‒ Partie 2: les fonctions d'ordre supérieur) montre comment Perl permet de construire à la demande et d'utiliser ce genre de fonctions d'ordre supérieur pour réaliser quantité d'autres choses très puissantes qui ne viendraient même pas à l'idée d'un programmeur C classique. C'est dans ce sens que Perl peut être considéré comme un langage offrant la plupart des concepts des langages fonctionnels. Nous montrerons notamment dans le troisième volet de cette série (La programmation fonctionnelle en Perl - Partie 3 ; étendre le langage) comment construire en quelques lignes de Perl pur une fonction simulant la fonction interne map (ou grep ou même sort) de Perl (d'ailleurs, nous incitons le lecteur qui ne comprendrait toujours pas parfaitement la fonction map à aller voir cette implémentation Perl de map, elle pourra l'aider à comprendre son fonctionnement). Ou encore de réaliser, toujours en quelques lignes de code, des fonctions « pipeline » classiques de la programmation fonctionnelle et inexistantes dans le Perl de base (mais souvent implémentées dans des modules standard), comme reduce ou combine. Ou encore, comment faire des fonctions qui fabriquent dynamiquement d'autres fonctions, et toutes sortes d'autres choses très utiles que nous ne pouvons décrire pour l'instant.

6 - Remerciements

Merci à Djibril et à Philou67430 pour leur relecture et leurs conseils avisés dans l'amélioration de ce tutoriel.

Merci à Claude Leloup et à Phanloga pour leur relecture orthographique attentive.