array et comparaison de valeurs

Version imprimable

07/02/2011, 14h24
Jasmine80

array et comparaison de valeurs

j'ai un array et j'aimerais afficher les x plus grandes valeurs et garder les indices associés ... quelle est la façon la + simple de faire? Merci
07/02/2011, 14h35
djibril

Tu reprends l'algo traité ici.
07/02/2011, 14h39
Dimitry.e

Tu crées un tableau T de X cases dans lequel tu stockeras, de manière ordonnée, les indices des X plus grandes valeurs de ta liste L.

Tu parcours ta liste élément par élément et tu insères l'indice de l'élément courant E dans T si T n'est pas rempli.
Si T est plein, tu compares E à L(T(0)). Si E est plus grand, tu supprimes T(0) et tu insères l'indice de E à sa place dans T.

Si ça peut attendre quelques minutes, j'essaierai de te donner un bout de code.

merci

merci, j'obtiens ainsi la valeur maximum et son indice mais si je veux les 5 premières valeurs maximales

ex : 564, 469, 456, 400, 365

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/perl
use warnings;
use strict;
 
 
 
my @test = qw/ 1 6  2 365 4 0 06 6 8 76 055 46 0 065 456 40 -5  95 4 05 400 564  4 469 6/;
 
# rechercher les indexs des 5 valeurs les + élevées
my $nb = 5;
 
my ($index, $max);
 
for my $i ( 0..$#test ) {
 
  if ( ( defined $max and $test[$i] > $max ) || not defined $max ) { 
 
    $index = $i; 
    $max = $test[$i]; 
 
  }
 
}
print "Index : $index, Max : $max\n";

comment adapter pour obtenir ces 5 valeurs et leur indice?

07/02/2011, 14h47
Jasmine80

Citation:

Envoyé par Dimitry.e

Tu crées un tableau T de X cases dans lequel tu stockeras, de manière ordonnée, les indices des X plus grandes valeurs de ta liste L.

Tu parcours ta liste élément par élément et tu insères l'indice de l'élément courant E dans T si T n'est pas rempli.
Si T est plein, tu compares E à L(T(0)). Si E est plus grand, tu supprimes T(0) et tu insères l'indice de E à sa place dans T.

Si ça peut attendre quelques minutes, j'essaierai de te donner un bout de code.

merci, c'est très sympa ;) ça a le temps, c'est pour demain. Je m'y remettrai à 7h00 en arrivant au boulot. Bonne après-midi.

j'avais pensé à qqch comme ça

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/bin/perl
 
use warnings;
use strict;
 
    use List::MoreUtils qw{    indexes    }; 
 
my @array_score = qw/ 1 6  2 365 4 0 06 6 8 76 055 46 0 065 456 40 -5  95 4 05 400 564  4 469 6/;
 
# rechercher les indexs des 5 valeurs les + élevées
my $nb = 5;
 
 
# tableau contenant les indices classés de @array_score
my @liste_t;
 
for (0..$#array_score){
 
	# on recherche l'indice ayant la valeur la + élevée de @array_score
	my @x = indexes { $_ == (sort {$b<=>$a} @array_score )[0]  } @array_score ;
 
	# on place la valeur de l'indice dans @liste_t
	push @liste_t, $x[0],
 
	# on supprime la valeur de @array_score
	delete $array_score[$x[0]];
 
 
}

:( mais à ça ne va pas

Il y a certainement mieux, mais voilà une solution :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
use strict;
use warnings;
 
my @t = qw/ 1 6  2 365 4 0 06 6 8 76 055 46 0 065 456 40 -5  95 4 05 400 564  4 469 6/;
my $N = 5;
 
#Stocker les indices des N premieres valeurs
my @max = (0..$N-1);
 
#Trier les indices en fonction des valeurs correspondantes dans t
@max = sort({$t[$a]<=>$t[$b]} @max);
 
#Recherche de valeurs plus grandes dans le reste du tableau
my $i = 5;
while ($i<scalar(@t)) {
  #Si la valeur pointee par i est plus grande que les 5 retenues
  if($t[$i] > $t[$max[0]]) {
    $max[0] = $i; # Ajouter son indice a la liste
    @max = sort({$t[$a]<=>$t[$b]} @max); # Placer le nouvel indice au bon endroit
  }
  ++$i;
}
 
foreach my $m (@max) {
  print $t[$m]."\n";
}

L'algorithme de dimitry me semble pas mal :
Code:

1 2 3 4 5 6 7 8 @index = (); my @array_score = qw/ 1 6 2 365 4 0 06 6 8 76 055 46 0 065 456 40 -5 95 4 05 400 564 4 469 6/; foreach my $score (0 .. $#array_score) { @index = (sort { $array_score[$b] <=> $array_score[$a] } grep defined, @index, $score)[0.. 4]; } print map "$array_score[$_] (indice $_)\n", @index;
Le sort n'est pas aussi efficace qu'une recherche linéaire pour savoir quel élément éjecter, mais sur une taille de 5 éléments et avec une liste toujours presqu'entièrement déjà triée, la perte d'efficacité aura une incidence assez faible.

Edit : grillé (de peu ;) )

Voilou

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/perl
use warnings;
use strict;
use List::MoreUtils qw{    uniq    }; 
 
my @test = qw/ 1 6  2 365 4 0 06 6 8 76 055 46 0 065 456 40 -5  95 4 05 400 564  4 469 6/;
my %values_index;
my $recherche_x_plus_grande_valeur = 5;
 
foreach my $valeur ( reverse sort { $a <=> $b } uniq @test ) {
  $values_index{$valeur} = undef;
  $recherche_x_plus_grande_valeur--;
  last if ( $recherche_x_plus_grande_valeur == 0 );
}
 
 
for my $i ( 0..$#test ) {
  if ( exists $values_index{ $test[$i] } ) { 
    print "Index : $i, value : $test[$i]\n";
    delete $values_index{ $test[$i] };
    last if ( scalar keys %values_index == 0 ); 
  }
}

07/02/2011, 16h44
djibril

Edit: grillé par les 2 ;)

Je me disais bien que j'avais déjà fait ça dans ma période "ça tient sur deux lignes en perl" :
Code:

1 2 3 4 my @t = qw/ 1 6 2 365 4 0 06 6 8 76 055 46 0 065 456 40 -5 95 4 05 400 564 4 469 6/; my $N = 5; @max = (sort({$t[$a]<=>$t[$b]} (0..$#t)))[scalar(@t)-$N..$#t];

08/02/2011, 07h20
Jasmine80

merciiiiiiiiii

:ccool: un grand merci pour vos réponses, c'est vraiment très sympa de votre part.
08/02/2011, 10h35
Philou67430
Citation:
Envoyé par Dimitry.e

Je me disais bien que j'avais déjà fait ça dans ma période "ça tient sur deux lignes en perl" :

Code:

1 2 3 4 my @t = qw/ 1 6 2 365 4 0 06 6 8 76 055 46 0 065 456 40 -5 95 4 05 400 564 4 469 6/; my $N = 5; @max = (sort({$t[$a]<=>$t[$b]} (0..$#t)))[scalar(@t)-$N..$#t];
Effectivement, le plus court est naturellement de faire un sort sur TOUT le tableau (tester l'efficacité de l'algo sur de gros tableaux par rapport à ton algo proposé initialement, qui est moins complexe).

Sinon, tu peux encore encore réduire ta ligne :

Code:

@max = (sort({$t[$b]<=>$t[$a]} (0..$#t)))[0..$N-1]; # tri inverse

ou

Code:

@max = (sort({$t[$a]<=>$t[$b]} (0..$#t)))[-$N..-1];
08/02/2011, 11h14
djibril

Citation:

Envoyé par Philou67430

Effectivement, le plus court est naturellement de faire un sort sur TOUT le tableau (tester l'efficacité de l'algo sur de gros tableaux par rapport à ton algo proposé initialement, qui est moins complexe).

Sinon, tu peux encore encore réduire ta ligne :

Code:

@max = (sort({$t[$b]<=>$t[$a]} (0..$#t)))[0..$N-1]; # tri inverse

ou

Code:

@max = (sort({$t[$a]<=>$t[$b]} (0..$#t)))[-$N..-1];

Pour faire le trie inverse, il faut utiliser reverse au lieu de $b <=> $a. C'est plus optimum !!
08/02/2011, 11h26
Philou67430

Euh... relis djibril... c'est ce que j'ai fais (mais comme le demandais Jasmine, c'est fait sur le tri des indices, pas sur celui des valeurs) 8-)

Fuseau horaire GMT +2. Il est actuellement 13h45.