Un nouveau regard sur Perl et les tris

Les tris peuvent être un goulot d'étranglement dans les programmes Perl. Les performances peuvent varier de plusieurs ordres de grandeur, selon la manière dont le tri est réalisé.

Dans ce document, nous examinerons en détails la fonction interne sort et verrons comment lui conserver de bonnes performances avec des données aussi bien simples que complexes. Nous analyserons ensuite et comparerons plusieurs idiotismes perliens bien connus (tels que la manoeuvre Or-cache et la transformée Schwartzienne). Puis nous montrerons comment améliorer leurs performances en pack-ant leurs clefs de tri dans une seule chaîne. Enfin, nous présenterons une nouvelle approche utilisant la fonction sort avec des clefs packées et sans fonction externe de tri. Cette approche surclasse toutes les autres question performances, et est facile à implémenter soit directement, soit en utilisant un module créé dans ce but, Sort::Records.

Qu'est-ce qu'un tri, et pourquoi trier ?

Trier, c'est réorganiser une liste selon un ordre défini par une séquence croissante (ou décroissante) monotone de clefs de tri, où chaque clef de tri est obtenue en appliquant une fonction à l'élément correspondant de la liste. Nous utiliserons le terme clef de tri pour éviter les confusions avec les clefs d'un hash.

Un tri réarrange une liste afin de faciliter d'autres traitements tels que la recherche d'un élément particulier. Les tris servent aussi pour faciliter la lecture aux humains ; ils permettent aussi de mieux embrasser les données et de localiser une donnée.

Les tris sont utilisés dans de nombreux types de programmes et sur toutes sortes de données. C'est une opération si banale et en même temps si complexe à mettre en oeuvre de manière efficace, que les algorithmes de tris et la création d'implémentations optimales constituent une branche importante de l'informatique.

Cet article traite de la manière de créer des tris efficaces en Perl. Nous commencerons avec un bref aperçu des tris (y compris la théorie des algorithmes de base et leur efficacité respective), le traitement des clefs de tris et les tris externes à perl. Nous décrirons ensuite la fonction sort [1] ainsi que son utilisation dans les cas triviaux. Nous traiterons ensuite des clefs de tris complexes, qui posent la question de l'optimisation de leur traitement. Enfin nous introduirons une méthode qui déplace le traitement des clefs de tris en dehors de la fonction sort, ce qui est la méthode de tri la plus efficace en Perl. Nous présenterons un module qui implémente cette technique de tri et fournit de puissantes méthodes pour l'extraction de clefs de tri (le traitement des données afin de produire les clefs de tri).

Algorithmes et théorie des tris

Une discussion complète sur la théorie et les algorithmes de tris dépasse le cadre de cet article. Cette section donnera juste ce qu'il faut de théorie et terminologie pour expliquer les méthodes de comparaison des techniques de tri.

La complexité d'un algorithme est la mesure des ressources nécessaires pour exécuter ledit algorithme -- typiquement, il y a une opération critique qu'il faut exécuter un certain nombre de fois. Une partie de la théorie des algorithmes consiste à trouver quelle opération est le facteur limitant, puis à formuler une fonction qui décrit le nombre de fois que cette opération est exécutée. Cette fonction de complexité est communément écrite avec la notation grand-O -- O(f(N)) -- où O est lu ordre de et f(N) est une fonction de N, la taille des données en entrée.

Les comparaisons O(f(N)) ont quelques propriétés inhabituelles. La taille réelle de N importe généralement peu pour l'algorithme, mais son influence sur le comportement de f(N) est déterminante. Si l'ordre d'un algorithme est O(N*log(N) + N), l'effet de N sur la valeur de la fonction est négligeable par rapport à N*log(N) quand N est suffisamment grand. Et l'ordre de cet algorithme sera donc O(N*log(N). Quelquefois, la fonction calculée pour l'ordre d'un algorithme est un polynôme de N, mais dans ce cas on ne prend en considération que le terme de plus haute puissance, et le coefficient de cette puissance n'est pas montré. De même, si deux algorithmes ont le même ordre mais que l'un effectue plus de travail à chaque opération, ils sont tout de même équivalents en terme d'ordre, même s'il peut y avoir une différence importante de vitesse lors de leur application. Ce dernier point est essentiel dans les techniques que nous montrerons pour optimiser les tris en Perl qui ont tous la même fonction grand-O, O(N*log(N)).

Voici quelques algorithmes connus et leur fonction d'ordre (adapté de [2]) :

    Notation     Nom              Exemple

    O(1)         constant         index de tableau ou de hash
    O(log(N))    logarithmique    recherche dichotomique
    O(N)         linéaire         comparaison de chaînes
    O(N*log(N))  n log n          tri avancé
    O(N**2)      quadratique      tri simple
    O(N**3)      cubique          multiplication de matrices
    O(2**N)      exponentiel      partionnement d'ensemble

L'opération élémentaire dans un tri consiste à déterminer dans quel ordre mettre deux données en entrées. La comparaison peut être aussi simple que trouver si deux nombres sont égaux ou trouver lequel est le plus grand (ou l'opération similaire sur les chaînes), ou elle peut être complexe.

