Comment prolonger un itérateur de recherche binaire consommer plusieurs cibles
https://stackoverflow.com/questions/2046390
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une fonction, binary_range_search, qui est appelé comme ceci:
my $brs_iterator = binary_range_search(
target => $range, # eg. [1, 200]
search => $ranges # eg. [ {start => 1, end => 1000},
); # {start => 500, end => 1500} ]
brs_iterator->() va parcourir toutes les gammes de @ $ sur quelle plage de $ chevauche.
Je voudrais étendre binary_range_search pouvoir l'appeler avec plusieurs plages comme cible, par exemple:
target => $target_ranges # eg. [ [1, 200], [50, 300], ... ]
search => $search_ranges # as above
Alors, quand la recherche sur la gamme de $ -> [0] est épuisé, il doit passer à la gamme de $ -> [1], et ainsi de suite. Voici la fonction en question, dans sa forme originale:
sub binary_range_search {
my %options = @_;
my $range = $options{target} || return;
my $ranges = $options{search} || return;
my ( $low, $high ) = ( 0, @{$ranges} - 1 );
while ( $low <= $high ) {
my $try = int( ( $low + $high ) / 2 );
$low = $try + 1, next if $ranges->[$try]{end} < $range->[0];
$high = $try - 1, next if $ranges->[$try]{start} > $range->[1];
my ( $down, $up ) = ($try) x 2;
my %seen = ();
my $brs_iterator = sub {
if ( $ranges->[ $up + 1 ]{end} >= $range->[0]
and $ranges->[ $up + 1 ]{start} <= $range->[1]
and !exists $seen{ $up + 1 } )
{
$seen{ $up + 1 } = undef;
return $ranges->[ ++$up ];
}
elsif ( $ranges->[ $down - 1 ]{end} >= $range->[0]
and $ranges->[ $down + 1 ]{start} <= $range->[1]
and !exists $seen{ $down - 1 }
and $down > 0 )
{
$seen{ $down - 1 } = undef;
return $ranges->[ --$down ];
}
elsif ( !exists $seen{$try} ) {
$seen{$try} = undef;
return $ranges->[$try];
}
else {
return;
}
};
return $brs_iterator;
}
return sub { };
}
Il est une stratégie de recherche binaire standard, jusqu'à ce qu'il trouve une zone de chevauchement. Il se déplace ensuite à droite, il épuise, se déplace sur la gauche, des échappements, et donne enfin. Idéalement, il devrait alors shift peut-être la prochaine fourchette cible, et refaire la recherche, je suppose (peut-être via récursion?). Mon problème est, je ne sais pas comment faire ce travail avec la construction iterator.
La solution
Je vient de terminer votre génération iterator dans une boucle, et construit une gamme de fonctions iterator.
En fonction du contexte, je retourne soit un iterator maître ou une liste de fonctions itérateur. Je ne savais pas ce que vous vouliez.
use strict;
use warnings;
my $t = [ [1,200], [400,900] ];
my @r = (
{ start => 1, end => 100 },
{ start => 2, end => 500 },
{ start => 204, end => 500 },
{ start => 208, end => 500 },
{ start => 215, end => 1000 },
{ start => 150, end => 1000 },
{ start => 500, end => 1100 },
);
# Get a master iterator that will process each iterator in turn.
my $brs_iterator = binary_range_search(
targets => $t,
search => \@r,
);
# Get an array of iterators
my @brs_iterator = binary_range_search(
targets => $t,
search => \@r,
);
sub binary_range_search {
my %options = @_;
my $targets = $options{targets} || return;
my $ranges = $options{search} || return;
my @iterators;
TARGET:
for my $target ( @$targets ) {
my ( $low, $high ) = ( 0, $#{$ranges} );
RANGE_CHECK:
while ( $low <= $high ) {
my $try = int( ( $low + $high ) / 2 );
# Remove non-overlapping ranges
$low = $try + 1, next RANGE_CHECK
if $ranges->[$try]{end} < $target->[0];
$high = $try - 1, next RANGE_CHECK
if $ranges->[$try]{start} > $target->[1];
my ( $down, $up ) = ($try) x 2;
my %seen = ();
my $brs_iterator = sub {
if ( exists $ranges->[$up + 1]
and $ranges->[ $up + 1 ]{end} >= $target->[0]
and $ranges->[ $up + 1 ]{start} <= $target->[1]
and !exists $seen{ $up + 1 } )
{
$seen{ $up + 1 } = undef;
return $ranges->[ ++$up ];
}
elsif ( $ranges->[ $down - 1 ]{end} >= $target->[0]
and $ranges->[ $down + 1 ]{start} <= $target->[1]
and !exists $seen{ $down - 1 }
and $down > 0 )
{
$seen{ $down - 1 } = undef;
return $ranges->[ --$down ];
}
elsif ( !exists $seen{$try} ) {
$seen{$try} = undef;
return $ranges->[$try];
}
else {
return;
}
};
push @iterators, $brs_iterator;
next TARGET;
}
}
# In scalar context return master iterator that iterates over the list of range iterators.
# In list context returns a list of range iterators.
return wantarray
? @iterators
: sub {
while( @iterators ) {
if( my $range = $iterators[0]() ) {
return $range;
}
shift @iterators;
}
return;
};
}
Autres conseils
Si vous êtes désireux de itérer sur toutes les valeurs qui se chevauchent les plages de recherche, vous n'avez pas besoin recherche binaire.
D'abord la question avant d'usage:
use warnings;
use strict;
use Carp;
Tout d'abord, vérifiez que nous avons des paramètres de target et search et que pour chaque plage, le point de départ ne dépasse pas son point de fin. Dans le cas contraire, nous refusons de continuer.
sub binary_range_search {
my %arg = @_;
my @errors;
my $target = $arg{target} || push @errors => "no target";
my $search = $arg{search} || push @errors => "no search";
for (@$target) {
my($start,$end) = @$_;
push @errors => "Target start ($start) is greater than end ($end)"
if $start > $end;
}
for (@$search) {
my($start,$end) = @{$_}{qw/ start end /};
push @errors => "Search start ($start) is greater than end ($end)"
if $start > $end;
}
croak "Invalid use of binary_range_search:\n",
map " - $_\n", @errors
if @errors;
L'itérateur lui-même est une fermeture qui maintient l'état suivant:
my $i;
my($ta,$tb);
my($sa,$sb);
my $si = 0;
où
-
$isi définie est la valeur suivante à partir de la zone de superposition de courant -
$taet$tbsont les points de départ et de fin de la fourchette cible actuelle -
$saet$sbsont comme ci-dessus mais pour la plage de recherche actuelle -
$siest un index dans@$searchet définit la plage de recherche actuelle
Nous allons attribuons et retourner le $it iterator. La déclaration et l'initialisation sont séparés de sorte que le iterator peut appeler lui-même si nécessaire.
my $it;
$it = sub {
Nous sommes fait si plus aucune fourchettes cibles restent ou s'il n'y avait pas de mots pour commencer la recherche.
return unless @$target && @$search;
Lorsque $i est défini, cela signifie que nous avons trouvé un chevauchement et itérer par incrémenter $i jusqu'à ce qu'il soit plus grand que le point final soit de la fourchette cible actuelle ou la plage de recherche en cours.
if (defined $i) {
# iterating within a target range
if ($i > $tb || $i > $sb) {
++$si;
undef $i;
return $it->();
}
else {
return $i++;
}
}
Dans le cas contraire, nous devons déterminer si la prochaine fourchette cible chevauche une plage de recherche. Toutefois, si $i est définie et nous avons déjà examiné toutes les plages de recherche, nous supprimons la fourchette cible actuelle et recommencer.
else {
# does the next target range overlap?
if ($si >= @$search) {
shift @$target;
$si = 0;
return $it->();
}
Ici, nous retirons les points de départ et se terminant à la fois la fourchette cible actuelle (toujours à l'avant de @$target) et la plage de recherche en cours (indexé par $si).
($ta,$tb) = @{ $target->[0] };
($sa,$sb) = @{ $search->[$si] }{qw/ start end /};
test maintenant pour le chevauchement est simple. Pour les plages de recherche disjoints, nous négligeons et passer. Dans le cas contraire, on trouve le plus à gauche point dans le recouvrement et itérer à partir de là.
if ($sb < $ta || $sa > $tb) {
# disjoint
++$si;
undef $i;
return $it->();
}
elsif ($sa >= $ta) {
$i = $sa;
return $i++;
}
elsif ($ta >= $sa) {
$i = $ta;
return $i++;
}
}
};
Enfin, nous revenons l'itérateur:
$it;
}
Pour un exemple similaire à celui de votre question
my $it = binary_range_search(
target => [ [1, 200], [50, 300] ],
search => [ { start => 1, end => 1000 },
{ start => 500, end => 1500 },
{ start => 40, end => 60 },
{ start => 250, end => 260 } ],
);
while (defined(my $value = $it->())) {
print "got $value\n";
}
Sa sortie avec des points internes élidés est
got 1 [...] got 200 got 40 [...] got 60 got 50 [...] got 300 got 50 [...] got 60 got 250 [...] got 260
diviser en deux fonctions, une fonction externe qui effectue une boucle sur les plages et appelle une fonction interne qui implémente une côtelette binaire classique.
Attention: très c ++ réponse biaisée:
ce que vous avez à faire est de définir un nouveau type de iterator, qui est une paire d'un itérateur d'habitude, et un segmemt iterrator (si vous ne disposez pas d'un iterator segment, il est une paire d'un pointeur const / ref pour les segments, et un index pointant vers le segment correct). Vous devez définir tous les concepts d'un itérateur d'accès aléatoire (différence, addition d'entiers, etc.). garder à l'esprit, au moins en C ++ Lingo ce n'est pas un vrai iterator au hasard, puisque l'addition d'un entier est vraiment pas le temps constant; telle est la vie.
