Je classe ce petit howto dans ma catégorie Linux, parce que c'est le seul véritable envirronnement pour développer du code. Quand Windows n'est fourni par défaut qu'avec Wordpad ou Notepad, Linux vient déjà avec des éditeurs de textes puissant en ligne de commande pour développer (Vim par exemple). Donc revenons à nos moutons: Je développe en ce moment un petit programme où il me faut comparer deux listes et trouver et identifier les éléments en commun (c'est le genre de trucs qu'on fait tous les jours en bioinformatiques :-) . Comme je manipule des chaines de caractères, j'ai fini par me tourner vers Perl. Perl est LE LANGAGE de script pour gérer les lignes de caractère. Une implémentation naïve de ce problème est quadratique. Mais si vous utilisez une table de hachage... alors ça devient linéaire YOUPI YOUPI YA: votre liste de 100000 éléments va pouvoir enfin être analysé. Voici la commande à utiliser:
my %seen;
my @common = grep {$seen{$_}++} @list_1 , @list_2;
Par contre cela nécessite que les listes une et deux ne comporte pas de doublé. Voyons un peu comment ça marche. J'utilise la fonction grep pour créer un filtre et je lis à la suite les deux listes. J'initialise d'abord ma petite table de hash en une table nulle. Lorsque je parcours les listes avec $_, lorsque je rencontre pour la première fois je rencontre un élément je le mets dans la table, mais comme la table est initialisée à faux à 0 au début, l'élément est filtré! Mais par post incrémentation je garde une trace de l'élément (le fameux ++). Lorsque l'élément apparait pour la seconde fois:
$seen{$_} est non nul et donc le filtre est passif. Vous récupérer enfin ce beau résultat dans votre table @common. Si je ne me trompe pas cette comparaison des deux tables est bien linéaire.
1 comment:
use strict;
use warnings;
use Data::Dumper;
my @a1 = (1, 2, 4, 6, 7, 8);
my @a2 = (1, 2, 3, 5, 6, 7);
print join "\t", @a1;
print "\n";
print join "\t", @a2;
print "\n";
print "\n";
print "###########################\n";
print "Elément dans un tableau et pas dans l'autre \n\n";
&different (\@a1,\@a2);
print "###########################\n";
print "Elément dans un tableau et pas dans l'autre \n\n";
&different (\@a2,\@a1);
print "###########################\n";
print "Eléments commun au 2 tableaux \n\n";
my %seen;
my @common = grep {$seen{$_}++} @a1 , @a2;
print Dumper @common;
print "\tNb Commun : ".scalar @common ."\n";
print "###########################\n";
sub different{
my $ref1=shift;
my $ref2=shift;
my @a1=@$ref1;
my @a2=@$ref2;
my %a;
map($a{$_}=1,@a1); # create %a with elements from @a1
my @diff=grep(!defined($a{$_}),@a2); # returns those elements of @a2 that +don't
# have a hash element in %a1 therefore they
# do not exist in @a1.
print Dumper @diff;
print "\tNb Diff : ".scalar @diff ."\n";
}
Post a Comment