Discussion :

[kioka]

Bonjour,

J'ai un tableau où chaque ligne est composée d'un tableau de 2 éléments [borne 1, borne 2]. Mon but est d'éliminer toutes les lignes dont les bornes sont déjà incluses dans d'autres lignes.
Exemple :

Mon vrai tableau fait plus de 2000 lignes !

Je me retrouve toujours avec une boucle infinie, je n'arrive pas à avoir une idée sur comment coder ça ...

Si vous avez des conseils et idées ... je suis toute ouïe !

[Jasmine80]

Bonjour,

J'ai un tableau où chaque ligne est composée d'un tableau de 2 éléments [borne 1, borne 2]. Mon but est d'éliminer toutes les lignes dont les bornes sont déjà incluses dans d'autres lignes.

Un array de array donc?
Peux-tu nous montrer ton code?

[Jasmine80]

A ta place, je chercherais un module sur le CPAN, il y en a certainesment pouvant t'aider.
C'est de loin la meilleure solution !

Sinon, un algorithme possible (mais il doit y avoir mieux) serait

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
22
# transformation schwarzienne
# tri sur la première puis la seconde valeur
my @sort_tab = (
	[11502, 13256],	
	[11502,	15202],
	[11725,	14536],
	[12010, 15202],
	[25312,	45258],
	[35258,	37256],
);
 
prend les valeurs $sort_tab[0][0] et $sort_tab[1][0]
	si elles sont égales => suppression de @{$sort_tab[0]} (car $sort_tab[0][1] < $sort_tab[1][1] car tableau trié)
	sinon, comparaison de $sort_tab[0][1] et $sort_tab[1][1]
		si $sort_tab[0][1] >= $sort_tab[1][1] (on sait que $sort_tab[0][0] < $sort_tab[1][0])
			suppression de l'array @{$sort_tab[1]}
 
 
			suppression de l'array @{$sort_tab[2]}			
En fonction du résultat précédent : 
	comparaison de $sort_tab[0][0] et $sort_tab[2][0] ou de $sort_tab[1][0] et $sort_tab[1][0]
	...

Il y a peut-être une solution beaucoup plus efficace en cherchant la valeur minimale de ta borne gauche et la valeur maximale de ta borne droite. Puis de récupérer la borne gauche et droite correspondantes dans ces 2 lignes et de rechercher les autres lignes qui pourraient avoir des bornes intermédiaires.

[Jasmine80]

Peut-être peux-tu utiliser ce module Text-NumericList

Code :

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

1
2
3
4
5
  $list->set_string('1-3,5-7');
  my @array = $list->get_array;     # Returns (1,2,3,5,6,7)
 
  $list->set_array(1,2,3,5,6,7);
  my $string = $list->get_string;   # Returns '1-3,5-7'

Avec le tableau de l'exemple

Code :

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

$list->set_string('11502-15202', '12010-15202', '11725-14536', '11502-13256', '25312-45258', '35258-37256');

Puis utiliser la fonction inverse afin de recréer de nouveaux couples de bornes ne se chevauchant pas. Mais les couples de bornes seront probablement différents que ceux de ton tableau de départ, et tu auras une analyse ultérieure à faire.

[kioka]

Kikou,
Oui en effet c'est bien un array de array

Dans mon tableau j'ai enfaite plusieurs colonnes, la 3e étant la distance entre les bornes.
Ce que j'ai fait, mais ma boucle tourne à l'infinie :

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# trier mon tableau des plus grandes distances au plus petites.
my @tri = sort { $$b[3] <=> $$a[3] } @tab;
 
# je me crée un tableau finale vide
my @net = ();
 
# j'initialise mon min et max
my $min = $tri[0][0];
my $max = $tri[0][1];
 
# pour stopper mon while
my $t = $#tri;    # taille du tableau
my $j = 0;
 
# ma boucle :
while (@tri)   # tant que mon tableau tri est définis
{
   foreach my $e(@tri)
   {
       my $i = 0; # pour connaître ma position dans le tableau
       if($$e[0] > $min and $$e[1] < $max or
          $$e[0] = $min and $$e[1] < $max or
          $$e[0] > $min and $$e[1] = $max )
       {
              # j'enlève la ligne de mon tableau
	      splice(@tri,$i,1);
              # réinitialise mes variables
	      $t = $#tri;
	      $j = 0;
	}
	$i++;
   }
   # normalement on entre dans ici que si plus aucun élément n'est 
   # enlevé du tableau ... il n'y a plus rien à enlever ...
   if ($j == $t) 
   {
        @net = @tri;
        undef(@tri);
   }
   # réinitialise le min et max 
   $min = $tri[0][0];
   $max = $tri[0][1];
   $j++;
}

