Discussion :

[dreydrey]

Bonjour,

J'ai un tableau qui contient des hachages (pour faire simple) et je voudrais éliminer les doublons du tableau (c'est à dire les hachages identiques). Pour le moment, je ne trouve rien qui puisse m'aider. Quelqu'un a une idée ?
Merci

Audrey

[djibril]

j'ai un script qui permet de supprimer les doublons d'un tableau, je l'ai jamais essayé sur les hash.
mais peux tu mieuw expliquer ton souci. Ca ressemble à quoi on tableau de hash

[gege2061]

Bonjour,

J'ai un tableau qui contient des hachages

Qu'est ce que tu appel des hachages? Parce qu'une table de hachage permet ceci :
Comment définir et utiliser une table associative ?

[dreydrey]

OK, alors mes hâchages ont cette forme là, par exemple

Code :

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

1
2
3
4
5
6
7
8
9
%ligne1=("time"=>1000, "duree"=>"100", nom=>"secteur");
%ligne2=("time"=>1000, "duree"=>"100", nom=>"autrechose");
%ligne3=("time"=>1000, "duree"=>"100", nom=>"secteur");
%ligne4=("time"=>2000, "duree"=>"200", nom=>"secteur");
 
push(@tableau,{%ligne1});
push(@tableau,{%ligne2});
push(@tableau,{%ligne3});
push(@tableau,{%ligne4});

Donc je récupère le tableau @tableau et je voudrais en enlever les doublons, icic, la ligne 1 et la ligne 2.
J'ai trouvé des trucs pour faire ça, mais sur des scalaires seulement, et ça ne marche pas dans mon cas. En plus, je ne sais même pas comparer les hachages entre eux. Bref, j'y arrive pas quoi.

Audrey

[djibril]

tu veux dire supprimer ligne 1et ligne 3?

[dreydrey]

non, juste une sur 2 n'importe laquelle. Ah j'oubliais le tableau est ordonné selon le clé "time" des hâchages (mais je pense pas que ce soit important).

[djibril]

non, je voulais dire que les lignes identiques sont la 1 et 3??? et tu souhaite en suprimer une des deux??

[dreydrey]

oui, voilà, c'est exactement ce que je veux faire.
Désolée de pas avoir été claire

[djibril]

je t'ai fais une fonction qui te renvoie identique ou different losque que tu lui soumme deux hash.
Tu peux déjà faire un truc avec. Je continue à chercher un bon algo.
voilà pour l'instant :

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
 
 
my %ligne1=("time"=>1000, "duree"=>"100", nom=>"secteur");
my %ligne2=("time"=>1000, "duree"=>"100", nom=>"autrechose");
my %ligne3=("time"=>1000, "duree"=>"100", nom=>"secteur");
my %ligne4=("time"=>2000, "duree"=>"200", nom=>"secteur");
 
#compare %ligne1 et %ligne2
print &compare_hash(\%ligne1,\%ligne3);
 
sub compare_hash {
	my $hash1 = shift;
	my $hash2 = shift;;
	my $ok = "identique";
	my $no_ok = "different";
	if (scalar keys %$hash1 != scalar keys %$hash2) {
		return $no_ok;
		exit;
	}
	foreach my $cle (keys %$hash1) {
		if (! $$hash2{$cle} ){
			return $no_ok;
			exit;
		}elsif ($$hash1{$cle} ne $$hash2{$cle}) {
		  return $no_ok;
		  exit;	
		}	
	}
return $ok;	
}

[djibril]

je ne sais pas combien t'as de hash en tout, mais plus t'en as, plus il te faura de comparaison donc de temps d'execution.
Petit calcul math.
4 hash à comparer entre eux => 6 comparaison max
5 hash => 10 comparaison max
6 hash => 15 comparaison max

soit [n * (n-1)]/2 comparaison max à faire.
donc en fonction de ses qq remarques, revoit ton algo.

[dreydrey]

Ok merci, c'est un 1er pas., ç ame parait assez clair. Tous mes hash ont les mêmes clés donc je vais passer directement à l'étape 2 de la comparaison valeur après valeur.
Je pense que je vais faire un algo à 2 boucles qui remplit un 2ème tableau au fur et à mesure et qui vérifie à chaque fois. Par contre, mon tableau à des milliers d'entrées, c'est clair que ça prendre du temps, mais bon, je verrai.
Merci en tout cas.
Audrey

[tfe]

Je pense qu en utilisant
sort

Code :

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

 perldoc -f sort

et en comparant l element en cours avec le precedant y a moyen de faire quelque chose de plus performant

[dreydrey]

Effectivement, c'était très très long, j'ai arrêté après une 30aine de minutes.

L'idée d'utiliser sort est pas mal, du coup, ce que j'essaie maintenant, c'est de trier mon tableau sur toutes les clés.

Code :

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

@tableau = sort {$a->{time} <=> $b->{time} or $a->{image} cmp $b->{image} or $a->{nom} cmp $b->{nom}} @tableau;

