Discussion :

[vidici]

ce qui donne chez moi

lolo -> tri alphabetique
moosebis: time sort sorted.txt > genetic_sorted.txt
real 0m5.436s
user 0m2.297s
sys 0m0.679s
lolo -> traitement
moosebis: time perl lolo.pl genetic_sorted.txt > genetic_result.txt
real 0m3.253s
user 0m2.259s
sys 0m0.214s

wc genetic_result.txt
2130535 2130535 55701458 genetic_result.txt

et pour moi

time perl genes.pl sorted.txt > vidici_result.txt
real 1m7.602s
user 1m3.487s
sys 0m1.841s
wc vidici_result.txt
2130535 2130535 55701458 vidici_result.txt
tu l'emportes nettement, c'est sur.

[Lolo78]

Bonsoir Vidici,

Ah oui, je pensais avoir utilisé la dernière version de ton code.

J'ai réessayé avec le say directement dans la boucle:

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
 
#!/usr/bin/perl
use strict;
use warnings;
use feature qw /say/;
my $ad="genetic.txt";
open my $FILE, '<', $ad or die "$ad : $!\n\n";
my %tout;
while (my $v = <$FILE>) {
     chomp $v;
     my $n = length($v); 
     my $s = $v;
     for (my $var = $n; $var > 0; $var--) {
         $s = substr($s,0,$var);
         if ( (exists( $tout{$s} ))) {
             my @tob = $tout{$s};
             push($tob[0], $v);
             last;
         }
     } 
     if ( (!exists( $tout{$s} ))) {
          say $v;
          my @tab;
          push(@tab, $v);
          $tout{$v} = [@tab];
     }
}

L'amélioration des performances semble exister mais n'est pas flagrante:

Code :

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

1
2
3
real    0m38.600s
user    0m38.032s
sys     0m0.545s

A vrai dire, je doutais fortement que cette boucle finale prît tant de temps que cela. A vue de nez, c'est la boucle:

Code :

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

1
2
3
4
5
6
7
8
     for (my $var = $n; $var >= 23; $var--) {
         $s = substr($s,0,$var);
         if ( (exists( $tout{$s} ))) {
             my @tob = $tout{$s};
             push($tob[0], $v);
             last;
         }
     }

exécutée 3,3 millions de fois qui doit prendre beaucoup de temps.

Ceci m'amène à une autre amélioration possible. En remarquant que la ligne la plus courte du fichier d'Isabella fait 23 caractères, je constate que je ne peux trouver dans le hash %tout de chaîne d'une longueur inférieure à 23 caractères et je modifie donc la boucle for en question comme suit:

Code :

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

1
2
 
for (my $var = $n; $var >= 23; $var--) {

Le résultat est toujours identique, mais les performances sont nettement améliorées:

Code :

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

1
2
3
4
 
real    0m18.450s
user    0m18.018s
sys     0m0.420s

Comme cette boucle doit encore prendre beaucoup de temps, je regarde plus en détail ce qu'elle fait exactement, et constate que le tableau @tob ne sert en fait à rien: c'est une variable lexicale locale au bloc if, et cette variable n'est en fait jamais utilisée. Donc, je modifie la boucle for comme suit (j'ajoute un peu de simplification syntaxique):

Code :

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

1
2
3
4
5
 
     for (my $var = $n; $var >= 23; $var--) {
         $s = substr $s, 0, $var;
         last if exists $tout{$s} ;
     }

Nouvelle amélioration, pas extraordinaire cette fois, mais néanmoins non négligeable des performances (avec toujours un résultat identique):

Code :

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

1
2
3
4
 
real    0m16.460s
user    0m16.068s
sys     0m0.373s

Tant que j'y suis, je regarde le bloc if qui suit:

Code :

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

1
2
3
4
5
6
 
            if ( (!exists( $tout{$s} ))) {                 
            my @tab;                                       
            push(@tab, $v);                                
            $tout{$v} = [@tab];                            
    }

et remarque qu'il est également inutile d'alimenter le tableau @tab. Un peu de simplification syntaxique complémentaire ne fera pas de mal et devrait améliorer encore un peu les performances, même si ça devient sans doute presque anecdotique:

Code :

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

1
2
3
4
5
 
     if ( (!exists( $tout{$s} ))) {
          say $v;
          $tout{$v} = [$v];
     }

Ce qui donne toujours le même résultat et les durées d'exécution suivantes:

Code :

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

1
2
3
4
 
real    0m15.310s
user    0m15.006s
sys     0m0.295s

Pas mal, quand même, je suis passé de 42 secondes à 15 secondes. Et puis le code est passé de 35 lignes à 20 lignes, j'ai la faiblesse de croire que ça le rend plus compréhensible et plus facile à maintenir. En ce qui me concerne, en tous cas, je me demandais confusément à quoi servaient les variables @tab et @tob, je suis content d'avoir pu les éliminer. Le code de ton programme me paraît maintenant beaucoup plus clair et compréhensible.

Mais là, je suis à court d'idées sur un simple exercice de relecture de code. Pour essayer d'optimiser plus, il faut utiliser un profileur de code afin de déterminer les lignes de codes qui prennent beaucoup de temps et voir si on peut les améliorer. Je te conseille d'essayer http://search.cpan.org/~timb/Devel-N...vel/NYTProf.pm. Il te dira les lignes du code qui prennent le plus de temps, ce qui te permettra (peut-être) de trouver des moyens de les optimiser. Je viens de passer presque deux heures à faire les tests et répondre à ton post, j'arrête et vais bientôt me coucher. A toi d'essayer NYTprof si le cœur t'en dit.

