Perl Language
Tri

Introduction

Syntaxe

• sort SUBNAME LIST
• sort BLOCK LIST
• trier la liste

Tri Lexique de base

@sorted = sort @list;

@sorted = sort { $a cmp $b } @list;

sub compare { $a cmp $b }
@sorted = sort compare @list;

Les trois exemples ci-dessus font exactement la même chose. Si vous ne fournissez aucune fonction ou bloc de comparaison, sort supposant que vous souhaitez que la liste à sa droite soit triée du point de vue lexical. C'est généralement la forme que vous voulez si vous avez simplement besoin de vos données dans un ordre prévisible et que vous ne vous souciez pas de la correction linguistique.

sort paires d'éléments dans @list à la fonction de comparaison, qui indique le sort élément le plus grand. L'opérateur cmp fait pour les chaînes alors que <=> fait la même chose pour les nombres. Le comparateur est appelé assez souvent, en moyenne n * log ( n ) fois, n étant le nombre d'éléments à trier, il est donc important qu'il soit rapide. C'est la raison pour laquelle le sort utilise des variables globales de package prédéfinies ( $a et $b ) pour passer les éléments à comparer au bloc ou à la fonction, au lieu de paramètres de fonction appropriés.

Si vous use locale , cmp prend en compte l'ordre de classement spécifique à l'environnement local, par exemple, il triera Å comme A sous une langue danoise mais après Z sous une langue anglaise ou allemande. Cependant, il ne prend pas en compte les règles de tri Unicode plus complexes et n'offre aucun contrôle sur la commande - par exemple, les annuaires téléphoniques sont souvent triés différemment des dictionnaires. Pour ces cas, les modules Unicode::Collate et particulièrement Unicode::Collate::Locale sont recommandés.

Numérique Sort

@sorted = sort { $a <=> $b } @list;

En comparant $a et $b à l'opérateur <=> , on s'assure qu'ils sont comparés numériquement et non textuellement selon la valeur par défaut.

Tri inverse

@sorted = sort { $b <=> $a } @list;
@sorted = reverse sort { $a <=> $b } @list;

Le tri des éléments en ordre décroissant peut être réalisé simplement en échangeant $a et $b dans le bloc comparateur. Cependant, certaines personnes préfèrent la clarté d'un reverse séparé, même s'il est légèrement plus lent.

La Transformation Schwartzienne

C'est probablement l'exemple le plus célèbre d'une optimisation de tri utilisant les fonctions de programmation fonctionnelle de Perl, à utiliser lorsque l'ordre de tri des éléments dépend d'une fonction coûteuse.

# What you would usually do
@sorted = sort { slow($a) <=> slow($b) } @list;

# What you do to make it faster
@sorted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ $_, slow($_) ] }
@list;

Le problème avec le premier exemple est que le comparateur est appelé très souvent et continue à recalculer les valeurs en utilisant une fonction lente encore et encore. Un exemple typique serait le tri des noms de fichiers par la taille de leur fichier:

use File::stat;
@sorted = sort { stat($a)->size <=> stat($b)->size } glob "*";

Cela fonctionne, mais au mieux, il subit la surcharge de deux appels système par comparaison, au pire il doit aller au disque, deux fois, pour chaque comparaison, et ce disque peut se trouver dans un serveur de fichiers surchargé de l'autre côté du disque. planète.

Entrez le tour de Randall Schwartz.

La transformation Schwartzian transforme fondamentalement @list en trois fonctions, de bas en haut. La première map transforme chaque entrée en une liste de deux éléments de l'élément d'origine et le résultat de la fonction lente en tant que clé de tri. Nous avons donc appelé slow() une fois pour chaque élément. Le sort suivant peut alors simplement accéder à la clé de tri en consultant la liste. Comme nous ne nous soucions pas des clés de tri mais que nous avons seulement besoin des éléments d'origine dans l'ordre trié, la map finale jette les listes à deux éléments de la liste déjà triée @sort de @sort et renvoie uniquement la liste de leurs premiers membres .

Tri insensible à la casse

La technique traditionnelle pour faire sort cas est de passer des chaînes à lc ou uc pour comparaison:

@sorted = sort { lc($a) cmp lc($b) } @list;

Cela fonctionne sur toutes les versions de Perl 5 et est tout à fait suffisant pour l'anglais; Peu importe si vous utilisez uc ou lc . Cependant, cela pose un problème pour les langues comme le grec ou le turc où il n'y a pas de correspondance 1: 1 entre les lettres majuscules et minuscules, ce qui vous donne des résultats différents selon que vous utilisez uc ou lc . Par conséquent, Perl 5.16 et les versions ultérieures ont une fonction de pliage de cas appelée fc qui évite ce problème, de sorte que le tri multilingue moderne devrait utiliser ceci:

@sorted = sort { fc($a) cmp fc($b) } @list;