Discussion :

[CKLN00]

Salut ,
alors je cherche à faire un tri sur un tableau
les éléments du tableau sont du type : 123,55*
soit /\d+ \d+[X><*]/ sous forme d'expression réguliere
et en fait j'aimerais trier ma liste comme suit : selon le chiffre qui vien avant la virgule et en cas d'égalité selon le chiffre qui suit la virgule c a d si j'ai :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
my @list = ('19,12*','1,15X','100,1<','1,8>','19,20X','100,0*') ;
# j'aimerais avoir à la fin :
@list_trie = ('1,8>','1,15X','19,12*','19,20X','100,0*','100,1<')

mais je n'ai pas trouver quelles instruction mettre dans le bloque du sort

[Jasmine80]

A ta place je créerais un tableau dont la clé serait composée du chiffre décimal correspondant à ton entier et ta fraction et je placerais la valeur entière de ta donnée en valeur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
$hash{19.12} = '19,12*';
$hash{1.15} = '1,15X' ;
$hash{100.1} = '100,1<';
$hash{1.8} =  '1,8>';

Tu remplis ta hash via une expreg et ensuite tu fais un (sort {$a<=>$b] keys %hash ) et le tour est joué !!!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/bin/perll
 
use strict;
use warnings;
 
my @list = ('19,12*','1,15X','100,1<','1,8>','19,20X','100,0*') ;
 
my %hash;
 
foreach my $val (@list ){
		my ($ent, $dec) = ( $val =~ /(\d+),(\d+)\D/);
		$hash{$ent.'.'.$dec} = $val;
}
 
my @sort;
 
foreach my $x (sort {$a<=>$b} keys %hash){
		push(@sort, $hash{$x});
}
 
map{print $_."\n";} @sort;

[CKLN00]

j'avais pensé à cette méthode sauf que 19.10 seras AVANT 19.9 alors que justement je ne veut pas !

[Jasmine80]

http://www.sysarch.com/Perl/sort_paper.html

Multi-subkey sorts

In some cases you need to sort records by a primary subkey, then for all the records with the same primary subkey value, you need to sort by a secondary subkey. One horribly inefficient way to do this is to sort first by the primary subkey, then get all the records with a given subkey and sort them by the secondary subkey. The standard method is to do a multi-key sort. This entails extracting a subkey for each field, and comparing paired subkeys in priority order. So if two records with the same primary subkey are compared, they will actually be compared based on the secondary subkey. Sorting on more than two subkeys is done by extending the logic.

Perl has a very nice feature which makes multi-key sorts easy to write. The || (short-circuit or) operator returns the actual value of the first logically true operand it sees. So if you use || to concatenate a set of key comparisons, the first comparison is the primary subkey. If a pair of primary subkeys compare equal, the sortsub´s return value will be the result of the secondary subkey comparison.

[Jasmine80]

J'ai mis le temps à comprendre le fonctionnement mais cela fait ce que tu veux.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/bin/perll
 
use strict;
use warnings;
 
my @in = ('19,12*', '19,9U', '1,15X','100,1<','1,8>','19,20X','100,0*') ;
 
my @out = sort {
 
         $a =~ /(\d+,\d+)\D+/;
         $b =~ /(\d+,\d+)\D+/;
 
         (split ',', $a)[0] <=> (split ',', $b)[0]  ||
         (split '\D', $a)[1] <=> (split '\D', $b)[1] 
} @in;
 
 
 
 
 
map{print $_."\n";} @out;

Je ne sais pas pourquoi mais dans $a =~ /(\d+,\d+)\D+/; , $a récupère quand même les lettres et donc lors du second tri, Perl n'est pas content. J'évite les messages d'erreurs en effectuant le second split sur '\D' au lieu de ',' afin de me débarasser des lettres excédentaires.

Voila, en attendant de trouver mieux, tu peux utiliser cette façon de procéder.

