Les perles de ce mois-ci ont été rédigées par Philippe "BooK" Bruhat (book@mongueurs.net), de Lyon.pm et Paris.pm.

Merci à Jean-Luc Pinardon d'avoir lancé une discussion au sujet de max() sur la liste perl@mongueurs.net, ce qui m'a conduit à faire des recherches et un comparatif.

La fonction `reduce()`

La fonction reduce() est une notion qui vient de la programmation fonctionnelle, comme map ou grep.

L'idée est assez simple : soit une fonction f() prenant deux paramètres, il s'agit d'appliquer cette fonction à une liste de paramètres. On réduit la liste en appliquant successivement la fonction f() aux deux premiers éléments de la liste et en les remplaçant par le résultat. On continue jusqu'à ce que la liste ne contienne plus qu'un seul élément, le résultat final.

Un exemple concret est celui de la somme, qui généralise l'addition (opération appliquée à deux opérandes) à une liste de plusieurs opérandes.

Dans le cas général, la réduction de la liste (a, b, c, d, e) par la fonction f() serait f( f( f( f( a, b ), c ), d ), e ).

Perl ne dispose pas d'une fonction reduce() en standard (contrairement à Python, par exemple). Heureusement, le module List::Util en propose une, qui s'utilise en passant un bloc de code en premier paramètre, exactement comme la fonction standard sort().

List::Util fait partie de la distribution Scalar-List-Utils, qui contient également Scalar::Util. Ces deux modules font partie de la distribution standard de Perl depuis la version 5.7.3.

Comme List::Util fournit déjà une fonction sum(), nous allons écrire une fonction mul() qui calcule le produit des éléments d'une liste :

    use List::Util qw( reduce );
    sub mul { reduce { $a * $b } @_ }

Tout l'intérêt de la fonction reduce() de List::Util est de pouvoir utiliser les variables globales standard $a et $b, comme avec sort().

En effet, on peut sinon écrire très facilement l'équivalent du code précédent :

    sub mul { my $res = shift; $res = $res * $_ for @_; $res }

Ceci est bien sûr valable quelle que soit la fonction f() que l'on souhaite réduire. Il suffit d'écrire $res = f( $res, $_ ) for @_ dans l'exemple précédent.

