Как расширить итератор бинарного поиска, чтобы потреблять несколько целей
https://stackoverflow.com/questions/2046390
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть функция, binary_range_search, это называется так:
my $brs_iterator = binary_range_search(
target => $range, # eg. [1, 200]
search => $ranges # eg. [ {start => 1, end => 1000},
); # {start => 500, end => 1500} ]
brs_iterator->() Будет ли вытекать на все диапазоны @$, на которых $ range совпадает.
Я хотел бы продлить binary_range_search Чтобы иметь возможность назвать это с несколькими диапазонами в качестве цели, например:
target => $target_ranges # eg. [ [1, 200], [50, 300], ... ]
search => $search_ranges # as above
Таким образом, когда поиск в $ range-> [0] исчерпан, он должен перейти к $ range-> [1] и т. Д. Вот рассматриваемая функция, в его исходном виде:
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 { };
}
Это стандартная стратегия бинарного поиска, пока она не найдет перекрывающийся диапазон. Затем он движется справа, исчерпает его, движется слева, исчерпает его и, наконец, сдается. В идеале это должно быть тогда, может быть shift Я полагаю, что следующий целевой диапазон и повторно поиск (возможно, через рекурсию?). Моя проблема в том, что я не уверен, как заставить это работать со конструкцией итератора.
Решение
Я только что завернул ваше генератор итератора в петлю и создал множество функций итератора.
В зависимости от контекста я либо возвращаю мастер -итератор, либо список функций итератора. Я не был уверен, чего вы хотели.
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;
};
}
Другие советы
Если вы хотите итерацию по всем значениям, которые перекрывают диапазоны поиска, вам не нужен бинарный поиск.
Сначала обычный фронт:
use warnings;
use strict;
use Carp;
Во -первых, проверьте, что у нас есть target а также search Параметры, и для каждого диапазона отправная точка не превышает его точку окончания. В противном случае мы отказываемся продолжать.
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;
Сам итератор - это закрытие, которое поддерживает следующее состояние:
my $i;
my($ta,$tb);
my($sa,$sb);
my $si = 0;
куда
$iЕсли определено следующее значение из текущего диапазона перекрытия$taа также$tbЯвляются ли начальные и окончательные точки для текущего целевого диапазона$saа также$sbпохожи на вышеизложенное, но для текущего диапазона поиска$siявляется указателем в@$searchи определяет текущий диапазон поиска
Мы будем назначать и вернуть итератор $it. Анкет Объявление и инициализация являются отдельными, поэтому итератор может вызвать себя при необходимости.
my $it;
$it = sub {
Мы закончили, если больше не осталось целевых диапазонов или если не было диапазонов поиска с самого начала.
return unless @$target && @$search;
Когда $i определено, это означает, что мы нашли перекрытие и итерацию путем увеличения $i до тех пор, пока он не будет больше конечной точки либо текущего целевого диапазона, либо текущего диапазона поиска.
if (defined $i) {
# iterating within a target range
if ($i > $tb || $i > $sb) {
++$si;
undef $i;
return $it->();
}
else {
return $i++;
}
}
В противном случае нам нужно определить, перекрывает ли следующий целевой диапазон любой диапазон поиска. Однако, если $i не определен, и мы уже рассмотрели все диапазоны поиска, мы отбрасываем текущий целевой диапазон и начинаем снова.
else {
# does the next target range overlap?
if ($si >= @$search) {
shift @$target;
$si = 0;
return $it->();
}
Здесь мы вынимаем начальные и конечные точки обоих текущих целевых диапазонов (всегда в передней части @$target) и текущий диапазон поиска (индексируемый $si).
($ta,$tb) = @{ $target->[0] };
($sa,$sb) = @{ $search->[$si] }{qw/ start end /};
Теперь тестирование на перекрытие простое. Для диапазонов поиска в борьбе с ними мы игнорируем и движемся дальше. В противном случае мы находим самую левую точку в перекрытии и итерации оттуда.
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++;
}
}
};
Наконец, мы возвращаем итератор:
$it;
}
Для примера, аналогичного тому в вашем вопросе
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";
}
Его вывод с внутренними точками Elided
got 1 [...] got 200 got 40 [...] got 60 got 50 [...] got 300 got 50 [...] got 60 got 250 [...] got 260
Разделите его на две функции, внешнюю функцию, которая переходит через диапазоны и вызывает внутреннюю функцию, которая реализует обычную бинарную отбивку.
Предупреждение: очень предвзятый C ++ Ответ:
Что вам нужно сделать, так это определить новый тип итератора, который является парой обычного итератора, и иерратор Segmemt (если у вас нет итератора сегмента, это пара константного указателя / REF на сегменты, и индекс, указывающий на правильный сегмент). Вы должны определить все понятия итератора случайного доступа (разница, добавление целого числа и т. Д.). Имейте в виду, что, по крайней мере, в Lingo C ++ это не настоящий случайный итератор, поскольку добавление целого числа на самом деле не является постоянным временем; такова жизнь.