[CKLN00]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
my @out = sort {
 
         $a = $a =~ /(\d+,\d+)\D+/;
         $b = $b =~ /(\d+,\d+)\D+/;
 
         (split ',', $a) <=> (split ',', $b)

je suppose que comme ça c'est mieux (pas encore tester !)

[Jasmine80]

Tu n'as pas compris le principe. Tu as deux parties séparées par ||. Tu commences par comparer les deux valeurs entières et ensuite, si elles sont égales tu effectues la seconde partie qui compare les parties décimales.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
         (split ',', $a)[0] <=> (split ',', $b)[0]  ||
         (split ',', $a)[1] <=> (split ',', $b)[1]

Si tu ne mets qu'une partie à ton 'sort', le tri sera numérique sur l'entièreté de tes valeurs (partie entière et partie décimale prise en compte en même temps) et ton .9 dera évidemment considéré comme .90 et donc placé après ton .13

Est-ce clair? Tu peux aller voir la documentation du lien.

[Jedai]

En bref tu veux trier des chiffres décimaux mais ils ne sont pas au bon format, c'est ça ?

Si le changement de format ne te dérange pas, tu peux juste en passer par la comparaison numérique :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
s/(\d+),/$1./ foreach @list;
{ no warnings "numeric"; @list = sort { $a <=> $b } @list; }
# optionel pour en revenir aux virgules :
# s/(\d+)./$1,/ foreach @list;

fera ce que tu veux (mais les virgules seront remplacés par des points, enfin tu peux toujours inverser ceci après).

--
Jedaï

[Jasmine80]

j'avais pensé à cette méthode sauf que 19.10 seras AVANT 19.9 alors que justement je ne veut pas !

Il ne veut pas que ses valeurs soient traitées comme des nombres décimaux mais que la partie décimale soit traitée comme une partie entière et donc que .9 passe avant .10

[Jedai]

Il ne veut pas que ses valeurs soient traitées comme des nombres décimaux mais que la partie décimale soit traitée comme une partie entière et donc que .9 passe avant .10

Ah effectivement... Dans ce cas, ta méthode est correcte (bien que l'implémentation soit loi d'être optimale) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
my @sorted_list =
  map { $_->[2] }
    sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] }
      map { m/^(\d+),(\d+)\D$/; [ $1, $2, $_ ] }
        @list;

sera plus rapide (Schwartzian Transform), ou même utiliser l'un des Sort modules du CPAN.

--
Jedaï

[Jasmine80]

Pourrais-tu expliquer ton code s'il te plait.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
  map { $_->[2] }

Pourquoi commence t'on par cette ligne?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  map { m/^(\d+),(\d+)\D$/; [ $1, $2, $_ ] }

Donc ici on vérifie que la liste [ $1, $2, $_ ] match bien ? Que contient $_


Merci beaucoup,

[Jedai]

Tu as une explication dans le lien que tu as donné plus tôt. Les Perliste lui donne un nom "Swartzian Transform" mais c'est une technique très naturelle pour un programmeur ayant l'expérience du paradigme fonctionnel.
Il faut le lire à l'envers, de bas en haut (enfin si tu n'as pas d'expérience avec, ça se lit bien de haut en bas pour un habitué).
L'idée est de commencer par transformer ton tableau en tableau 2D, chaque élément étant rassemblé avec ses clés de tri :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

map { m/^(\d+),(\d+)\D$/; [ $1, $2, $_ ] }

ici je crée pour chaque élément de @list un tableau anonyme contenant le premier nombre, le deuxième nombre et l'élément d'origine.

Ensuite on tri normalement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] }

sur le premier nombre et le deuxième nombre.

Puis on reextrait les éléments d'origine en jetant les clés de tri :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

map { $_->[2] }

Et au final on obtient notre tableau trié.

Cette technique est relativement efficace, elle ne pollue pas l'espace de nom, elle ne calcule que O(n) fois la clé de tri au lieu de O(n*ln(n)). Pour faire mieux en Perl, il faut en revenir au tri par défaut (sort sans subroutine de tri) ce qui est faisable mais illisible, le mieux est de le faire faire par un module de tri comme Sort::Maker par exemple.

(Je rappelle quelques éléments clés : dans la subroutine passée à map, $_ est l'élément du tableau entrant, les regexps sans "=~" s'appliquent par défaut à $_)

--
Jedaï

[Jasmine80]

Merci beaucoup pour les explications, c'est vraiment très clair dans mon esprit maintenant.

[CKLN00]

Woaw ! heu et bha alors heu bien merci beaucoup !
j'ai appris des choses bien intéressantes !

[Jasmine80]

Oui, moi aussi je vais d'ailleurs lire en détails la documentation sur les tris.