Attention tout de même aux effets de bords, en particulier avec l'utilisation de shift(), qui enlève le premier élément de la liste. Dans un contexte plus large qu'une simple fonction de quelques lignes où on manipule @_, il faut faire attention à ne pas modifier le tableau en question (ou au moins savoir qu'on le fait). Ainsi, à la place de :

    my $res = shift @liste;    # ATTENTION, modifie la liste !
    $res = f( $res, $_ ) for @liste;

on préfèrera par exemple écrire :

    my $res = $liste[0];
    $res = f( $res, $_ ) for @liste[ 1 .. $#liste ];

ou toute autre version adaptée à la fonction f() et à l'utilisation que l'on fait du tableau @liste.

Pour information, le module List::Util fournit également les fonctions suivantes :

min LISTE et max LISTE
Le minimum et le maximum d'une liste de nombres.
minstr LISTE et maxstr LISTE
Le minimum et le maximum d'une liste de chaînes de caractères.
first BLOC LISTE
Le premier élément de la liste pour lequel le bloc renvoie une valeur vraie.
sum LISTE
La somme des éléments de la liste, l'exemple classique.
shuffle LISTE
Renvoie les éléments de la liste dans un ordre aléatoire.

Minimum et maximum d'une liste

Perl ne dispose pas non plus des fonctions min() et max() pour obtenir le minimum et le maximum d'une liste.

Sans rentrer dans les détails, on peut dire que c'est probablement parce qu'il existe beaucoup de manières de comparer plusieurs valeurs (en tant que nombres ou en tant que chaînes de caractères, en tenant compte ou non de la localisation, etc.). De plus, de telles fonctions sont finalement assez peu utilisées et en général courtes à coder (comme nous l'avons vu avec reduce()) ; il n'a probablement pas été jugé utile de « gaspiller » un mot-clé pour elles.

C'est pourquoi le jour où on a besoin du maximum ou du minimum d'une liste (et pas de toute la liste triée, auquel cas on utilise sort(), bien sûr), il va nous falloir écrire la fonction nous-mêmes. Dans les exemples qui suivent, nous prendrons pour simplifier le maximum numérique d'un tableau, mais c'est évidemment la même chose quelle que soit la liste à traiter et la fonction de comparaison.

Commençons par la fausse bonne idée :

    sub max { (sort { $a <=> $b } @_)[-1] } # MAUVAIS

Le résultat est juste : on prend le dernier élément d'une liste triée dans l'ordre croissant, c'est-à-dire le maximum. C'est facile à écrire, ça utilise un idiome Perl (indice négatif d'une liste), mais c'est très mauvais en performance : en effet, on trie la liste toute entière pour n'en garder qu'un seul élément.

L'algorithme de tri utilisé par Perl dépend des versions (il y a eu pas mal d'ajouts pour Perl 5.8, en particulier la possibilité avec la pragma sort de choisir l'algorithme de tri utilisé), mais il donne au mieux un résultat en O(n log(n)).

Pour obtenir le maximum d'une liste, on va plutôt utiliser la méthode classique, qui consiste à décréter que le maximum est le premier élément de la liste, puis à parcourir la liste pour mettre à jour sa valeur à chaque fois qu'on rencontre un élément plus grand que le maximum en cours.

    sub max { my $max = shift; $_ > $max and $max = $_ for @_; $max }

Cette méthode est en O(n), c'est à dire que le nombre d'opérations est proportionnel au nombre d'éléments de la liste. On ne peut pas faire mieux algorithmiquement. Plus le nombre n d'éléments de la liste croît, meilleur sera cet algorithme par rapport au précédent.

Nous avons trouvé le meilleur algorithme, est-ce à dire qu'il n'est pas possible de faire mieux ? Bien sûr nous pouvons mieux faire, mais le gain obtenu ne pourra être que de l'ordre d'un facteur multiplicatif.

Ainsi, le module List::Util vu précédemment fournit une fonction max() écrite en C. Sur mon système, celle-ci est environ 3 fois plus rapide que la version Perl présentée ci-dessus. Certes, trouver le maximum d'une liste est d'autant plus long que la liste est grande, mais la fonction max() de List::Util reste toujours à peu près 3 fois plus rapide que la version précédente sur une liste de taille donnée.

À propos de List::Util, nous pourrions nous servir de la version Perl de reduce() présentée dans la perle précédente. La fonction qui donne le maximum de deux éléments, tout le monde la connaît : qui n'a pas vu les sempiternelles macros min et max en C ?

    #define max(a,b) ((a)>(b)?(a):(b))

On pourrait donc écrire une version un peu différente de max(), comme ceci :

    sub max { my $max = shift; $max = $_ > $max ? $_ : $max for @_; $max }

Il va falloir comparer les temps d'exécution de ces fonctions pour estimer les performances des quatre versions de max() dont nous disposons désormais. Nous pouvons d'ores et déjà faire quelques prédictions :

Les versions utilisant l'algorithme en O(n) finiront toujours par être plus rapides que la version en O(n log(n)).
La version C de List::Util sera plus rapide que les versions Perl.
La version Perl utilisant la formule $_ > $max and $max = $_ sera plus rapide que celle utilisant $max = $_ > $max ? $_ : $max. En effet, la première formule fait une comparaison et éventuellement une affection (une fois le maximum trouvé, plus aucune affectation ne sera faite), tandis que la seconde fait à chaque fois une comparaison et une affection, ce qui est nécessairement plus coûteux.

Note : Jérôme Quelin avait déjà fait ces remarques sur l'utilisation de sort() dans le paragraphe Ne pas être plus royaliste que le roi de son article Tris en Perl paru dans Linux Magazine 48.

Nous ferons les comparaisons de performances de ces 4 fonctions dans les perles du mois prochain, et j'en profiterai pour vous présenter le module Benchmark.

Perles de Mongueurs (10)

La fonction `reduce()`

Minimum et maximum d'une liste

À vous !

Perles de Mongueurs (10)

La fonction reduce()

Minimum et maximum d'une liste

À vous !

La fonction `reduce()`