Puis je parcoure ce tableau, et ajoute chaque ligne à un tableau de résultat (@res) sauf si la ligne est identique à la dernière ligne de res (en utilisant la fonction compare_hash).

Pour le moment j'ai un bug, mais ça ne devrait pas tarder à marcher, en tout cas, le temps à l'air correct.

Voilà !

[djibril]

si ton script n'est pas tres long, tu peux nous le montrer, y a peut etre moyen de l'optimiser!

[dreydrey]

Bien sûr, le voilà :

Fonction enleveDoublons :

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
sub enleveDoublons{
  my @tableau=@_;
  @tableau = sort {$a->{time} <=> $b->{time} or $a->{image} cmp $b->{image} or $a->{nom} cmp $b->{nom}} @tableau;
 
  my @res;
  push(@res,$tableau[0]);
 
  for(my $i=1;$i<@tableau;++$i){
      if( ! same_hash($tableau[$i],$res[$#res])){
        push(@res,$tableau[$i]);
      }
  }
  return @res;
 
}

et la fonction same_hash :

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
sub same_hash {
   my $hash1 = shift;
   my $hash2 = shift;;
 
   if (scalar keys %$hash1 != scalar keys %$hash2) {
      return 0;
      exit;
   }
 
   foreach my $cle (keys %$hash1) {
      if (! $$hash2{$cle} ){         
         return 0;
         exit;
      }elsif ($$hash1{$cle} ne $$hash2{$cle}) {        
        return 0;
        exit;
      }
   }
return 1;
}

ça marche très bien et dans un temps très respectable !
:-)

[djibril]

ton script me plait bien et est bien ecrit. Juste une remarque.
Je me demande si tu ne loupe pas des étapes!!!
Etant donné qu'avant de faire ton push, tu compares ton hash au dernier de ta liste, il peux s'avérer que ton hash soit identique à l'avant des hash de ta liste et du coup, tu le loupera et t'aura des doublons!!!
verifie ton algo 8)

[dreydrey]

mmmm... je sais pas, vu que je trie le tableau avant, du coup les lignes doublons sont forcément consécutives dans le tableau @tableau, non ?

Tu penses à un cas particulier où ça ne marcherait pas ?

Sinon, dans la pratique, ça a l'air de marcher.

Merci en tout cas

[djibril]

mmmm... je sais pas, vu que je trie le tableau avant, du coup les lignes doublons sont forcément consécutives dans le tableau @tableau, non ?

Tu penses à un cas particulier où ça ne marcherait pas ?

Sinon, dans la pratique, ça a l'air de marcher.

Merci en tout cas

C'est vrai que les lignes doublons seront consécutives dans le tableau mais peut etre pas forcement en fin de tableau non!!!!!

[dreydrey]

Ben non, j'arrive pas à voir (ce qui ne veut pas dire que j'ai raison)

Les push, ça ajoute les lignes à la fin du tableau @res, non ?
Si on imagine :

Code :

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

1
2
3
4
5
$tableau[0]={time=>1000, nom=>"nom1",image=>"secteur"};
$tableau[1]={time=>1000, nom=>"nom1",image=>"secteur"};
$tableau[2]={time=>2000, nom=>"nom1",image=>"secteur"};
$tableau[3]={time=>2000, nom=>"nom2",image=>"secteur"};
$tableau[4]={time=>2000, nom=>"nom2",image=>"secteur"};

quand $i=1 alors

Code :

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

$res[0]={time=>1000, nom=>"nom1",image=>"secteur"};

On compare $tableau[1] et $res[0] -> ce sont les mêmes donc on n'ajoute pas la ligne à @res.

quand $i=2 , @res n'a pas changé, on compare $tableau[2] à $res[0], ils sont différents.
On ajoute la ligne à @res

quand $i=3

Code :

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

1
2
$res[0]={time=>1000, nom=>"nom1",image=>"secteur"};
$res[1]={time=>2000, nom=>"nom1",image=>"secteur"};

on compare $tableau[3] à $res[1], ils sont différents, on ajoute la ligne à @res

quand $i=4

Code :

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

1
2
3
$res[0]={time=>1000, nom=>"nom1",image=>"secteur"};
$res[1]={time=>2000, nom=>"nom1",image=>"secteur"};
$res[2]={time=>2000, nom=>"nom2",image=>"secteur"};

on compare $tableau[4] à $res[2], ils sont identiques, donc on n'ajoute pas la ligne.

A la sortie de la boucle, on a donc @res=

Code :

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

1
2
3
$res[0]={time=>1000, nom=>"nom1",image=>"secteur"};
$res[1]={time=>2000, nom=>"nom1",image=>"secteur"};
$res[2]={time=>2000, nom=>"nom2",image=>"secteur"};

Et ça marche, non ?

Ou peut être que push ne place pas la ligne à la fin du tableau ? Qu'est ce que je n'ai pas compris ?

[djibril]

je suis d'accord avec ton exemple qui marchera à merveille au fait! tres bon algo.
je me suis trituré l'esprit, mais au final, ton sort est efficace et empeche toute problematique en effet. Bien vu!