Je peut marquer @tri = undef ou undef(@tri) ou @tri =(); rien n'y fait il continue le while ....

Je vais regarder les astuces que tu me propose ... je te dirais ensuite ce que ça donne.

Merci !

[EDIT : juste pour éviter les doubles posts ]
Non la méthode set_string ne s'adapte pas car mon tableau ne fait pas juste 2 colonnes, j'ai mis 2 colonnes juste pour simplifier. En faite, il fait 18 colonnes et 2378 lignes ...
Merci quand même

J'ai réussi à stopper ma boucle mais mon tableau ne se nettoye pas (-_-)" car il ne test que le premier min max et pas les suivants .........
[/EDIT]

[Jasmine80]

Code :

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

my @tri = sort { $$b[3] <=> $$a[3] } @tab;

Ca ne fonctionne pas, @tri est identique à @tab.

Utilises-tu les pragmas 'strict' et 'warnings'? Si non, tu devrais.

[kioka]

heu bas pourtant quand je "print" mon tableau il est bien trié (ordre décroissant) sur la colonne 3 !?!

J'utilise normalement mais du coups je peut pas faire mon sort comme ça puisqu'il faut déclarer $a et $b. D'où je l'ai désactivé ....

[Jasmine80]

heu bas pourtant quand je "print" mon tableau il est bien trié (ordre décroissant) sur la colonne 3 !?!

J'utilise normalement mais du coups je peut pas faire mon sort comme ça puisqu'il faut déclarer $a et $b. D'où je l'ai désactivé ....

Oui, tu as raison, désolée, j'avais confondu mes 2 tableaux, ton code est correct.

Code :

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

my @tri = sort { $$b[3] <=> $$a[3] } @tab;

[kioka]

Pas grave
J'ai réussi à faire marché sort avec strict qui n'hurle pas

Mais je ne parviens pas à nettoyer mon tableau malgré tout

[Jasmine80]

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#!/usr/local/bin/perl
 
 
use strict;
use warnings;
 
 
my @tab = (
	[11502,	15202],
	[12010, 15202],
	[11725,	14536],
	[11502, 13256],
	[25312,	45258],
);
 
 
 
# trier mon tableau en fonction de la première puis de la seconde valeur
my @tri = map { $_} 
  sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] }
  map { [ @{$_}] } @tab;
 
 
 
 
 
for my $i (0..$#tri){
	print "$i $tri[$i][0] $tri[$i][1]\n";
}
=h
@tri vaut bien :
0 11502 13256
1 11502 15202
2 11725 14536
3 12010 15202
4 25312 45258
=cut
 
 
for my $i (0..$#tri-1){
 
	print "$tri[$i][0] $tri[$i+1][0]\n";
 
	if ($tri[$i][0] == $tri[$i+1][0]){
		delete $tri[$i];
	}
	elsif ($tri[0][1] > $tri[1][1]){
		delete $tri[$i+1]; 
		# il faudrait un $i ++
		# afin de passer directement à la comparaison $i+2 vs $i+3
		# car $i+1 vs $i+2 impossible car $i+1 supprimé
	}
}
 
for my $i (0..$#tri){
	print "$i $tri[$i][0] $tri[$i][1]\n";
}

Je pensais à un code dans ce genre, mais l'ennui est qu'il faudrait pouvoir modifier $i ... il y a moyen, mais je ne sais plus comment.

[Jasmine80]

J'ai trouvé mon erreur

Code :

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

