如何延長二進制搜索迭代器消耗多目標

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