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がオーバーラップするすべての@$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次のターゲット範囲であり、検索をやり直す必要があります（おそらく再帰を介して？）。私の問題は、イテレータ構造でそれを機能させる方法がわからないことです。

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

これを2つの関数に分割します。範囲をループし、従来のバイナリチョップを実装する内部関数を呼び出す外部関数です。

于 2010-01-12T02:57:53.557 に答える
0

警告：非常にc ++に偏った答え：

あなたがしなければならないのは、通常のイテレータのペアである新しいタイプのイテレータと、segmemtイテレータを定義することです（セグメントイテレータがない場合は、セグメントへのconstポインタ/refのペアです。および正しいセグメントを指すインデックス）。ランダムアクセスイテレータのすべての概念（差、整数の加算など）を定義する必要があります。少なくともc++の用語では、整数の加算は実際には一定の時間ではないため、これは真のランダムイテレータではないことに注意してください。それが人生だ。

于 2010-01-12T06:10:30.620 に答える