IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Perl Discussion :

[Optimisation] Recherche algorithme pour optimiser des recherches dans des tableaux


Sujet :

Langage Perl

  1. #1
    Responsable Perl et Outils

    Avatar de djibril
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    19 818
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 19 818
    Points : 499 183
    Points
    499 183
    Par défaut [Optimisation] Recherche algorithme pour optimiser des recherches dans des tableaux
    Bonjour,

    Je suis à la recherche d'une méthodologie pour optimiser une portion d'un programme qui à ce jour dure environ plus de 35 h. Le programme prend beaucoup de ressources, mais bon, de ce coté pas le choix. Il tourne sur un serveur de plus de 100 Go de RAM et 64 threads.

    Pour simplifier au maximum afin que vous compreniez mon souci, j'ai fait un petit programme d'exemple :

    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
    #!/usr/bin/perl
    use warnings;
    use strict;
     
    my @region = ( 1, 100 );
    my %data;
     
    my $start = 1;
    my $end = $start + 100;
    for my $num (1..1_000_000) {
    	$start = $end+1;
    	$end += 100;
     
    	$data{"seq$num"}{start} = $start;
    	$data{"seq$num"}{end} = $end;
    }
     
    print recherche_presence_1( \%data, \@region ),"\n";
     
    sub recherche_presence_1 {
    	my ( $ref_data, $ref_region ) = @_;
     
    	foreach my $cle ( sort { $ref_data->{$a}{start} <=> $ref_data->{$b}{start} } keys %{$ref_data} ) {
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
    Ce script lit un hash qui ressemble à ceci (les positions sont aléatoires) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    (
    	'seq1' => { start => 0,    end => 50, },
    	'seq2' => { start => 10,   end => 150, },
    	'seq3' => { start => 100,  end => 200, },
    	'seq4' => { start => 150,  end => 250, },
    	'seq5' => { start => 500,  end => 1000, },
    	'seq6' => { start => 600,  end => 900, },
    	'seq7' => { start => 800,  end => 950, },
    	'seq8' => { start => 1000, end => 2000, },
    )
    j'ai une région my @region = ( 1, 100 ); qui contient une position de début et une position de fin. Le but est de savoir si ma région chevauche une de mes régions de mon hash. Le simple programme ci-dessus dure 12 secondes et je souhaite une méthode pour aller plus vite car le problème est que dans mon programme, le hash contient des millions de régions à tester ET le test s'effectue des centaines de milliers de fois. Vous comprenez donc que le temps de calcul prends un coup sur la tête .
    Ma méthode actuelle boucle toujours sur toutes les régions à tester. Il y a peut-être un moyen de filtrer la liste où faire les tests sans perdre au final en performance, bref tout aide est la bienvenue

    d'avance !

  2. #2
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Bonjour,

    il faudrait que j'y réfléchisse plus, et je n'ai pas le temps maintenant, mais je me demande si une autre structure de données et une recherche dichotomique ne serait pas plus efficace dans ce cas de figure.

    Je regarderai plus en détail ce soir.

    Laurent.

  3. #3
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Est-ce que les intervalles de ton hash sont plus ou moins bornés, ou les valeurs sont-elles réellement aléatoires?

  4. #4
    Responsable Perl et Outils

    Avatar de djibril
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    19 818
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 19 818
    Points : 499 183
    Points
    499 183
    Par défaut
    les valeurs sont vraiment aléatoires, du moins, elles sont issues d'une autre analyse donc je n'ai aucun contrôle dessus. Elles peuvent chevaucher entre elles.

  5. #5
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Djibril,

    à quoi sert le tri effectué ici dans la ligne ci-dessous?
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    foreach my $cle ( sort { $ref_data->{$a}{start} <=> $ref_data->{$b}{start} } keys %{$ref_data} ) {
    Il me semble que l'algorithme marchera de la même façon sans ce tri. Or ce tri prend beaucoup de temps. J'ai lancé ton programme avec et sans le tri, la durée d'exécution passe de :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    real    0m15.211s
    user    0m14.959s
    sys     0m0.249s
    à :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    real    0m3.953s
    user    0m3.603s
    sys     0m0.343s
    Et si tu fais ce tri des millions de fois, alors c'est vraiment très pénalisant.

    Si, contrairement à mon impression, tu as vraiment d'accéder au hash sur des valeurs triées selon la date de début, alors ne fais le tri qu'une seule fois avant de commencer tes recherches et stocke tes clefs triées dans un tableau. Quelque chose du genre:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    my @sorted_keys = sort { $data{$a}{start} <=> $data{$b}{start} } keys %data;
    Et ensuite, dans ta fonction:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    sub recherche_presence_1 {
    	my ( $ref_data, $ref_region, $ref_sorted_keys ) = @_;
     
    	foreach my $cle ( @$ref_sorted_keys ) {
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
                    # ...
             # ...
    }
    A vue de nez, tu pourrais peut-être gagner un facteur de 3 ou 4, ce qui serait déjà pas mal. (Sauf si ne j'ai rien compris à ton programme.)

    Tu pourrais peut-être gagner encore un facteur d'environ 2 en analysant @sorted_keys avant de commencer pour ne faire les recherches qu'à partir de l'endroit approximatif dans ce tableau où les débuts d'intervalles sont supérieurs ou égaux au début de la région que tu analyses.

    Je continue à réfléchir à une structure de données qui éviterait de devoir examiner toutes les clefs. J'ai bien une idée pour trouver rapidement soit le début, soit la fin, soit même les deux, mais je ne vois pas pour l'instant comment les combiner pour focaliser la recherche sur la seule zone intéressante.

  6. #6
    Responsable Perl et Outils

    Avatar de djibril
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    19 818
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 19 818
    Points : 499 183
    Points
    499 183
    Par défaut
    Bonsoir lolo,

    Merci pour ta réponse. Sincèrement, le tri ne me sert à rien. Il a fait apparition pendant mes recherches d'une solution optimale, donc en l’enlevant, je gagnerai surement un peu de temps.

  7. #7
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Ben, il pourrait quand même te servir pour limiter le nombre de valeurs à vérifier.

    Supposons que tu fasses ce tri avant de commencer à étudier tes régions, comme je l'ai suggéré:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    my @sorted_keys = sort { $data{$a}{start} <=> $data{$b}{start} } keys %data;
    Tu as ici un million d'éléments, maintenant triés sur la valeur de début. Tu analyses le tableau @sorted_array et mets dans un hachage
    les valeurs de début correspondant, par exemple, aux indices 100000, 200000, 300000, ... 900000.

    Du coup, quand tu analyses une région dont la valeur de début est supérieure à la valeur correspondant à l'indice 500000, tu sais que
    tu ne dois examiner les clefs que pour la tranche de tableau @sorted_array[500000..1000000]:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    	foreach my $cle ( @$ref_sorted_keys[500000..$size_array] ) {
    		my $start = $ref_data->{$cle}{start};
           # ...
    ce qui divise par deux le nombre de clés à examiner et donc le travail de recherche à effectuer pour cette région.

    Et en moyenne, sur beaucoup de recherches de région, ça devrait aussi diviser par presque deux le travail de la fonction. C'est déjà pas mal comme gain.

  8. #8
    Expert éminent Avatar de CosmoKnacki
    Homme Profil pro
    Justicier interdimensionnel
    Inscrit en
    Mars 2009
    Messages
    2 848
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente Maritime (Poitou Charente)

    Informations professionnelles :
    Activité : Justicier interdimensionnel

    Informations forums :
    Inscription : Mars 2009
    Messages : 2 848
    Points : 6 535
    Points
    6 535
    Par défaut
    Du coup, quand tu analyses une région dont la valeur de début est supérieure à la valeur correspondant à l'indice 500000, tu sais que
    tu ne dois examiner les clefs que pour la tranche de tableau @sorted_array[500000..1000000]:
    Ce n'est pas forcément vrai car les clefs sont basées sur les valeurs de départ des régions du hash, or vu que leur taille est inconnue, la seule région du hash pouvant chevaucher la région soumise peut très bien démarrer avant 500000.

    Ceci dit on peut pallier au problème en triant les régions du hash selon leur fin ou en utilisant la valeur de fin de la région soumise.
    Brachygobius xanthozonus
    Ctenobrycon Gymnocorymbus

  9. #9
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Bonjour CosmoKnacki,

    soit tu n'as pas compris mes explications, soit c'est moi qui ne comprends pas ton objection.

    J'ai un tableau @t avec un million d'entrées, triées sur les valeurs de début des intervalles. Si ma valeur de début recherchée est supérieure à $t[500000], je n'ai plus qu'à rechercher entre $t[500000] et $t[999999], car je sais avec certitude que je ne la retrouverai pas dans la première moitié du tableau. Et je peux recommencer avec $t[750000], et ainsi de suite dans une bonne vieille recherche dichotomique.

    (Le modèle de données est un peu plus complexe, mon tableau trié est en fait un tableau de tableaux, mais c'est l'idée.)

    D'ailleurs, je vais présenter d'ici peu un script avec une telle recherche dichotomique, dès que j'aurai fait quelques mesures de performances.

    EDIT: tu as raison (), j'avais mal compris ton objection. Mais bon, comme tu le dis, on peut utiliser les données autrement (par ex. la valeur de fin au lieu de la valeur de début) pour obtenir le résultat escompté. (NB: ça ne change pas les résultats de mon test ci-dessous, car les données en entrée n'ont pas ce problème.)

  10. #10
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Hello,

    voici le résultat de mes tentatives avec une recherche dichotomique.

    Premier programme, celui de Djibril en ayant enlevé le sort dans la fonction de recherche et avec 20 régions dont la valeur de début sont nombres aléatoires compris entre 0 et 150.000.000.

    Voici le programme tel que légèrement modifié:
    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/bin/perl
    use warnings;
    use strict;
     
    my @regions = map {[$_, $_+100]} qw( 134458715 80746103 96630231 13838773 49918859 111965520 9780842 144196723 11342097 139116781 
                                         107776124 91911965 98959327 143561758 22508428 118145047 28069945 137091240 54322850 49024177 ); # nb: 20 nombres aléatoires inf à 150 M
    my %data;
     
    my $start = 1;
    my $end = $start + 100;
    for my $num (1..1_000_000) {
    	$start = $end+1;
    	$end += 100;
     
    	$data{"seq$num"}{start} = $start;
    	$data{"seq$num"}{end} = $end;
    }
     
    my $start_time = time;
     
    print " @$_ : ", recherche_presence_1( \%data, $_ ),"\n" for @regions;
     
    my $end_time = time;
    print "\n", time - $start_time, "\n";
     
    sub recherche_presence_1 {
    	my ( $ref_data, $ref_region ) = @_;
     
    	foreach my $cle ( keys %{$ref_data} ) {
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
    Affichage à l'exécution:
    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
     
    $ perl djibril2.pl
     134458715 134458815 : OUT
     80746103 80746203 : IN
     96630231 96630331 : IN
     13838773 13838873 : IN
     49918859 49918959 : IN
     111965520 111965620 : OUT
     9780842 9780942 : IN
     144196723 144196823 : OUT
     11342097 11342197 : IN
     139116781 139116881 : OUT
     107776124 107776224 : OUT
     91911965 91912065 : IN
     98959327 98959427 : IN
     143561758 143561858 : OUT
     22508428 22508528 : IN
     118145047 118145147 : OUT
     28069945 28070045 : IN
     137091240 137091340 : OUT
     54322850 54322950 : IN
     49024177 49024277 : IN
     
    21
    Donc, durée d'exécution de la recherche proprement dite (sans les initialisations): 21 secondes pour 20 recherches, environ une par seconde.

    Voici maintenant le programme avec recherche dichotomique:
    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
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
     
    #!/usr/bin/perl
    use warnings;
    use strict;
     
    my @regions = map {[$_, $_+100]} qw( 134458715 80746103 96630231 13838773 49918859 111965520 9780842 144196723 11342097 139116781 
                                         107776124 91911965 98959327 143561758 22508428 118145047 28069945 137091240 54322850 49024177 ); # nb: 20 nombres aléatoires inf à 150 M
    my %data;
     
    my $start = 1;
    my $end = $start + 100;
    for my $num (1..1_000_000) {
    	$start = $end+1;
    	$end += 100;
     
    	$data{"seq$num"}{start} = $start;
    	$data{"seq$num"}{end} = $end;
    }
     
    my @sorted_keys = map { [$_, $data{$_}{start}] } sort { $data{$a}{start} <=> $data{$b}{start} } keys %data;
    my $max = $#sorted_keys;
    my $start_time = time;
     
    for (1..5000) {
        print " @$_ : ", recherche_presence_1( \%data, $_ , \@sorted_keys),"\n" for @regions;
    }
     
    my $end_time = time;
    print "\n", ($end_time - $start_time), "\n";
     
    sub recherche_presence_1 {
    	my ( $ref_data, $ref_region, $sorted_ref ) = @_;
    	my $start_reg = $ref_region->[0];
    	my $min = search_min (0, $max, $start_reg, $sorted_ref);
     
     
    #	foreach my $cle ( sort { $ref_data->{$a}{start} <=> $ref_data->{$b}{start} } keys %{$ref_data} ) {
    #	foreach my $cle (keys %{$ref_data} ) {
        foreach my $range_val ($min..$max) {
        	my $cle = $sorted_ref->[$range_val][0];
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
     
    sub search_min {
    	# recherche dichotomique écourtée
        my ($first, $last, $start_reg, $sorted_ref) = @_;
        return $first if $first >= $last - 50;
        my $pivot = int (($first + $last)/2);
        if ($start_reg > $sorted_ref->[$pivot][1]) {
        	search_min ($pivot, $last, $start_reg, $sorted_ref);
        } elsif  ($start_reg < $sorted_ref->[$pivot][1]) {
        	search_min ($first, $pivot, $start_reg, $sorted_ref);
        } else {
        	return $first;
        }
    }
    Avec ce programme, ma durée d'exécution était systématiquement de 0. J'ai donc ajouté une boucle pour effectuer 5000 fois les 20 recherches (donc 100.000 recherches en tout). Voici son exécution (seulement la fin de l'affichage):

    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
     
    (...)
     9780842 9780942 : IN
     144196723 144196823 : OUT
     11342097 11342197 : IN
     139116781 139116881 : OUT
     107776124 107776224 : OUT
     91911965 91912065 : IN
     98959327 98959427 : IN
     143561758 143561858 : OUT
     22508428 22508528 : IN
     118145047 118145147 : OUT
     28069945 28070045 : IN
     137091240 137091340 : OUT
     54322850 54322950 : IN
     49024177 49024277 : IN
     134458715 134458815 : OUT
     80746103 80746203 : IN
     96630231 96630331 : IN
     13838773 13838873 : IN
     49918859 49918959 : IN
     111965520 111965620 : OUT
     9780842 9780942 : IN
     144196723 144196823 : OUT
     11342097 11342197 : IN
     139116781 139116881 : OUT
     107776124 107776224 : OUT
     91911965 91912065 : IN
     98959327 98959427 : IN
     143561758 143561858 : OUT
     22508428 22508528 : IN
     118145047 118145147 : OUT
     28069945 28070045 : IN
     137091240 137091340 : OUT
     54322850 54322950 : IN
     49024177 49024277 : IN
     
    5
    Donc, 100.000 recherches en 5 secondes, ou 20.000 par seconde. Tout de suite, ça va mieux.

    Bon, en fait, j'ai d'abord été très surpris de ce résultat dépassant toutes mes espérances. Mais j'ai eu beau cherché, je ne vois pas de bug et les deux programmes affichent bien les mêmes résultats. Donc, ça me paraît correct.

    En y regardant de plus près, je me suis rendu compte qu'en fait, la façon dont le hash construit les données en entrée est très très favorable à la stratégie de recherche dichotomique que j'ai employée: dès que l'on commence la recherche à proximité de l'indice où l'on va trouver la donnée, on la trouve très rapidement. Avec des données aléatoires ou pseudo-aléatoires, ça ira certainement beaucoup moins bien.

    On remarque aussi que l'on a sans doute pas besoin d'un hash, on pourrait probablement tout faire dans un tableau trié, mais je n'ai pas voulu changer cela pour rester au plus près qu programme existant.

    Il y a d'autres points de détails à améliorer, mais ça ne sert à rien d'aller plus loin, il faudrait des données plus réalistes pour faire des tests.

    Djibril, il y a une autre stratégie d'optimisation envisageable, qui sera peu ou très efficace selon le profil de tes données. Une fois les données triées par date de début, on pourrait les parcourir et fusionner au fur et à mesure les régions du hash qui se touchent ou se chevauchent, de façon à réduire le nombre de ces régions du hash. Selon le profil de tes données, tu réduiras plus ou moins considérablement le nombre de régions à vérifier (ou peut-être pas du tout si les données ne s'y prêtent pas). Il s'agirait de n'effectuer les recherches qu'après cet élagage du nombre de régions.

  11. #11
    Expert éminent Avatar de CosmoKnacki
    Homme Profil pro
    Justicier interdimensionnel
    Inscrit en
    Mars 2009
    Messages
    2 848
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente Maritime (Poitou Charente)

    Informations professionnelles :
    Activité : Justicier interdimensionnel

    Informations forums :
    Inscription : Mars 2009
    Messages : 2 848
    Points : 6 535
    Points
    6 535
    Par défaut
    Pour être plus clair, admettons que le hash de régions contienne seulement deux régions, disons (800100,900100) et (400100,500200) et que la région cherchée soit (500100,500200). Tu obtiendras dans le tableau trié (400100,500200) et (800100,900100) dans cet ordre (puisque le critère de tri est le début de l'intervalle). Ensuite, comme le début de l'intervalle recherché est 500100, tu te retrouveras à rechercher dans la mauvaise partie du tableau (c'est à dire entre $t[500000] et $t[999999] qui ne contiendra que la région (800100,900100)), et ce en excluant d'entrée de jeu la partie entre $t[0] et $[499999] qui elle seule contient la bonne région (c'est à dire (400100,500200) ).
    Brachygobius xanthozonus
    Ctenobrycon Gymnocorymbus

  12. #12
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Oui, CosmoKnacki, tu as raison (). J'étais d'ailleurs en train de mettre un ajout à mon post précédant (voir ci-dessus) pendant que tu as posté le tien.

    Mais cela ne change pas fondamentalement la stratégie envisagée.

  13. #13
    Expert éminent Avatar de CosmoKnacki
    Homme Profil pro
    Justicier interdimensionnel
    Inscrit en
    Mars 2009
    Messages
    2 848
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente Maritime (Poitou Charente)

    Informations professionnelles :
    Activité : Justicier interdimensionnel

    Informations forums :
    Inscription : Mars 2009
    Messages : 2 848
    Points : 6 535
    Points
    6 535
    Par défaut
    Non bien sûr, la méthode par dichotomie est toujours possible. À un moment j'avais pensé trier le tableau par taille d'intervalle décroissante et compter sur les probabilités (autrement dit une bonne étoile) pour sortir le chevauchement plus rapidement, mais ça dépend beaucoup de la manière dont se présente le hash de régions (si elles ont toutes plus ou moins la même taille c'est rappé).
    Brachygobius xanthozonus
    Ctenobrycon Gymnocorymbus

  14. #14
    Responsable Perl et Outils

    Avatar de djibril
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    19 818
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 19 818
    Points : 499 183
    Points
    499 183
    Par défaut
    Bonsoir à tous les deux,

    Eh beh, j'ai été tellement surpris du résultat de lolo que je me suis dis, j'espère que mon sujet de base était bien ce que j'ai, mais bon, on dirait.
    Je vais tout de même résumer la problématique, même si je pense que vous l'avez bien cerné.
    J'ai un hash qui contient des régions définies par leur start et end. On compte des millions d'entrées. Exemple :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    'region 1' =>  {
        'start' => 100,
        'end'   => 235,
    }
    'region 2' =>  {
        'start' => 250,
        'end'   => 600,
    }
    ...
    Donc, je peux avoir des millions de régions. Pour rebondir sur la remarque de lolo, les positions normalement ne se chevauchent pas. Donc, pas besoin de trouver un algorithme qui fusionnerait les régions.

    Ensuite, mon programme est amené à faire des milliers de tests sur ces régions. En fait, j'ai des milliers de séquences ayant chacune une position start et une position end. Le but est de savoir pour chacune de ces séquences si elle chevauche au moins une fois une des régions. Si c'est le cas, alors je considère que la séquence est IN. Si la séquence ne chevauche aucune région alors elle est out.
    Prenons pour exemple les deux régions ci-dessus et mes séquences seq1 = [50, 150], seq2=[300, 500], seq3=[240 245] seq4=[650, 750].
    seq1 est IN (chevauche region 1, seq2 est IN (chevauche region 2), seq3 et seq4 sont out car ne chevauchent rien.

    Voilà, je bien résumé je pense. Donc j'ai des milliers de séquences à tester sur des millions de régions et le tout est répété 2000 fois (car les données sont énormes).

    Donc au début, le programme a été conçu avec des vérifications simples :

    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
    sub recherche_presence_1 {
    	my ( $ref_data, $ref_region ) = @_;
     
    	foreach my $cle ( sort { $ref_data->{$a}{start} <=> $ref_data->{$b}{start} } keys %{$ref_data} ) {
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
    Problèmes de ce code :
    • il y a un sort qui ne sert à rien et alourdi le temps de calcul ;
    • on teste systématiquement les n régions avant celle qui va peut-être chevaucher ;
    • si notre séquence se situe avant la première région, on teste toutes les régions pour rien ;
    • si notre séquence se situe après la dernière région, on teste toutes les régions pour rien ;
    • temps de calcul très très long dans le contexte de volumétrie actuelle.


    Le but est de trouver un moyen plus rapide pour savoir s'il y a chevauchement ou non en réduisant au maximum le nombre de tests pour une recherche.
    Voici un programme reprenant ce qui a été fait :

    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
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    #!/usr/bin/perl
    use warnings;
    use strict;
    use List::MoreUtils qw( firstidx );
     
    my @regions = map {[$_, $_+100]} qw( 134458715 80746103 96630231 13838773 49918859 111965520 9780842 144196723 11342097 139116781 
                                         107776124 91911965 98959327 143561758 22508428 118145047 28069945 137091240 54322850 49024177 ); # nb: 20 nombres aléatoires inf à 150 M
     
    # Construction du hash
    my %data;
    my $start = 1;
    my $end = $start + 100;
    for my $num (1..1_000_000) {
    	$start = $end+1;
    	$end += 100;
     
    	$data{"seq$num"}{start} = $start;
    	$data{"seq$num"}{end} = $end;
    }
     
    print "DEBUT DES RECHERCHES\n";
    print "METHODE 1\n";
    my $start_time = time;
    print recherche_presence_1( \%data, $_ ),"\n" for @regions;
    my $duree = time - $start_time;
    print "DUREE : $duree\n";
     
    print "METHODE 2 sans sort\n";
    $start_time = time;
    print recherche_presence_2( \%data, $_ ),"\n" for @regions;
    $duree = time - $start_time;
    print "DUREE : $duree\n";
     
    print "METHODE 3 trie et bidouille\n";
    my @sorted_keys = sort { $data{$a}{start} <=> $data{$b}{start} } keys %data;
    my $ref_sorted_keys = \@sorted_keys;
     
    $start_time = time;
    print recherche_presence_3( \%data, $_, $ref_sorted_keys ),"\n" for @regions;
    $duree = time - $start_time;
    print "DUREE : $duree\n";
     
     
    sub recherche_presence_3 {
    	my ( $ref_data, $ref_region, $ref_sorted_keys ) = @_;
     
    	my $index_start = firstidx { $ref_region->[0] < $ref_data->{$_}->{'start'} and $ref_region->[1] < $ref_data->{$_}->{'start'} } @{ $ref_sorted_keys };
    	return 'OUT' if ($index_start == -1 or $index_start == 0);
    	$index_start -= 1 if ($index_start > 0);
     
    	foreach my $cle ( keys %{$ref_data} ) {
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
     
    sub recherche_presence_2 {
    	my ( $ref_data, $ref_region ) = @_;
     
    	foreach my $cle ( keys %{$ref_data} ) {
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
     
    sub recherche_presence_1 {
    	my ( $ref_data, $ref_region ) = @_;
     
    	foreach my $cle ( sort keys %{$ref_data} ) {
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
    Résultat :

    DEBUT DES RECHERCHES
    METHODE 1
    OUT
    IN
    IN
    IN
    IN
    OUT
    IN
    OUT
    IN
    OUT
    OUT
    IN
    IN
    OUT
    IN
    OUT
    IN
    OUT
    IN
    IN
    DUREE : 36
    METHODE 2 sans sort
    OUT
    IN
    IN
    IN
    IN
    OUT
    IN
    OUT
    IN
    OUT
    OUT
    IN
    IN
    OUT
    IN
    OUT
    IN
    OUT
    IN
    IN
    DUREE : 15
    METHODE 3 trie et bidouille
    OUT
    IN
    IN
    IN
    IN
    OUT
    IN
    OUT
    IN
    OUT
    OUT
    IN
    IN
    OUT
    IN
    OUT
    IN
    OUT
    IN
    IN
    DUREE : 14
    Méthode 1 avec sort = 36 secondes
    Méthode 2 sans sort = 15 sec, on gagne donc déjà pas mal de temps.
    Méthode 3 utilisant un trie préalable puis même méthode de recherche que la 1 sur une partie plus restreinte = 14 sec, on ne gagne pas grand chose.

    Reste à étudier le code dichotomique de lolo qui va me sauver la vie !

  15. #15
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    OK, avec les informations supplémentaires, je pense pouvoir faire mieux.

    Les régions sont disjointes, donc forcément relativement petites. Je pense qu'il serait intéressant de parcourir le hash des régions pour mesurer la taille maximale d'une région avant de commencer les recherches; ensuite, avec une recherche dichotomique et une taille maximale, on peut considérablement réduire le nombre de recherches.

    J'essaie de faire une nouvelle version basée sur ces hypothèses (et corrigeant la petite erreur de conception signalée par CosmoKnacki, qui ne gênait pas avec le jeu de test utilisé mais pourrait gêner dans d'autres cas).

  16. #16
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Salut Djibril,
    Bon, voilà, je crois que c'est bon. En tous cas, ça marche avec le jeu de test artificiel que nous avons, mais je pense que ça devrait aussi aller (et être spectaculaire) avec des données réelles.

    Voici le code:

    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
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
     
    #!/usr/bin/perl
    use warnings;
    use strict;
     
    my @regions = map {[$_, $_+100]} qw( 134458715 80746103 96630231 13838773 49918859 111965520 9780842 144196723 11342097 139116781 
                                         107776124 91911965 98959327 143561758 22508428 118145047 28069945 137091240 54322850 49024177 ); # nb: 20 nombres aléatoires inf à 150 M
    my %data;
     
    my $start = 1;
    my $end = $start + 100;
    for my $num (1..1_000_000) {
    	$start = $end+1;
    	$end += 100;
     
    	$data{"seq$num"}{start} = $start;
    	$data{"seq$num"}{end} = $end;
    }
     
    my @sorted_keys = map { [$_, $data{$_}{start}] } sort { $data{$a}{start} <=> $data{$b}{start} } keys %data;
     
    my $max_size = 0;
    $max_size = $data{$_}{end} - $data{$_}{end} > $max_size ? $data{$_}{end} - $data{$_}{end} : $max_size for keys %data;
     
    my $max = $#sorted_keys;
    my $start_time = time;
     
    for (1..5000) {
        print " @$_ : ", recherche_presence_1( \%data, $_ , \@sorted_keys),"\n" for @regions;
    }
     
    my $end_time = time;
    print "\n", ($end_time - $start_time), "\n";
     
    sub recherche_presence_1 {
    	my ( $ref_data, $ref_region, $sorted_ref ) = @_;
    	my $start_search = $ref_region->[0] - $max_size;
    	$start_search = 0 if $start_search < 0;
    	my $min = search_min (0, $max, $start_search, $sorted_ref);
    	my $end_search = $ref_region->[1];
     
    	foreach my $range_val ($min..$max) {
    		my $cle = $sorted_ref->[$range_val][0];
    		my $start = $ref_data->{$cle}{start};
    		my $end   = $ref_data->{$cle}{end};
    		return 'OUT' if  $ref_region->[1] < $start; # Optimisation essentielle sur fin d'intervalle
    		if (
    			   ( $ref_region->[0] >= $start and $ref_region->[0] <= $end )
    			or ( $ref_region->[1] <= $end   and $ref_region->[1] >= $start )
     
    		  )
    		{
    			return 'IN';
    		}
    	}
    	return 'OUT';
    }
     
    sub search_min {
    	# recherche dichotomique écourtée. (A un certain point,
    	# quand l'intervalle devient très petit, continuer la recherche
    	# dichotomique récursive est plus long que parcourir 
    	# séquentiellement l'intervalle restant. On peut donc 
    	# s'arrêter un peu avant d'avoir réduit l'intervalle à 1.)
        my ($first, $last, $start_reg, $sorted_ref) = @_;
        return $first if $first >= $last - 20;
        my $pivot = int (($first + $last)/2);
        if ($start_reg > $sorted_ref->[$pivot][1]) {
        	return search_min ($pivot + 1, $last, $start_reg, $sorted_ref);
        } elsif  ($start_reg < $sorted_ref->[$pivot][1]) {
        	return search_min ($first, $pivot - 1, $start_reg, $sorted_ref);
        } else {
        	return $pivot;
        }
    }
    Et voici son exécution (seulement la fin de l'affichage):

    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
     
     111965520 111965620 : OUT
     9780842 9780942 : IN
     144196723 144196823 : OUT
     11342097 11342197 : IN
     139116781 139116881 : OUT
     107776124 107776224 : OUT
     91911965 91912065 : IN
     98959327 98959427 : IN
     143561758 143561858 : OUT
     22508428 22508528 : IN
     118145047 118145147 : OUT
     28069945 28070045 : IN
     137091240 137091340 : OUT
     54322850 54322950 : IN
     49024177 49024277 : IN
     
    3
    J'en suis à 3 secondes pour 100.000 recherches.

    Mais l'important n'est pas cette amélioration de 5 à 3 secondes avec ce jeu de données de toute façon trop favorable à la recherche dichotomique mise en œuvre, c'est presque anecdotique, mais le fait que je pense que tu auras une amélioration vraiment spectaculaire avec un jeu de données réelles.

    Un mot d'explication:

    Supposons que la taille maximale de la région dans le hash soit 2000 (elle n'est pas codée en dur mais calculée par le programme avec les données présentes). Je limite la recherche des deux façons suivantes:
    - en dessous, en commençant la recherche dichotomique au début de la région en cours d'analyse moins la taille maximale d'une région du hash;
    - au dessus, avec cette ligne:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    return 'OUT' if  $ref_region->[1] < $start;
    qui arrête la recherche dès le début de la région recherchée est supérieur à la fin de la région du hash en cours d'analyse.

    J'ai hâte de connaître les résultats.

    Bonne soirée,
    Laurent.

  17. #17
    Responsable Perl et Outils

    Avatar de djibril
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    19 818
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 19 818
    Points : 499 183
    Points
    499 183
    Par défaut
    Lolo,

    J'essaye de comprendre ton code et te tiens au courant.

  18. #18
    Responsable Perl et Outils

    Avatar de djibril
    Homme Profil pro
    Inscrit en
    Avril 2004
    Messages
    19 818
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 19 818
    Points : 499 183
    Points
    499 183
    Par défaut
    Je ne comprends pas ce code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    $max_size = $data{$_}{end} - $data{$_}{end} > $max_size ? $data{$_}{end} - $data{$_}{end} : $max_size for keys %data;
    On aura systématiquement 0 non ?

  19. #19
    Expert éminent Avatar de CosmoKnacki
    Homme Profil pro
    Justicier interdimensionnel
    Inscrit en
    Mars 2009
    Messages
    2 848
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente Maritime (Poitou Charente)

    Informations professionnelles :
    Activité : Justicier interdimensionnel

    Informations forums :
    Inscription : Mars 2009
    Messages : 2 848
    Points : 6 535
    Points
    6 535
    Par défaut
    Une autre méthode qui joue sur la proximité des centres des intervalles:
    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
    my $middle = $region[0] + $region[1];
     
    my @sorted_keys = sort { abs($data{$a}{start} + $data{$a}{end} - $middle) <=>
                             abs($data{$b}{start} + $data{$b}{end} - $middle) } keys %data;
     
    my $ref_sorted_keys = \@sorted_keys;
     
    sub recherche_presence_1 {
        my ( $ref_data, $ref_region, $ref_sorted_keys ) = @_;
     
        foreach my $cle ( @{$ref_sorted_keys} ) {
            if (( $ref_region->[0] >= $ref_data->{$cle}{start} and $ref_region->[0] <= $ref_data->{$cle}{end} ) or
                ( $ref_region->[1] >= $ref_data->{$cle}{start} and $ref_region->[1] <= $ref_data->{$cle}{end} )) {
                return 'IN';
            }
        }
        return 'OUT';
    }
    L'idée est d'effectuer un tri croissant des intervalles selon la distance de chacun de leur centre à celui de la région recherchée de manière à tester les intervalles dont le centre est le plus proche en premier. Si la vitesse de convergence vers un potentiel intervalle chevauchant est peu prévisible, elle est plutôt bonne. Dans le pire des cas (pas d'intervalle chevauchant) la liste est simplement parcourue jusqu'à la fin.
    Si la taille des intervalles a une limite maximum, il sera alors facile d'interrompre la boucle prématurément.

    [EDIT] j'avais fait une erreur, le temps de tri est trop important maintenant.
    Brachygobius xanthozonus
    Ctenobrycon Gymnocorymbus

  20. #20
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par djibril Voir le message
    Je ne comprends pas ce code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    $max_size = $data{$_}{end} - $data{$_}{end} > $max_size ? $data{$_}{end} - $data{$_}{end} : $max_size for keys %data;
    On aura systématiquement 0 non ?
    Oui, erreur de copier-coller.

    Ce doit être:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    $max_size = $data{$_}{end} - $data{$_}{start} > $max_size ? $data{$_}{end} - $data{$_}{start} : $max_size for keys %data;
    Ça marche quand même avec le jeu de données fabriquées que nous avons, mais ça n'irait pas avec des données moins régulières.

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Réponses: 2
    Dernier message: 26/12/2013, 19h39
  2. Comment ajouter des séries dans des graphes sur des feuilles variables
    Par Molomarcopolo dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 06/07/2012, 17h26
  3. recherche algorithme d'optimisation
    Par jlf205 dans le forum MATLAB
    Réponses: 3
    Dernier message: 09/07/2010, 15h32
  4. Réponses: 5
    Dernier message: 30/10/2006, 14h59
  5. Réponses: 6
    Dernier message: 26/12/2005, 01h48

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo