如何延长二进制搜索迭代器消耗多目标

Question

我有一个函数，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]耗尽时，它应该移至$ 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 { }; 
} 

这是一个标准的二分法搜索策略，直到它找到一个重叠的范围。然后它向右移动，耗尽它，向左移动，耗尽它，最后放弃。理想情况下，它应该可能是下一个目标范围，然后重新搜索，我想（可能是通过递归？）。我的问题是，我不确定如何使用迭代器构建工作。

Answer 1

我刚刚裹着哟ur循环中生成迭代器，并构建一个迭代器函数数组。

根据上下文，我要么返回一个主迭代器或迭代器函数列表。我不确定你想要什么。

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

Answer 2

将其拆分为两个函数，一个外部函数，该函数循环遍历范围并调用实现常规二元碎片的内部函数。

Answer 3

警告：一个非常C++偏见答案：

，你所要做的就是定义一个新的类型的迭代器，这是一对平常的迭代器，以及一个segmemt iterrator（如果你没有什么段迭代器，它是一对段指针的const指针/ ref，以及一个指向正确段的索引）。您必须定义随机访问迭代器的所有概念（差异，整数的加法等）。请记住，至少在C++术语中，这不是一个真正的随机迭代器，因为添加一个整数并不是真正的恒定时间;这就是人生。

Answer 4

如果您想迭代所有与搜索范围重叠的值，则不需要二分搜索。

首先习惯前面的问题：

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

及其与省略的内部点输出

got 1 
[...] 
got 200 
got 40 
[...] 
got 60 
got 50 
[...] 
got 300 
got 50 
[...] 
got 60 
got 250 
[...] 
got 260