Les algorithmes de tris simples (tri bulle ou tri par insertion) comparent chaque élément avec tous les autres, donc leur complexité est O(N**2). Même avec l'optimisation du triangle ($x est égal à $x, et $x comparé à $y est l'opposé de $y comparé à $x), qui réduit la fonction à O((N*(N-1))/2), la complexité reste O(N**2) ainsi qu'expliqué ci-dessus.

Mais ces algorithmes ont leur utilité. Quand N est petit, ils peuvent être plus rapides que les autres méthodes, car les complexités ajoutées de O(1) et O(N) des tris avancés peuvent dépasser le comportement en O(N**2) des tris simples. « Les algorithmes complexes sont lents pour les petites valeurs de N, et N est généralement petit. Les algorithmes complexes ont de grandes constantes. » [3]. Les cas réellement importants surviennent avec des valeurs élevées de N.

Les méthodes de tri avancé partitionnent les enregistrements à trier en ensembles plus petits, afin de réduire le nombre de comparaisons nécessaires. Leur complexité est O(N*log(N)), fournissant un gain réellement important pour les valeurs de N suffisamment grandes. Ces algorithmes incluent le tri arborescent, le tri Shell et le quicksort. [4]

Quelques algorithmes de tri spécialisés (tels la méthode de tri digital ou radix sort) travaillent en comparant des parties de clefs de tri numériques et peuvent obtenir une complexité linéaire (O(N)) [5]. Ces méthodes cependant ne peuvent servir dans tous les cas, et nous ne les étudierons donc pas.

Une propriété des algorithmes de tri est leur stabilité. Un tri stable préserve l'ordre relatif dans les données triées de deux éléments égaux (en terme de tri). Certains problèmes mettant en oeuvre des tris requièrent la stabilité. Les algorithmes de tri simples sont généralement stables, les algorithmes avancés ne le sont pas. Nous montrerons comment créer des tris stables en Perl.

Quand les données originelles ne peuvent être facilement déplacées par l'algorithme de tri, il faut trier leur index et ensuite utiliser les index triés pour créer une liste d'éléments triés. Certains opérateurs de tri dans les autres langages (et on pense ici à APL) renvoient simplement des index triés, et c'est à l'utilisateur de les utiliser correctement. Nous montrerons comment créer un tri d'index efficace en Perl et les endroits où il est utile de procéder ainsi.

Clefs de tri

