1

我有一个函数，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 重叠的所有 @$ranges。

我想扩展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是下一个目标范围，并重做搜索，我想（也许通过递归？）。我的问题是，我不确定如何使用迭代器构造来实现它。

4

4 回答 4

2

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

首先是习惯的正面问题：

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

其内部点被省略的输出是

得到 1
[...]
得到 200
得到 40
[...]
得到 60
得到 50
[...]
得到 300
得到 50
[...]
得到 60
得到 250
[...]
得到 260
于 2010-01-12T21:15:59.003 回答
2

我只是将您的迭代器生成包装在一个 for 循环中，并构建了一个迭代器函数数组。

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

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;
        }; 
}
于 2010-01-12T21:17:17.960 回答
0

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

你要做的是定义一个新类型的迭代器，它是一对普通的迭代器和一个 segmemt 迭代器（如果你没有一个段迭代器，它是一对指向段的 const 指针/引用，和指向正确段的索引）。您必须定义随机访问迭代器的所有概念（差异、整数相加等）。请记住，至少在 C++ 术语中，这不是一个真正的随机迭代器，因为整数的加法并不是真正的恒定时间；这就是生活。

于 2010-01-12T06:10:30.620 回答
0

将其拆分为两个函数，一个在范围内循环的外部函数并调用一个实现传统二进制截断的内部函数。

于 2010-01-12T02:57:53.557 回答