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;
}
} |
Partager