La fonction sort

Perl dispose en interne d'une fonction de tri, la bien nommée sort. Appelée sur une liste, elle va renvoyer une liste triée :

    @lettres = qw( a z e r t y );
    @out = sort @lettres;
    # @out vaut maintenant (a,e,r,t,y,z)

L'ordre de tri utilisé est l'ordre lexicographique ascendant (en d'autres termes, l'ordre des caractères dans la table ASCII).

La fonction sort de Perl est très rapide, car elle utilise un algorithme de tri évolué et est écrite complètement en C.

Par contre, la fonction sort ne sait manipuler que des listes tenant entièrement en mémoire (vive ou swap). Cela exclut donc les tris sur d'énormes fichiers nécessitant des fichiers temporaires. De plus, la liste n'est pas triée sur place, comme dans d'autres langages : la fonction sort produit une nouvelle liste.

Tris étendus

Tris personnalisés

Tant que l'on veut trier selon l'ordre ASCIIbétique, la fonction sort convient à nos besoins. Mais si on veut trier selon l'ordre numérique (car (1,2,10) se trie en (1,10,2) suivant l'ordre lexicographique), ou même selon un ordre totalement arbitraire (comme le nombre de « e » dans un mot par exemple), alors il faut utiliser une fonction de tri personnalisée.

Heureusement, Perl propose un moyen standard de réutiliser la fonction sort (ce qui est une forme de Paresse, l'une des trois vertus du programmeur), qui est déjà optimisée. Ce moyen consiste à passer à sort le nom d'une fonction de comparaison. Laquelle fonction reçoit deux arguments et doit renvoyer un nombre positif, négatif ou nul selon que le premier argument est supérieur, inférieur ou égal au second. Pour des raisons d'efficacité, les arguments ne sont pas passés comme dans une fonction normale, mais comme des alias sur les arguments à comparer, nommés respectivement $a et $b. Votre fonction personnalisée doit donc comparer $a et $b, et renvoyer -1, 0 ou 1 selon que $a est inférieur, égal ou supérieur à $b. C'est le cas des opérateurs prédéfinis <=> et cmp.

Voici par exemple comment trier numériquement une liste :

Un mot sur la rapidité

Notez cependant qu'utiliser un bloc anonyme ou une fonction de comparaison ralentit la fonction sort. En effet, la fonction sort seule n'exécute que du code C, alors que la fonction sort accompagnée d'un bloc de comparaison oblige à appeler du code Perl, moins rapide. Il faut donc privilégier les fonctions internes de Perl pour une efficacité accrue.

    @out = sort @in;               # tri lexicographique
    @out = sort { $a cmp $b } @in; # même chose, explicite

Bien que ces deux instructions fassent la même chose, la version explicite prend environ le double de temps que la version par défaut. De même, si on veut trier selon un ordre lexicographique descendant, il vaut mieux utiliser la combinaison sort + reverse (la fonction reverse ne faisant que déplacer des pointeurs, elle est très rapide).

    @out = reverse sort @in;       # tri lexicographique descendant
    @out = sort { $b <=> $a } @in; # même chose, explicite

Ici encore, du fait du très faible surcoût de la fonction reverse, le temps de traitement de la version reverse est quasiment la moitié de celui de la version explicite.

Tris complexes

Comme la liste à trier peut contenir n'importe quelles données, y compris des références (cf article 5 de l'introduction à Perl - numéro 45), rien ne nous empêche d'interpréter les valeurs comme nous le voulons :

    @out = sort { $a->[0] <=> $b->[0] } @in;

Ici, nous trions une liste de listes sur le premier champ de chacune de ces listes.

Si la liste à trier contenait des objets de type Employe disposant d'une méthode salaire par exemple, nous aurions pu trier la liste des employés par leur salaire de cette façon :

    @out = sort { $b->salaire <=> $a->salaire } @employes;
    # on affiche les gros salaires d'abord

Voici enfin comment trier des lignes de fichiers passwd selon leur uid :

    @out = sort {
        (split ':', $a, 4)[2] <=>
        (split ':', $b, 4)[2]
    } @pw_lines;

Bref, seule votre imagination limite ce que vous pouvez trier, comme pour beaucoup d'autres choses en Perl...

Tris multiples

