이진 검색 반복기를 확장하여 여러 대상을 소비하는 방법
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->() $ 범위가 겹치는 모든 @$ 범위를 반복합니다.
확장하고 싶습니다 binary_range_search 여러 범위를 대상으로 부를 수 있도록 : 예를 들어 :
target => $target_ranges # eg. [ [1, 200], [50, 300], ... ]
search => $search_ranges # as above
따라서 $ 범위-> [0]의 검색이 소진되면 $ 범위-> [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++;
}
}
그렇지 않으면 다음 목표 범위가 검색 범위와 겹치는지 여부를 결정해야합니다. 그러나 if $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";
}
내부 포인트가있는 출력은 IS입니다
got 1 [...] got 200 got 40 [...] got 60 got 50 [...] got 300 got 50 [...] got 60 got 250 [...] got 260
범위를 반복하고 기존의 이진 절단을 구현하는 내부 기능을 호출하는 두 가지 함수로 나뉩니다.
경고 : 매우 C ++ 바이어스 답변 :
당신이해야 할 일은 일반적인 반복기 한 쌍의 새로운 유형의 반복기와 segmemt iterrator를 정의하는 것입니다 (세그먼트 반복기가없는 경우 세그먼트에 대한 const pointer / ref 쌍입니다. 그리고 올바른 세그먼트를 가리키는 색인). 임의의 액세스 반복기 (차이, 정수 추가 등)의 모든 개념을 정의해야합니다. 정수의 추가는 실제로 일정하지 않기 때문에 적어도 C ++ Lingo에서는 진정한 임의의 반복자가 아닙니다. 그런 삶입니다.