Après, il y a un point où il faut parfois cesser d'optimiser un algorithme, mais éventuellement penser à un autre algo. Je pense que le mien est intrinsèquement nettement plus rapide, sauf, bien sûr, qu'avec les données fournies en entrée par Isabella, il me fallait retrier autrement les données (14 secondes, au total on est donc dans les mêmes ordres de grandeurs que ton programme sans tri, mais cela tient surtout au fait qu'Isabella avait fait le tri dans un certain ordre marchant avec ton algo, alors que le mien avait besoin d'un autre ordre de tri).

Je ne sais pas si Isabella repassera ici, mais j'espère au moins que ce post te sera utile et t'aura appris quelque chose.

En post-scriptum, ma version finale de ton code, incluant toutes les modif proposées ci-dessus et donnant toujours le même résultat:

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
 
#!/usr/bin/perl
use strict;
use warnings;
use feature qw /say/;
my $ad="genetic.txt";
open my $FILE, '<', $ad or die "$ad : $!";
my %tout;
while (my $v = <$FILE>) {
     chomp $v;
     my $n = length($v); 
     my $s = $v;
     for (my $var = $n; $var >= 23; $var--) {
         $s = substr $s, 0, $var;
         last if exists $tout{$s} ;
     } 
     if ( !exists $tout{$s} ) {
          say $v;
          $tout{$v} = [$v];
     }
}

Bonne nuit.

[Lolo78]

ce qui donne chez moi

lolo -> tri alphabetique
moosebis: time sort sorted.txt > genetic_sorted.txt
real 0m5.436s
user 0m2.297s
sys 0m0.679s
lolo -> traitement
moosebis: time perl lolo.pl genetic_sorted.txt > genetic_result.txt
real 0m3.253s
user 0m2.259s
sys 0m0.214s

wc genetic_result.txt
2130535 2130535 55701458 genetic_result.txt

et pour moi

time perl genes.pl sorted.txt > vidici_result.txt
real 1m7.602s
user 1m3.487s
sys 0m1.841s
wc vidici_result.txt
2130535 2130535 55701458 vidici_result.txt
tu l'emportes nettement, c'est sur.

Je n'avais pas vu ce message quand j'ai posté mon long message précédent.

Je ne cherche vraiment pas à "l'emporter", mais juste à communiquer les idées que m'ont données l’expérience.

Bon, là, je vais vraiment aller dormir. @ +

[vidici]

Ceci m'amène à une autre amélioration possible. En remarquant que la ligne la plus courte du fichier d'Isabella fait 23 caractères, je constate que je ne peux trouver dans le hash %tout de chaîne d'une longueur inférieure à 23 caractères et je modifie donc la boucle for en question comme suit:

Code :

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

1
2
 
for (my $var = $n; $var >= 23; $var--) {

En fait je ne voulais pas présupposer de la taille des séquences. Mais tu as raison, j'avais négligé l'importance de l'effet sur la conséquence .

Pas mal, quand même, je suis passé de 42 secondes à 15 secondes. Et puis le code est passé de 35 lignes à 20 lignes, j'ai la faiblesse de croire que ça le rend plus compréhensible et plus facile à maintenir. En ce qui me concerne, en tous cas, je me demandais confusément à quoi servaient les variables @tab et @tob, je suis content d'avoir pu les éliminer. Le code de ton programme me paraît maintenant beaucoup plus clair et compréhensible.

vu pour tab et tob. En fait c'est une erreur que je fait souvent des que je manie des références. ça m'aide à matérialiser l'idée du tableau dans le Hash. Quand je t'ai demandé de revoir le code, je savais que tu allais avoir une autre, une meilleure façon de voir les choses et je te remercie de 'avoir communiquée. Ce n'était pas temps l'optimisation qui m'intéressait mais la simplification et la clarification. Si Isabelle repasse par là, comme tu dis, elle pourra avoir une version fiable. Car au final j'aime bien ma façon de faire, elle offre d'autres possibilités en aval. Bon, Bonne nuit et merci.

[vidici]

J
Je ne cherche vraiment pas à "l'emporter", mais juste à communiquer les idées que m'ont données l’expérience.

Pas de souci la dessus. Je l'ai bien compris.

[Philou67430]

Je ne sais pas sur quelles bécanes vous tournez, mais si je lance le script de vidici (pas la dernière version, mais une des premières), ou mes variantes et autres implémentations, elles tournent toutes en au moins 7mn ! (pour un résultat semblant identique en terme de nombre de ligne du résultat).

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
$ for s in *.pl ; do time perl $s -file=sorted_length_pool_piRNA_embryo_02h_GSM12.txt ; done
perl root_seq.pl -file=sorted_length_pool_piRNA_embryo_02h_GSM12.txt
3305904 sequences in array : OK !
Min length : 23
Sequences: 100% [======================================================================================================= ]D 0h07m03s
real    7m16.784s
user    7m12.465s
sys     0m3.961s
 
perl vidici.pl -file=sorted_length_pool_piRNA_embryo_02h_GSM12.txt
Sequences: 100% [======================================================================================================= ]D 0h07m32s
real    7m50.033s
user    7m47.690s
sys     0m1.419s
 
perl vidici-ple.pl -file=sorted_length_pool_piRNA_embryo_02h_GSM12.txt
3305904 sequences in array : OK !
Sequences: 100% [======================================================================================================= ]D 0h07m10s
real    7m13.588s
user    7m12.044s
sys     0m0.826s

[Isabella83]

Merci beaucoup à tous pour votre aide !
J'ai beaucoup appris grâce à vous ! C'est très utile de lire les lignes codes des autres !