Ce modèle peut d'ailleurs être très facilement étendu si vous voulez trier sur différents paramètres. Pour cela, nous allons utiliser l'opérateur ||, qui a la particularité intéressante de renvoyer la première valeur vraie parmi ses opérandes (contrairement en C où les valeurs sont booléanisées) et de court-circuiter les autres.

Ainsi, l'expression :

    $foo || $bar

va renvoyer $foo si $foo est vrai, sinon $bar. Et nous pouvons facilement enchaîner :

    $foo || $bar || $baz

qui renverra la première valeur vraie (c'est-à-dire non nulle) entre $foo, $bar et $baz.

Revenons à nos moutons. Si nous reprenons l'exemple consistant à trier les mots selon le nombre de « e », puis sur l'ordre alphabétique, nous allons utiliser la formule suivante :

    @out = sort { $a =~ y/e// <=> $b =~ y/e// || 
                  $a cmp $b } @mots;

(la fonction y, ou tr, utilisée sans complément, compte le nombre d'occurrences des caractères précisés).

Bon, je pense que vous avez compris, et nous pouvons donc passer à des sujets un peu plus retors.

La Manœuvre Or-cache

Tout cela est bel et bon, mais les lecteurs avertis auront tout de suite remarqué que nous recalculons lors de chaque test la clef de tri, c'est à dire la valeur associée à la clef et sur laquelle le tri va réellement se faire. Par exemple, dans le cas où nous trions les noms de fichiers selon leur date de dernière modification, nous accédons au système de fichiers chaque fois que nous voulons comparer deux valeurs entre elles. Et comme chaque valeur est typiquement comparée plusieurs fois avec d'autres valeurs, nous allons chercher plusieurs la fois la même information dans le système de fichiers. De même, l'exemple triant les lignes de fichier passwd selon leur uid doit refaire deux split à chaque comparaison, ce qui est extrêmement inefficace et antiperformant.

Pour remédier à cela, nous allons donc passer par une phase de prétraitement des données, consistant à mettre dans un cache les clefs de tri. La fonction de comparaison ne cherchera plus les informations directement, mais utilisera le cache.

Une clef de tri étant associée à une valeur particulière, nous pensons immédiatement à un tableau associatif (ou hash).

Donc, pour reprendre notre exemple de date de modification :

    $cache{$_} = -M for @fichiers;
    @out = sort { $cache{$a} <=> $cache{$b} } @fichiers;

(la première ligne crée une table de hachage dont les clefs sont les noms de fichiers contenus dans la variable tableau @fichiers et dont la valeur associée est la date de modification du fichier)

Nous avons donc remplacé de longs calculs compliqués dans la fonction de comparaison par une rapide consultation de hash.

Nous pouvons même optimiser notre mise en cache, en pré-allouant notre hash et en utilisant une tranche de hash :

    keys my %cache = @fichiers;
    @cache{@fichiers} = map { -M } @fichiers;

Ici, la première ligne crée directement une table de hachage dont les clefs sont les noms de fichiers contenus dans la variable @fichiers (l'opérateur keys est utilisé ici en 'lvalue', c'est-à-dire à gauche du signe d'affectation). La seconde ligne affecte les valeurs à ces clefs (via une tranche de hash). On gagne ainsi en vitesse car notre hash n'alloue de la mémoire qu'une seule fois, au lieu de l'allouer au fur et à mesure de ses besoins lorsqu'on ajoute de nouvelles clefs.

Et si nous voulons effectuer un tri multi-critères, il suffit de créer autant de hashs de cache qu'il y a de valeurs à comparer :

    keys my %cache1 = keys my %cache2 = @mots;
    @cache1{@mots}  = map { y/e// } @mots;
    @cache2{@mots}  = map { y/a// } @mots;
    @out = sort { $cache1{$a} <=> $cache1{$b} ||
                  $cache2{$a} <=> $cache2{$b} } @mots;

Nous venons juste de trier nos mots selon le nombre de « e », puis selon le nombre de « a ».

Attention tout de même à ne pas tomber dans le piège consistant à mettre en cache des données qui sont plus rapides à retrouver qu'une consultation de hash. Par exemple, il est inutile de mettre en cache le nom lui-même :

    keys my %cache = @mots;
    @cache{@mots} = map { y/e// } @mots;
    @out = sort { $cache{$a} <=> $cache{$b} ||
                  $a cmp $b # $a et $b servent de clef de tri
                } @mots;

De même, de nombreuses fonctions internes de perl sont très rapides et ne nécessitent pas de mise en cache : lc, uc, substr par exemple (et bien d'autres) peuvent être plus rapides qu'une consultation de hash.

Cette approche a tout de même un inconvénient : elle impose de lire les données deux fois, une fois pour la mise en cache et une fois lors du tri proprement dit. Ce comportement peut être gênant, si les données sont lues depuis un fichier par exemple.

La Manœuvre Or-cache (Orcish Maneuver en VO) résout ce problème en éliminant la phase de pré-traitement, tout en n'effectuant l'extraction de la clef de tri qu'une fois par valeur. Le test et le stockage des clefs de tri est effectué par l'opérateur ||= (affectation ou-logique avec court-circuit), qui évalue et assigne l'expression de droite à la lvalue de gauche, si ladite lvalue est fausse. Notre code devient donc :

    keys my %cache = @fichiers;  # optimisation toujours valable
    @out = sort { 
        ( $cache{$a} ||= -M $a ) # extraction si nécessaire
                 <=>             # comparaison numérique
        ( $cache{$b} ||= -M $b ) # extraction si nécessaire
    } @fichiers;

La première partie de la fonction de tri vérifie si la clef de tri de $a est en cache. Si ce n'est pas le cas, elle extrait la valeur de la clef de tri de l'opérande et la met en cache. La clef de tri de $a est alors comparée à la clef de tri de $b (qui est retrouvée exactement de la même manière).

Les tris multicritères se font en utilisant, là encore, plusieurs hashs de cache.

La Manœuvre Or-cache a cependant quelques défauts. Un test supplémentaire est nécessaire afin de rechercher les valeurs des clefs de tri depuis le cache. De plus, si une clef de tri a une valeur fausse, elle sera recalculée à chaque fois. Ceci n'est généralement pas un problème, car les clefs de tri extraites sont rarement fausses, comme dans le cas de -M $fichier. Dans le cas du nombre de « e » dans les mots à trier, une simple astuce permet d'éluder le problème du zéro : il suffit de trier par le nombre de « e » plus 1. Cependant, sauf quand il faut absolument éviter de lire les données deux fois, la méthode de tri avec cache explicite est toujours un peu plus rapide que la Manœuvre Or-cache.

La Transformée Schwartzienne

Une manœuvre plus efficace de mettre en cache les clefs de tri, sans utiliser de variables temporaires nommées, fut popularisée par le très célèbre Randal L. Schwartz, et fut surnommée Transformée Schwartzienne (Schwartzian Transform en VO).

L'invention majeure de la Transformée Schwartzienne est d'utiliser des tableaux anonymes pour conserver l'enregistrement et sa clef de tri. Les clefs de tri sont extraites une fois, durant une phase de prétraitement des données de la liste à trier.

    @out =
        map  { $_->[0] }
        sort { $a->[1] cmp $b->[1] }
        map  { [ $_, -M ] } @fichiers;

Reprenons ce code plus en détails. Pour le comprendre, il faut le lire de bas en haut. La dernière ligne :

        map { [ $_, -M ] } @fichiers

crée une liste temporaire de références symboliques vers des couples (fichier, date). L'élément fichier d'un couple (obtenu par $_) est un élément de @fichiers, tandis que l'élément date (obtenue par -M, opérateur unaire appliqué à $_ par défaut) est sa date de dernière modification.

Cette liste de paires de valeurs est ensuite triée par l'instruction sort. Sa fonction de tri :

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

compare les seconds éléments ($a->[1] et $b->[1]) de chaque couple. Le tri se fait donc bien par rapport aux dates.

L'instruction map de la première ligne :

        map { $_->[0] }

n'a plus qu'à extraire de cette nouvelle liste triée les noms de fichiers. Il s'agit des premiers éléments (d'où le $_->[0]) de chaque couple. Ainsi le tableau @out reçoit-il une liste de noms de fichiers triés.

La Transformée Schwartzienne ne trie pas en fait les données réelles. Elle trie les références à des tableaux anonymes contenant l'enregistrement et les clefs de tris. Nous devons donc effectuer un post-traitement pour retrouver les éléments triés depuis les tableaux anonymes.

Utiliser la Transformée Schwartzienne pour un tri multi-critères est simple. Il suffit de sauvegarder chaque clef de tri secondaire dans l'élément suivant du tableau anonyme. Dans la fonction de tri, il suffit de faire un || entre les différentes comparaisons des clefs de tri secondaires, comme dans les tris standards ou la Manœuvre Or-cache.

    @out =
        map  { $_->[0] }
        sort { $a->[1] <=> $b->[1] || # nombre de e
               $a->[2] <=> $b->[2] || # nombre de a
               $a->[0] cmp $b->[0] }  # tri lexicographique
        map  { [ $_, y/e//, y/a// ] } @mots;

Retour au tri interne

Les techniques de tri avancé décrites auparavant sauvegardent les opérandes à trier avec leurs clefs de tri (dans les tris avec clefs mises en cache, les opérandes sont les clefs d'un hash et les clefs de tri sont les valeurs du hash ; dans la Transformée Schwartzienne, les opérandes sont les premiers éléments des tableaux anonymes, et les clefs de tri sont les autres éléments des tableaux). Nous allons maintenant étendre cette idée pour sauver les opérandes à trier avec leurs clefs de tris sous forme de chaînes d'octets, en utilisant la concaténation. Ceci nous permettra d'utiliser la fonction sort sans fonction de comparaison, ce qui est plus rapide comme nous l'avons vu précédemment.

Cette optimisation peu connue améliore la Transformée Schwartzienne en éliminant la fonction de tri et en s'appuyant donc sur le tri lexicographique par défaut, qui est très rapide.

Cette méthode a été étudiée par Uri Guttman et Larry Rosler dans un article, A Fresh Look at Efficient Perl Sorting, dont vous trouverez les références à la fin de l'article.

Afin d'accomplir ceci, nous allons modifier la Transformée Schwartzienne en remplaçant le tableau anonyme par des chaînes d'octets. Nous packons donc les clefs dans des chaînes simples. Les clefs secondaires sont simplement concaténées, convenablement délimitées si nécessaire. Nous y adjoignons ensuite l'opérande à trier.

Il nous suffit alors de trier lexicographiquement ces chaînes, et nous retrouvons finalement les opérandes à la fin des chaînes.

On peut retrouver l'opérande grâce à un appel à substr ou via d'autres méthodes, selon la préférence de l'utilisateur.

Pour classer une liste de mots suivant leur quatrième lettre, puis leur deuxième lettre, nous utiliserons donc le code suivant :

    @out =
        map { substr $_, 2 }
        sort
        map { substr($_, 3, 1) . # quatrième lettre
              substr($_, 1, 1) . # deuxième lettre
              $_ }               # mot entier
        @in;

Remarquez que la fonction sort est appelée sans code de comparaison, et est de ce fait extrêmement rapide.

Cette optimisation est très facile à réaliser si les clefs de tri sont elles-mêmes des chaînes. Dans le cas où ce sont des nombres, le mieux est d'utiliser le module Sort::Records qui implémente cette méthode sur toutes sortes de données : chaînes de longueur fixe, de longueur variable, entiers, réels, signés, non signés, etc.

Ne pas être plus royaliste que le roi

Voilà, vous en savez maintenant (je l'espère) beaucoup plus sur les tris en Perl. Mais ce n'est pas pour autant qu'il faut utiliser des tris de partout, sans discrimination.

Par exemple, il n'est pas rare de voir les débutants utiliser le bout de code suivant pour trouver le plus petit et le plus grand des éléments d'une liste :

    my ($min, $max) = (sort @tab)[0, -1]

Quelle perte de temps ! La complexité est loin d'être linéaire (elle dépend de l'algorithme de tri utilisé, et peut même aller jusqu'à être quadratique).

Il vaut mieux analyser une seule fois la liste en modifiant le minimum et le maximum si besoin :

    my ($min,$max) = ($tab[0]) x 2; # init. sinon warnings
    foreach ( @tab ) {
        $min = $_ if $_ < $min;
        $max = $_ if $_ > $max;
    }

Ici la complexité est linéaire selon la taille du tableau. Si on ne veut qu'une seule de ces deux valeurs, on peut utiliser la construction plus idiomatique :

    my $max = $tab[0];
    $_ > $max and $max = $_ for @tab;

Et même encore mieux, le module List::Util fournit la fonction max :

    use List::Util qw( max );
    my $max = max @tab;

Bref, les tris ont de l'intérêt, mais pas partout. Saisissez cette occasion de faire fonctionner votre cerveau ! :-)

Références

Pour plus de détails, je vous invite à regarder :

Auteur

Jérôme Quelin <jquelin@mongueurs.net>