elsif ($tri[0][1] > $tri[1][1]){

doit être

Code :

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

elsif ($tri[$i][1] > $tri[$i+1][1]){

... ça nettoie bien une partie du tableau mais pas tout, il reste 3 12010 15202 en trop

Code :

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

1
2
3
4
5
0  
1 11502 15202
2  
3 12010 15202
4 25312 45258

[Jasmine80]

Code :

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

elsif ($tri[$i][1] >= $tri[$i+1][1]){

il manque aussi un égal

[Jasmine80]

Code :

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

1
2
3
4
5
6
@tri vaut bien :
0 11502 13256
1 11502 15202
2 11725 14536
3 12010 15202
4 25312 45258

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/local/bin/perl
 
 
use strict;
use warnings;
 
 
my @tab = (
	[11502,	15202],
	[12010, 15202],
	[11725,	14536],
	[11502, 13256],
	[25312,	45258],
);
 
 
 
# trier mon tableau en fonction de la première puis de la seconde valeur
my @tri = map { $_} 
  sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] }
  map { [ @{$_}] } @tab;
 
 
for my $i (0..$#tri-1){
 
	print "$i vs ".($i+1)."\t(@{$tri[$i+1]} vs @{$tri[$i+1]})\n";
	if ($tri[$i][0] == $tri[$i+1][0]){
		delete $tri[$i];
		print "suppression de $i\n";
	}
	elsif ($tri[$i][1] >= $tri[$i+1][1]){
		delete $tri[$i+1]; 
		print "suppression de ".($i+1)."\n";
 
		# il faudrait comparer $i à $i+2 dans le cycle suivant
               # vu que $i+1 vient d'être supprimé
               # ($i de ce tour ci donc $i-1 à $i+1 du tour suivant)
	}
}
 
for my $i (0..$#tri){
	print "$i $tri[$i][0] $tri[$i][1]\n";
}

0 vs 1 (11502 15202 vs 11502 15202)
suppression de 0
1 vs 2 (11725 14536 vs 11725 14536)
suppression de 2
2 vs 3 (12010 15202 vs 12010 15202) => il faudrait faire 1 vs 3 (qui supprimerait 3)
3 vs 4 (25312 45258 vs 25312 45258)

Je pense que si tu arrives à modifier cela, mon code fonctionnera.
@tri final vaudra bien

Code :

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

1
2
3
4
5
0  
1 11502 15202
2  
3 
4 25312 45258

Je pars en vacances 6 jours, repos bien mérité

[kioka]

J'vais tenter le coups (^_^) merci pour ton aide et bonne vacances !

[Jasmine80]

J'vais tenter le coups (^_^) merci pour ton aide et bonne vacances !

Bonne chance pour ton code.

Je vais voir mon amie d'enfance qui habite en Normandie ... parait que le temps y est pourri, faudra que je prenne de gros pulls

Attends l'avis d'autres personnes, elles auront peut-être un module miracle à te conseiller ou une autre solution.

[kioka]

Merci bien et en effet prévois les gros pulls si j'en crois les commérages

[kioka]

enfin j'ai réussi !!!!

Pas sûr que ce soit la méthode la plus optimum mais bon au moins ça marche ...

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
22
23
24
25
26
my $j = 0;
while ($j != $#a_tri-1)
{
        # mes min et max
	my $min = $a_tri[$j][7];
	my $max = $a_tri[$j][8];
 
	my $i = 0;
	foreach my $el(@a_tri)
	{
		if(($$el[7] >= $min) and ($$el[8] < $max))
		{
			splice(@a_tri, $i, 1);
			$j = 0;
			$i-- if ($i > 0);
		}
		elsif(($$el[7] > $min) and ($$el[8] <= $max))
		{
			splice(@a_tri, $i, 1);
			$j = 0;
			$i-- if ($i > 0);
		}
		$i++;
	}
	$j++;
}

Si quelqu'un connais une solution plus optimale qui me le dise sans hésiter .... cela m'intéresse ....

[Jedai]

Ta solution a l'air non-optimale (O(n²) alors que le problème est probablement en O(n log n), ou O(n) si les tableau sont déjà triés). Mais d'abord je veux une précision : est-il acceptable que deux intervalles se chevauchent ? C'est à dire pour deux intervalles [a;b] et [c;d], doit-on supprimer [c;d] à partir du moment où (c appartient à [a;b] ou d appartient à [a;b]) ou uniquement si ([c;d] est inclus dans [a;b]) ?

--
Jedaï

[kioka]

Kikou !

O(n²) alors que le problème est probablement en O(n log n), ou O(n) si les tableau sont déjà triés

Le tableau est trié par ordre décroissant suivant la distance entre les bornes.

est-il acceptable que deux intervalles se chevauchent ?

Oui normalement je veux les garder et surtout pas les jeter .... d'où je n'ai pas demander ">= and <=" mais "> and <" ou "= and <" ou
"> and =", afin d'éliminer ces cas :
102 152
102 120 -> supprime
123 152 -> supprime
112 125 -> supprime

Je traite les chevauchement à part car comme j'ai dit mon tableau est pas former que de 2 colonnes en réelle et le sort des chevauchements va dépendre des autres colonnes ....

Je veux bien des astuces pour optimiser ce code en tout cas ! (^_^)

Merci ...