Come estendere una ricerca binaria iteratore di consumare bersagli multipli
https://stackoverflow.com/questions/2046390
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho una funzione, binary_range_search, che si chiama in questo modo:
my $brs_iterator = binary_range_search(
target => $range, # eg. [1, 200]
search => $ranges # eg. [ {start => 1, end => 1000},
); # {start => 500, end => 1500} ]
brs_iterator->() sarà iterare su tutte le gamme @ $ $ su cui gamma si sovrappone.
desidero estendere binary_range_search per essere in grado di chiamare con più intervalli come suo obiettivo, per esempio:
target => $target_ranges # eg. [ [1, 200], [50, 300], ... ]
search => $search_ranges # as above
Così, quando la ricerca su $ gamma -> [0] si esaurisce, si dovrebbe passare a $ gamma -> [1], e così via. Ecco la funzione in questione, nella sua forma 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 { };
}
Si tratta di una strategia standard di ricerca binaria, finché non trova un campo di sovrapposizione. Si muove poi a destra, espelle, si sposta a sinistra, esaurisce e, infine, si arrende. Idealmente, dovrebbe allora forse shift il prossimo target di riferimento, e rifare la ricerca, suppongo (forse tramite ricorsione?). Il mio problema è che non sono sicuro di come fare questo lavoro con la costruzione iteratore.
Soluzione
Ho appena avvolto tua generazione iteratore in un ciclo for, e costruito una serie di funzioni iteratori.
A seconda del contesto, sia restituire un iteratore master o un elenco di funzioni iteratori. Non ero sicuro di quello che si voleva.
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;
};
}
Altri suggerimenti
Se hai intenzione di iterare su tutti i valori che si sovrappongono gli intervalli di ricerca, non hai bisogno di ricerca binaria.
In primo luogo la questione davanti consueta:
use warnings;
use strict;
use Carp;
Prima di tutto, controllare che abbiamo parametri target e search e che per ogni intervallo, il punto di partenza è non superiore al suo punto finale. In caso contrario, ci rifiutiamo di procedere.
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'iteratore in sé è una chiusura che mantiene il seguente stato:
my $i;
my($ta,$tb);
my($sa,$sb);
my $si = 0;
dove
-
$ise definito è il seguente valore della corrente gamma sovrapposizione -
$tae$tbsono il punto iniziale e finale per la gamma target corrente -
$sae$sbsono come sopra, ma per il campo di ricerca corrente -
$siè un indice in@$searchche definisce il campo di ricerca corrente
Saremo l'assegnazione e la restituzione del $it iteratore. La dichiarazione e l'inizializzazione sono separati così all'iteratore possono dirsi quando necessario.
my $it;
$it = sub {
Abbiamo finito se non più intervalli di destinazione rimangono o se non ci fosse Intervalli di ricerca per cominciare.
return unless @$target && @$search;
Quando $i è definito, significa abbiamo trovato una sovrapposizione e scorrere incrementando $i finché non è superiore al punto finale di una gamma di destinazione corrente o l'intervallo di ricerca corrente.
if (defined $i) {
# iterating within a target range
if ($i > $tb || $i > $sb) {
++$si;
undef $i;
return $it->();
}
else {
return $i++;
}
}
In caso contrario, abbiamo bisogno di determinare se il prossimo target di riferimento si sovrappone qualsiasi campo di ricerca. Tuttavia, se $i non è definito e abbiamo già preso in considerazione tutti gli intervalli di ricerca, scartiamo la gamma target corrente e ricominciare.
else {
# does the next target range overlap?
if ($si >= @$search) {
shift @$target;
$si = 0;
return $it->();
}
Qui tiriamo fuori il punti iniziale e finale sia del target di riferimento di corrente (sempre nella parte anteriore della @$target) e la gamma di ricerca corrente (indicizzato da $si).
($ta,$tb) = @{ $target->[0] };
($sa,$sb) = @{ $search->[$si] }{qw/ start end /};
Ora il test per la sovrapposizione è semplice. Per gli intervalli di ricerca disgiunti, ignoriamo e andare avanti. In caso contrario, troviamo il punto più a sinistra nella sovrapposizione e iterare da 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++;
}
}
};
Infine, torniamo l'iteratore:
$it;
}
Per un esempio simile a quello nella tua domanda
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";
}
La sua uscita con punti interni elise è
got 1 [...] got 200 got 40 [...] got 60 got 50 [...] got 300 got 50 [...] got 60 got 250 [...] got 260
dividerlo in due funzioni, una funzione esterna che loop negli intervalli e chiama una funzione interna che implementa un chop binaria convenzionale.
Attenzione: un c ++ risposta di parte:
quello che dovete fare è definire un nuovo tipo di iteratore, che è una coppia di un iteratore al solito, e un segmemt iterrator (se non si dispone di un iteratore segmento, si tratta di un paio di un const puntatore / ref a i segmenti, e un indice che punta al segmento corretto). È necessario definire tutti i concetti di un iteratore ad accesso casuale (la differenza, l'aggiunta di numeri interi, ecc). tenere a mente, che almeno in c ++ gergo questo non è un vero iteratore casuale, dal momento che l'aggiunta di un numero intero non è tempo realmente costante; così è la vita.
