كيفية تمديد جهاز استغلال البحث الثنائي لاستهلاك أهداف متعددة

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

إنها استراتيجية بحث ثنائية قياسية، حتى تجد مجموعة متداخلة. ثم يتحرك على اليمين، ثماره، يتحرك على اليسار، ثماره، ويستسلم أخيرا. من الناحية المثالية، يجب بعد ذلك shift النطاق المستهدف التالي، وإعادة البحث، أفترض (ربما عبر العودية؟). مشكلتي هي أنني لست متأكدا من كيفية جعل هذا العمل مع بناء المؤتمر.

Answer 1

أنا فقط ملفوفة جيلك للمكترونات في حلقة، وبناء مجموعة من وظائف القياس.

اعتمادا على السياق، إما إرجاع جهاز كمبيوتر رئيسي أو قائمة وظائف ITERATOR. لم أكن متأكدة مما تريد.

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

إذا كنت ترغب في التكرار على جميع القيم التي تتداخل نطاقات البحث، فلن تحتاج إلى بحث ثنائي.

أولا المادة الأمامية العرفية:

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 وتحدد نطاق البحث الحالي

سنقوم بتعيين وإعادة ماكينة ITERATOR $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

Answer 3

قم بتقسيمها إلى وظيفتين، وهي وظيفة خارجية حلقات على النطاقات وتدعو إلى وظيفة داخلية تقوم بتنفيذ ختم ثنائي تقليدي.

Answer 4

تحذير: إجابة متحيزة للغاية C ++:

ما عليك فعله هو تحديد نوع جديد من مقطوعة القياس، وهو زوج من ماسيرات معتاد، وميكر إيرراري SEGMEMT (إذا لم يكن لديك اختبار قطيع، فهو زوج من مؤشر CONST / REF إلى القطاعات، ومؤشر يشير إلى القطاع الصحيح). يجب عليك تحديد جميع مفاهيم مزايدة الوصول العشوائي (الفرق، إضافة عدد صحيح، إلخ). ضع في اعتبارك، أنه على الأقل في Lingo C ++ هذا ليس كمطارا عشوائيا حقيقيا، لأن عددا صحيحا ليس وقتا ثابتا حقا؛ هكذا هي الحياة.