Dans le cas d'un tri scalaire sur les éléments (avec une comparaison s'effectuant sur l'élément en entier), la clef de tri est tout simplement l'élément. Plus généralement, la clef de tri est basée sur certaines propriétés fonctions de tout ou partie de l'élément. De telles sous-clefs peuvent être extraites de propriétés internes de l'élément (champs d'un enregistrement) ou dérivée de propriétés externes de l'élément telles que la date de modification d'un fichier dont le nom est l'élément lui-même, ce qui est coûteux à rechercher depuis le système de fichiers.

Afin d'éviter de répéter le calcul des clefs de tris, le tri doit retenir les associations entre les enregistrements et leur clef de tri extraite ou dérivée. La théorie et les algorithmes de tri ignorent généralement le coût de cette association, mais il est un facteur constant de l'opération de comparaison. Nous verrons par la suite que dans les cas réels, supprimer ce surcoût ou le réduire de O(N*log(N)) à O(N) apporte un gain de temps appréciable, surtout lorsque N augmente.

Les clefs de tri complexes peuvent augmenter énormément le surcoût de chaque comparaison. En particulier quand on effectue un sous-tri sur des sous-clefs. Extraire et comparer des clefs de tri complexes peut être coûteux.

Aucune implémentation d'un algorithme de tri universel ne peut supporter l'extraction et la comparaison de différents types de clefs de tri de manière efficace. Et donc, la plupart des implémentations fournissent une interface permettant d'appeler une fonction de tri -- une fonction de comparaison personnelle à laquelle on passe deux opérandes. Ces opérandes peuvent être les enregistrement eux-mêmes, des références ou les index de ces enregistrements. La comparaison renvoie une valeur négative, positive ou nulle selon l'ordre relatif des clefs de tri des deux enregistrements. Le programmeur est responsable du pré-traitement des enregistrements afin de générer les clefs de tri, ainsi que du post-traitement pour retrouver les données originales. Cette fonction générique de tri s'occupe juste des comparaisons et de remettre les opérandes dans le bon ordre.

Comme la fonction interne de tri de Perl a un ordre de O(N*log(N)), l'efficacité d'un tri proviendra de l'optimisation de l'extraction et de la comparaison de clefs de tri. Cet article traite principalement des méthodes permettant de rendre l'extraction et la comparaison aussi efficace que possible.

Tri externe

Tout système d'exploitation digne de ce nom propose un utilitaire de tri. Les différents Unix/POSIX proposent typiquement une commande sort à la fois rapide et souple pour l'extraction de clefs de tri à partir de fichiers texte. Il peut être plus facile à coder et plus efficace d'utiliser cette commande en lieu et place de la fonction de tri de Perl, même en considérant le surcoût dû au transfert des données dans et depuis le second processus.

De nombreux fournisseurs vendent des extensions commerciales de tri hautement optimisées, profitant de décennies d'optimisations et pouvant gérer de gros volumes de données. Mais ces extensions sont chères et généralement mal adaptées à un usage depuis un programme Perl.

Ces tris externes sont capables de gérer efficacement de gros volumes de données, en utilisant des médias externes tels que disques ou bandes magnétiques comme moyen de stockage intermédiaire si nécessaire. Au contraire de Perl, qui requiert que la liste entière des opérandes soit en mémoire (vive ou -- bien que plus coûteux en terme de rapidité -- virtuelle) en même temps. Perl n'est donc pas l'outil idéal pour les énormes tris (avec « énorme » défini par les limites de votre système en termes de mémoire), nous les négligerons donc par la suite.

Tri en Perl

La fonction interne de tri de Perl utilise une implémentation de l'algorithme quicksort similaire (mais plus robuste) à la fonction qsort de la bibliothèque ANSI/ISO Standard C [6]. Dans sa forme la plus simple, sort ne requiert aucune fonction de tri :

    @out = sort @in;

Par défaut, le tri est effectué en respectant un ordre lexicographique ascendant, utilisant de manière efficace comme opération de comparaison la fonction C memcmp (qui compare simplement des séquences d'octets non signés). Si une locale est spécifiée, il utilise à la place la fonction C plus compliquée (et plus lente) strcoll.

Si vous voulez un autre ordre que celui-ci, vous devez fournir une fonction de comparaison personnalisée. La fonction de comparaison peut être spécifiée soit comme un bloc de code, soit comme le nom d'une routine, ou comme un typeglob référant une routine. Dans Perl 5.6, une variable scalaire contenant une référence sur du code peut aussi être utilisée pour spécifier la fonction de comparaison.

Afin d'optimiser l'appel de la fonction de comparaison, Perl saute le passage d'arguments classique via @_, et utilise à la place une méthode spéciale et plus efficace. A l'intérieur de la fonction de tri, les variables de package $a et $b sont des alias sur les deux opérandes à comparer. La fonction de tri doit renvoyer un nombre inférieur, égal ou supérieur à zéro selon le résultat de la comparaison entre les clefs de tri $a et $b. Les variables $a et $b ne doivent en aucun cas être modifiées, sinon l'algorithme de tri a de fortes chances de renvoyer n'importe quoi.

Même le tri personnalisé le plus simple sera moins efficace en Perl que d'utiliser la comparaison par défaut. Le tri interne n'utilise que du code C dans le binaire perl, alors que n'importe quelle fonction de comparaison doit exécuter du code Perl. Une optimisation bien connue consiste à minimaliser le code Perl exécuté afin d'essayer de rester dans le binaire perl autant que possible. Nous étudierons par la suite plusieurs techniques permettant de réduire le code Perl exécuté.

Le but premier de cet article est d'effectuer de nombreux tests en utilisant la fonction de tri interne de Perl. Voici comment un tri lexicographique ascendant utilisant une fonction de tri personnalisée :

    @out = sort { $a cmp $b } @in;

Pour une comparaison, reportez-vous aux lignes "Défaut" et "Explicite" dans le test de performances A1 de l'annexe A. La méthode par défaut est environ deux fois plus rapide que la méthode explicite.

Tris triviaux

Nous appelons tris triviaux les tris utilisant comme clef de tri tout ou partie de l'enregistrement, et effectuant un traitement minimum de l'enregistrement. Pour effectuer en Perl des tris triviaux autrement que lexicographiques ascendants, il suffit de créer la fonction de tri correspondante. Voici quelques exemples simples mais utiles de fonctions de comparaison.

L'exemple le plus simple est le tri numérique ascendant, qui utilise le bien nommé opérateur vaisseau spatial :

    @out = sort { $a <=> $b } @in;

Un tri numérique est requis car l'ordre lexicographique de la liste (1, 10, 2) ne correspond pas à son ordre numérique (1, 2, 10).

Si vous voulez trier en ordre descendant, vous pouvez utiliser trois techniques. La pire est d'inverser le résultat de la comparaison dans la fonction de comparaison. Inverser l'ordre de comparaison en échangeant $a et $b est beaucoup plus avantageux : cette implémentation sera aussi rapide que le tri correspondant ascendant.

    # tri numérique descendant.
    @out = sort { $b <=> $a } @in;
    # tri lexicographique descendant.
    @out = sort { $b cmp $a } @in;

La meilleure méthode est d'utiliser la fonction reverse sur le résultat du tri interne lexicographique ascendant.

    @out = reverse sort @in;

Ceci est plus efficace que d'utiliser le tri lexicographique descendant explicite, pour la raison citée plus haut : le tri par défaut est plus rapide que d'utiliser une fonction de tri. La fonction reverse est efficace car elle ne fait que déplacer des pointeurs.

Un autre exemple trivial consiste à trier sur une sous-chaîne de l'élément, en utilisant la fonction substr. Ceci peut être plus rapide que le tri avancé équivalent que nous présentons par la suite, car un appel à substr peut être plus rapide qu'une consultation de hash (Manoeuvre Or-cache) ou un déréférencement de tableau (Transformée Schwartzienne).

    @out = sort { substr($a, 4, 6) cmp
                  substr($b, 4, 6) } @in;

Un problème courant consiste à trier sans tenir compte de la casse. Ceci peut être facilement résolu en utilisant la fonction lc ou uc. L'utilisation de l'une ou l'autre donnera les mêmes résultats.

    @out = sort { lc $a cmp lc $b } @in;

Le banc de tests A1 analyse ces exemples selon la taille du jeu de données. Le comportement en O(N*log(N)) est évident, de même que le coût d'utiliser dans la fonction de tri une fonction, fut-elle aussi simple que les fonctions internes substr ou lc.

Tris de champs et d'enregistrements

Les exemples triviaux ci-dessus trient la liste en entrée en utilisant comme clef de tri la chaîne en entier ou une sous-chaîne (pour un tri lexicographique) ou l'élément interprété comme nombre (tri numérique). De manière plus générale, la clef de tri est basée sur des propriétés qui sont fonctions de plusieurs parties de l'élément. Les sous-clefs individuelle peuvent être combinées dans une seule sous-clef ou peuvent être comparées ensemble.

Une chaîne peut être divisée en champs, dont certains peuvent servir de sous-clef. Par exemple, la commande sort des Unix/POSIX permet d'extraire des champs dans le flux en entrée. La fonction sort de Perl ne fournit pas ces facilités, et c'est donc au programmeur d'y remédier. Un module du CPAN s'attache au tris de champs [7].

Si vos données sont des enregistrement qui sont des chaînes complexes ou des références à des tableaux ou des hashes, vous devez comparer les parties pertinentes des enregistrements. Ceci est appelé tri d'enregistrements (les tris de champs en sont un sous-ensemble).

Dans les exemples qui suivent, il faut substituer CLEF() par le code Perl qui effectue l'extraction de la clef de tri. Il vaut mieux de ne pas la faire sous forme d'appel de fonction, car ces appels depuis des fonctions de tri peuvent être prohibitifs. Les appels de fonctions internes de Perl (tels que les appels à lc dans l'exemple précédent) sont équivalents à des opérateurs Perl, et donc moins coûteux.

Pour les tris de chaîne, $a et $b sont positionnés à ces chaînes, et donc pour extraire les clefs de tri, vous devez généralement effectuer diverses opérations de chaînes sur les enregistrements. Les fonctions communément utilisées incluent split, substr, unpack et m//. Voici un exemple, triant par nom d'utilisateur une liste de lignes de fichier passwd. Les champs sont séparés par le caractère deux-points, et le nom d'utilisateur est le premier champ.

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

Tris multiples

Souvent vous devez trier des enregistrements par clef de tri primaire, puis pour tous les éléments ayant la même clef de tri primaire, il vous faut trier sur une clef de tri secondaire. Vous pouvez le faire de manière horriblement inefficace en triant d'abord par la clef de tri primaire, puis trier tous les enregistrements d'une clef de tri primaire donnée par sa clef de tri secondaire. Mais il vaut mieux utiliser une méthode de tri multi-critères. Ceci veut dire l'extraction des clefs pour chaque champ et la comparaison des clefs dans l'ordre de priorité voulu. Et donc deux enregistrements avec la même clef de tri primaire sont immédiatement comparés suivant leurs clefs secondaires. On peut généraliser cette approche pour les tris avec plus de deux sous-clefs de tri.

Perl dispose d'une fonctionnalité intéressante permettant de simplifier les tris multi-critères. Les opérateurs || et or (opérateur logique court-circuit ou) renvoient la valeur du premier opérande logiquement vrai qu'ils rencontrent. Si un couple de clefs primaires sont égaux comparativement parlant, la valeur de retour de la fonction de comparaison sera le résultat de la comparaison des clefs de tri secondaires.

Un petit dessin valant mieux qu'un long discours, un exemple illustrera mieux cet empilement de comparaisons. Voici un tri reposant sur une comparaisons de trois sous-clefs :

    @out = sort {
        # Comparaison des clefs primaires
        CLEF1($a) cmp KEY1($b)
              ||
        # ou si elles sont égales renvoyer
        # la comparaison en ordre numérique
        # descendant
        CLEF2($b) <=> CLEF2($a)
              ||
        # ou si elles sont égales renvoyer
        # la troisième comparaison en ordre
        # lexicographique ascendant
        CLEF3($a) cmp CLEF3($b)
    } @in;

Tris multi-critères naïfs

Dans les deux exemples précédents, nous avons montré un tri avec une extraction de clef coûteuse (via split), et un tri multi-critères. Combinons-les maintenant. Pour coller à la réalité, nous allons résoudre un problème qui a soulevé de nombreux débats dans comp.lang.perl.misc : trier une liste d'adresses IP sous forme décimale pointée. Chaque élément de la list est une chaîne de la forme nnn.nnn.nnn.nnn\tabc.xyz.com\n, où nnn représente un entier entre 0 et 255, avec ou sans zéro initial.

L'approche la plus naïve consiste à considérer chacun des quatre champs numériques comme clef de tri, et trier successivement chacune de ces clefs de tri.

    @out = sort {
        my @a = $a =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/;
        my @b = $b =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/;
        $a[0] <=> $b[0] ||
        $a[1] <=> $b[1] ||
        $a[2] <=> $b[2] ||
        $a[3] <=> $b[3]
    } @in;

Cette approche est lente même pour de petites listes, à cause de toutes les opérations supplémentaires exécutées dans la fonction de comparaison pour chacune des O(N*log(N)) comparaisons.

Calcul d'une clef unique de tri

Afin d'améliorer les performances, nous allons créer pour chaque adresse IP une chaîne d'octets à partir de chacune des quatre sous-clefs, que nous pourrons alors utiliser pour trier le tableau de manière ascendante monotone.

Pour produire la clef la plus courte possible (une chaîne de quatre octets) nécessitant le moins de calculs en Perl, nous utiliserons :

    pack 'C4' => $string =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/;

Cette expression utilise l'opérateur virgule fantaisie =>, que vous pouvez lire appliqué à. Il nous suffit alors de trier ces clefs de tris par ordre lexicographique. Les quatre entiers auraient pu être combinés dans un entier 32-bits par multiplication ou décalage de bits, puis comparés numériquement. Mais nous recherchons autant que faire se peut le tri lexicographique.

Nous nous rapprochons donc d'un tri efficace avec la solution suivante :

    @out = sort {
        pack('C4' => $a =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/)
        cmp
        pack('C4' => $b =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/)
    } @in;

Le benchmark A2 montre que la comparaison des clefs secondaires par paires est moins rapide que de les packer et comparer les chaînes d'octets. Cette observation est valable pour toutes les méthodes de tri. Dans les tests suivants concernant des tris avancés pour ce problème, nous utiliserons donc des clefs de tri packées.

Néanmoins, les tris naïfs sont toujours tristement inefficaces, car chacune des clefs de tri sont recalculées chaque fois qu'un opérande est comparé à un autre. Nous devons donc calculer chaque clef de tri une seule fois et nous rappeler du résultat.

Tris avancés

Comme tous les tris en Perl utilisent la fonction interne sort, et donc le même algorithme quicksort, tous les tris en Perl sont de l'ordre de O(N*log(N)). Nous ne pouvons pas améliorer ce comportement, nous devons donc nous tourner ailleurs pour gagner en efficacité. Comme la complexité est fixée, améliorer les facteurs constants peut être réellement bénéfique, et, dans le monde réel, fournir des améliorations substantielles en terme de rapidité. Quand une fonction de tri doit générer une clef de tri complexe, ceci est réalisé O(N*log(N)) fois, alors qu'il n'y a que N éléments, et donc N clefs de tri. Et si nous arrivions à extraire la clef de tri une seule fois par enregistrement, et à savoir quelle clef de tri correspond à quel élément ?

Mettre les clefs de tri en cache

De manière évidente, nous allons donc associer les clefs avec les éléments dont elles sont dérivées à l'aide d'un hash. Le hash peut être construit dans une première passe sur les données. Si la taille approximative des données est connue, pré-allouer le hash peut encore améliorer les performances.

    keys my %cache = @in;
    $cache{$_} = CLEF($_) for @in;

On peut construire le cache de manière plus efficace en utilisant une tranche de hash :

    keys my %cache = @in;
    @cache{@in} = map CLEF($_) => @in;

La fonction de comparaison va donc simplement trier selon les valeurs des clefs de tri cachées.

    @out = sort {
        $cache{$a} cmp $cache{$b}
    } @in;

En fait, nous avons simplement remplacé de longs calculs compliqués dans la fonction de tri par une rapide consultation de hash (O(1)).

Et si vous souhaitez réaliser une comparaison multi-critères plus complexe, vous devez soit utiliser un cache séparé pour chacune des sous-clefs ou combiner les clefs de tri secondaires comme nous le verrons plus tard. Voici un exemple de la première solution :

    keys my %cache1 = @in;
    keys my %cache2 = @in;
    $cache1{$_} = CLEF1($_),
    $cache2{$_} = CLEF2($_) for @in;
    @out = sort {
        $cache1{$a} cmp $cache1{$b} ||
        $cache2{$b} <=> $cache2{$a}
    } @in;

Ou alors, un cache multi-niveaux peut être utilisé, qui sacrifie un peu de vitesse pour sauver un peu d'espace :

    keys my %cache = @in;
    $cache{@in} = map [ CLEF0($_), CLEF1($_) ] => @in;
    @out = sort {
       $cache{$a}[0] cmp $cache{$b}[0]
                   ||
       $cache{$b}[1] <=> $cache{$a}[1]
    } @in;

Un point important à propos des tris cachés est qu'aucun post-traitement n'est nécessaire pour retrouver les éléments triés. Cette méthode trie les enregistrements réels, mais utilise le cache pour réduire l'extraction des clefs de tri en O(N).

La Manoeuvre Or-Cache (Orcish Maneuver ou OM)

La Manoeuvre Or-Cache (inventée par Joseph N. Hall [8]) élimine la phase de prétraitement des données, qui peut éviter une copie des données si elles sont lues directement depuis un fichier. Il effectue l'extraction des clefs de tri une fois par enregistrement, étant donné qu'il vérifie dans le hash si l'extraction a déjà été effectuée auparavant. Le test et le stockage des clefs de tri est effectué par l'opérateur ||= (assignement ou-logique court-circuité), qui évalue et assigne l'expression de droite à la lvalue de gauche, si ladite lvalue est fausse. ([NdT] Le nom orcish est un jeu de mots avec or-cache). Nous nous retrouvons donc avec la fonction de tri suivante :

    keys my %or_cache = @in;
    @out = sort {
        ($or_cache{$a} ||= CLEF($a))
        cmp
        ($or_cache{$b} ||= CLEF($b))
    } @in;

La première partie de la fonction de tri vérifie si la clef de tri de $a est cachée. 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).

Et voici maintenant un exemple de comparaison multi-critères utilisant deux caches :

    keys my %or_cache1 = @in;
    keys my %or_cache2 = @in;
    @out = sort {
        ($or_cache1{$a} ||= CLEF1($a))
        cmp # clef de tri primaire
        ($or_cache1{$b} ||= CLEF1($b))
        ||  # ou
        ($or_cache2{$b} ||= CLEF2($b))
        <=> # clef de tri secondaire (numérique)
        ($or_cache2{$a} ||= CLEF2($a))
    } @in;

La Manoeuvre 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. 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 Manoeuvre Or-Cache (se reporter au banc de tests A3).

La Transformée Schwartzienne (Schwartzian Transform ou ST)

Une manoeuvre plus efficace de cacher les clefs de tri, sans utiliser de variables temporaires nommées, fut popularisée par Randal L. Schwartz, et fut surnommée Transformée Schwartzienne [9, 10] (elle aurait du en fait s'appeler Transformée de Schwartz, selon le modèle utilisé pour les transformées de Fourrier et de Laplace, mais il est trop tard maintenant pour changer le nom).

L'invention majeure de la ST consiste à 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 (comme ce que nous avons fait auparavant pour calculer le cache des clefs de tri).

    @out =
        map  $_->[0] =>
        sort { $a->[1] cmp $b->[1] }
        map  [ $_, CLEF($_) ] =>
        @in;

La ST ne trie pas en fait les données réelles. Elle trie les références à des tableaux anonymes contenant l'élément de 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 ST 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 ou entre les différentes comparaisons des clefs de tri secondaires, comme dans la Manoeuvre Or-cache ou le tri naïf.

    @out =
        map  $_->[0] =>
        sort { $a->[1] cmp $b->[1] ||
               $b->[2] <=> $a->[2] }
        map  [ $_, CLEF1($_), CLEF2($_) ] =>
        @in;

Pour une déconstruction lumineuse de la ST et une reconstruction non moins éclairée, se référer au [11].

Le tri interne packé

Toutes les techniques avancées de tri décrites auparavant sauvegardent les opérandes à trier avec leurs clefs de tri (dans les tris cachés, 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îne d'octet, en utilisant la concaténation.

Cette optimisation peu connue améliore la ST en éliminant la fonction de tri et en s'appuyant donc sur le tri lexicographique par défaut, qui, comme nous l'avons montré auparavant, est très rapide. Cette méthode est celle utilisée dans le module Sort::Records.

Afin d'accomplir ceci, nous allons modifier la ST 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.

Plusieurs méthodes peuvent être utilisées, seules ou en les combinant, afin de construire les chaînes d'octet. Les techniques pour calculer les clefs selon le type de données sont présentées dans l'annexe B.

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érandes selon plusieurs méthodes, y compris un appel à substr (comme dans l'exemple suivant), ce qui est certainement le plus rapide, split, unpack ou une expression rationnelle.

    @out =
        map substr($_, 4) =>
        sort
        map pack('C4' => /(\d+)\.(\d+)\.(\d+)\.(\d+)/) . $_ =>
        @in;

Bancs de test du tri interne packé

Le banc de tests A4 compare les deux techniques génériques les plus avancées, ST et défaut-packé. Les tris multi-passes sont mesurés en tant qu'instruction seule ainsi que le temps relatif mis par chacune des instructions le composant.

Le tri interne packé est environ deux fois plus rapide que la ST, ce qui en fait l'algorithme Perl générique le plus rapide.

Nous avons montré auparavant les tris simples utilisant les fonctions substr ou lc. Même dans ces cas, le tri interne packé est plus efficace dès qu'il s'applique à plus de quelques éléments. Se reporter au banc de tests A5, qui montre un comportement quasi en O(N) pour le tri interne packé sur des échantillons de taille variée, car le tri est bien plus rapide que l'extraction des clefs.

Trier une liste de tableaux ou de hashes

Considérons maintenant le problème classique consistant à trier une structure à deux dimensions, une liste de références à des tableaux ou des hashes, où les clefs de tris sont fonctions des valeurs des membres de la structure.

Si nous devions utiliser la méthode de tri interne packé, les références seraient converties en chaînes et concaténées aux clefs de tri. Après le tri, les opérandes pourraient être retrouvées en tant que chaînes, mais ne seraient plus utilisables en tant que références. Nous devons à la place utiliser les index des membres à la place des opérandes à trier.

Le banc de test suivant compare un tri clef packées ST et un tri indexé utilisant la méthode de tri interne packé. La liste à trier comprend des références vers des tableaux, dont chacun a deux éléments : une adresse IP (servant de clef de tri primaire), et un nom de domaine (servant de clef de tri secondaire). Ce sont les mêmes données que celles utilisées dans les bancs de test précédents, éclatées dans deux éléments de tableau.

    @out =
        map $_->[0] =>
        sort { $a->[1] cmp $b->[1] }
        map [ $_, pack('C4 A' =>
              $_->[0] =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/,
              $_->[1]) ] =>
        @in;

    my $i = 0;
    keys my %h = @in;
    @h{ map pack( 'C4 A x N' =>
                  $_->[0] =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/,
                  $_->[1], $i++
                ) => @in
      } = @in;
    @out = @h{ sort keys %h };

Le tri indexé est plus rapide que la ST une fois de plus (se reporter au benchmark A6).

Tris indexés et stabilité

Dans le tri indexé, l'auto-incrémentation de l'index $i assure qu'aucun élément de tableau n'aura de clef de tri packée identique. Elle assure de plus que le tri sera stable.

Tout tri en Perl peut être stabilisé en utilisant un index de cette sorte comme clef de tri décisive. Ceci offre de surcroît un avantage possible pour le tri indexé. Les éléments à trier (qui peuvent être de grandes chaînes) n'ont pas besoin d'être concaténées aux clefs de tri, ce qui créerait une deuxième copie de chaque élément. En utilisant le tri indexé, les enregistrements peuvent être récupérés après le tri depuis les données initiales, en utilisant les index triés.

Le module Sort::Records

Uri Guttman ([NdT] l'un des auteurs de l'article) a créé le module Sort::Records [12] qui combine la technique de tri interne packé avec l'extraction automatique des clef de tri en utilisant une syntaxe attribut / valeur. Le module crée une fonction qui convertit les clefs de tri en une chaîne d'octets qui peut être triée en utilisant la fonction interne de tri. Une référence à cette fonction est sauvée, et l'objet peut être utilisé pour trier d'autres données ou peut être clonée.

Conclusions

Packer les clefs de tri dans des chaînes pouvant être comparées lexicographiquement améliore les performances de toutes les techniques de tri, par rapport aux méthodes comparant les clefs de tri par paires.

Concaténer les opérandes aux clefs de tri permet d'utiliser la fonction de tri par défaut de Perl, en ordre lexicographique ascendant (sans fonction de tri personnalisée). Ceci permet d'effectuer des tris considérablement plus rapides que la Manoeuvre Or-cache ou la Transformée Schwartzienne. L'opération de tri peut même approcher d'un comportement en O(N) sur des données de grande taille, car le temps O(N*log(N)) du tri en lui-même peut être petit comparé au temps requis pour extraire les clefs de tri.

Le tri interne packé peut être utilisé explicitement, ou via le module Sort::Records.

Remerciements

L'idée de cet article a été soulevée par Michal Rutka [13]. John Porter a participé à l'élaboration du projet. Tom Christiansen a fourni de précieux commentaires sur l'avant-dernière version.

[NdT] Je tiens à remercier ici Uri Guttman et Larry Rosler pour m'avoir permis de traduire cet article.

Références

Annexe A : Bancs de test

L'utilité d'un banc de test repose sur l'isolation judicieuse des variables appropriées, dans l'algorithme testé et dans l'ensemble des valeurs. Différentes implémentations peuvent donner des résultats relatifs différents même avec le même algorithme et les mêmes données. Les tests suivants doivent donc être vérifiés suivant vos propres conditions. Bref, ça dépend.

Dans les bancs de test suivants, toutes les données représentes le temps CPU (en microsecondes) par ligne de données en entrée, qui compte en moyenne 35 caractères. Tous les tableaux nommés et les hashes sont pré-alloués, ce qui réduit la variance des mesures dûe à l'allocation du stockage.

A1 : Tris triviaux

    +------------------------------------------+
    | Méthode       | Code                     |
    |---------------+--------------------------|
    | Contrôle      | @out = @in;              |
    |---------------+--------------------------|
    | Défaut        | @out = sort @in;         |
    |---------------+--------------------------|
    | Reverse       | @out = reverse sort @in; |
    |---------------+--------------------------|
    | Explicite     | @out = sort              |
    |               |     { $a cmp $b } @in;   |
    |---------------+--------------------------|
    | Sous-chaîne   | @out = sort {            |
    |               |     substr($a, 4, 6) cmp |
    |               |     substr($b, 4, 6) }   |
    |               |   @in;                   |
    |---------------+--------------------------|
    | Insensibilité | @out = sort              |
    | à la casse    |     { lc $a cmp lc $b }  |
    |               |   @in;                   |
    +------------------------------------------+

    +--------------------------------------------+
    | Nombre de lignes | 100 | 1000 | 10K | 100K |
    |------------------+-----+------+-----+------|
    | Contrôle         |   5 |    6 |   7 |    8 |
    |------------------+-----+------+-----+------|
    | Défaut           |   9 |   13 |  19 |   25 |
    |------------------+-----+------+-----+------|
    | Reverse          |   9 |   14 |  19 |   26 |
    |------------------+-----+------+-----+------|
    | Explicite        |  17 |   25 |  37 |   50 |
    |------------------+-----+------+-----+------|
    | Sous-chaîne      |  33 |   49 |  68 |   85 |
    |------------------+-----+------+-----+------|
    | Casse            |  43 |   64 |  92 |  120 |
    +--------------------------------------------+

A2 : Tris naïfs (adresses IP)

    +---------------------------------------------+
    | Nombre de lignes | 100 | 1000 |  10K | 100K |
    |------------------+-----+------+------+------|
    | Clefs de tri     | 697 | 1251 | 1732 | 2758 |
    | séparées         |     |      |      |      |
    |------------------+-----+------+------+------|
    | Clefs de tri     | 583 | 1002 | 1363 | 1814 |
    | packées          |     |      |      |      |
    +---------------------------------------------+

A3 : Tris cachés (clefs packées)

    +----------------------------------------------+
    | Nombre de lignes   | 100 | 1000 | 10K | 100K |
    |--------------------+-----+------+-----+------|
    | Mise en cache      |  66 |   75 |  85 |   74 |
    |--------------------+-----+------+-----+------|
    | Tri                |  49 |   87 | 122 |  164 |
    |--------------------+-----+------+-----+------|
    | Total cache+tri    | 116 |  163 | 215 |  240 |
    |--------------------+-----+------+-----+------|
    | Manoeuvre Or-cache | 125 |  168 | 221 |  256 |
    +----------------------------------------------+

A4 : Tris avancés par clefs packées

    +---------------------------------------------+
    | Nombre de lignes  | 100 | 1000 | 10K | 100K |
    | ------------------+-----+------+-----+------|
    | ST                |     |      |     |      |
    |-------------------+-----+------+-----+------|
    | Mise en cache     |  80 |   84 |  84 |   75 |
    |-------------------+-----+------+-----+------|
    | Tri               |  27 |   47 |  76 |   97 |
    |-------------------+-----+------+-----+------|
    | Récupération      |  13 |   18 |  20 |   17 |
    |-------------------+-----+------+-----+------|
    | Une instruction   | 116 |  150 | 177 |  191 |
    |-------------------+-----+------+-----+------|
    | Tri interne packé |     |      |     |      |
    |-------------------+-----+------+-----+------|
    | Package           |  61 |   63 |  65 |   67 |
    |-------------------+-----+------+-----+------|
    | Tri               |   9 |   12 |  18 |   25 |
    |-------------------+-----+------+-----+------|
    | Récupération      |  12 |   12 |  13 |   12 |
    |-------------------+-----+------+-----+------|
    | Une instruction   |  73 |   79 |  86 |   93 |
    +---------------------------------------------+

A5 : Eclairage sur les tris triviaux

    +--------------------------------------------+
    | Sous-chaîne  | @out = map substr($_, 6) => |
    | packée       |    sort map                 |
    |              |    substr($_, 4, 6) . $_ => |
    |              |   @in;                      |
    |--------------+-----------------------------|
    | Packée       | @out = map substr($_,       |
    | insensible   |    1 + rindex $_, "\0")=>   |
    | à la casse   |    sort map "\L$_\E\0$_" => |
    |              |   @in;                      |
    +--------------------------------------------+

    +-------------------------------------------+
    | Nombre de lignes | 10| 100| 1000| 10K|100K|
    |------------------+---+----+-----+----+----|
    | Sous-chaîne      | 17|  33|   49|  68|  85|
    |------------------+---+----+-----+----+----|
    | substr packé     | 21|  23|   27|  35|  42|
    |------------------+---+----+-----+----+----|
    | Insens.          | 20|  43|   64|  92| 120|
    |------------------+---+----+-----+----+----|
    | Insens. packé    | 26|  29|   32|  38|  47|
    +-------------------------------------------+

A6 : Tris packés à deux dimensions

    +--------------------------------------------+
    | Nombre de lignes | 100 | 1000 | 10K | 100K |
    |------------------+-----+------+-----+------|
    | ST               | 243 |  314 | 359 |  435 |
    |------------------+-----+------+-----+------|
    | Index            | 200 |  285 | 323 |  259 |
    +--------------------------------------------+

Annexe B : tris internes explicites packés

B1 : Création de clefs de tri triables (chaînes)

Voici la phase de prétraitement (le premier map exécuté).

    @sorted = map ... => sort
        map CLEF($_) . $_ => @data;

Pour créer une clef de tri et son opérande concaténé, n'importe quelle combinaison de concaténation, interpolation, pack ou sprintf peut être utilisée, les deux derniers avec des formats simples ou composés.

B2 : Extraire les opérandes des chaînes triées

Cette section concerne la phase de post-traitement (le deuxième map exécuté).

    @sorted = map RESTAURE($_) =>
        sort map ... => @data;

Si toutes les clefs secondaires ont une longueur connue, utiliser la longueur totale :