[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:
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:
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 :aie:.
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 :aie:
:merci: d'avance !
