Comment étendre un itérateur de recherche binaire consommer plusieurs cibles

Question

Je fonction, binary_range_search, qui est appelé comme ceci:

my $brs_iterator = binary_range_search(
    target => $range,     # eg. [1, 200] 
    search => $ranges     # eg. [ {start => 1, end => 1000}, 
);          #  {start => 500, end => 1500} ] 

brs_iterator->() va parcourir toutes les @ gammes de $ sur quelle plage de $ chevauche.

Je voudrais étendre binary_range_search pouvoir l'appeler avec plusieurs plages comme cible, par exemple:

target => $target_ranges # eg. [ [1, 200], [50, 300], ... ] 
search => $search_ranges # as above 

Ainsi, lorsque la recherche sur la gamme de $ -> [0] est épuisé, il se doit passez à $ range -> [1], et ainsi de suite. Voici la fonction en question, sous sa forme originale:

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

C'est une stratégie de recherche binaire standard, jusqu'à ce qu'il trouve une zone de chevauchement. Il se déplace ensuite à droite, l'épuise, se déplace sur la gauche, l'épuise, et finalement abandonne. Idéalement, il faudrait alors shift la prochaine plage cible, et refaire la recherche, je suppose (peut-être via la récursivité?). Mon problème est, je ne suis pas sûr de savoir comment faire ce travail avec la construction de l'itérateur.

Answer 1

Je viens d'emballer yo ur génération de l'itérateur dans une boucle for, et construit un tableau de fonctions d'itérateur.Selon le contexte, je renvoie un itérateur maître ou une liste des fonctions de l'itérateur. Je n'étais pas sûr de ce que tu voulais.

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

Diviser en deux fonctions, une fonction externe qui boucle sur les plages et appelle une fonction interne qui implémente une coupure binaire classique.

Answer 3

Attention: très C++ réponse biaisée:

ce que vous devez faire est de définir un nouveau type de iterator, qui est une paire d'un itérateur d'habitude, et un segmemt iterrator (si vous ne disposez pas d'un itérateur de segment, il s'agit d'une paire d'un pointeur const/ref sur les segments, et d'un index pointant vers le segment correct). Vous devez définir tous les concepts d'un itérateur à accès aléatoire (différence, ajout d'entier, etc.). Gardez à l'esprit qu'au moins en langage C++ ce n'est pas un vrai itérateur aléatoire, puisque l'addition d'un entier n'est pas vraiment le temps constant; c'est la vie.

Answer 4

Si vous souhaitez parcourir toutes les valeurs qui chevauchent les plages de recherche, vous n'avez pas besoin de recherche binaire.

D'abord la question avant d'usage:

use warnings; 
use strict; 

use Carp; 

Tout d'abord, vérifier que nous avons target et search paramètres et que pour chaque plage, le point de départ ne dépasse pas son point de fin. Sinon, nous refusons de procéder.

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; 

L'itérateur est elle-même une fermeture qui maintient l'état suivant:

my $i; 
    my($ta,$tb); 
    my($sa,$sb); 
    my $si = 0; 

où

• $i si définie est la valeur suivante à partir de la zone de superposition de courant
• $ta et $tb sont les points de départ et de fin de la plage cible actuelle
• $sa et $sb sont comme ci-dessus mais pour la plage de recherche actuelle
• $si est un index dans @$search et définit la plage de recherche actuelle

Nous allons attribuons et retourner l'itérateur $it. La déclaration et l'initialisation sont séparées de sorte que l'itérateur puisse s'appeler lui-même si nécessaire. Nous aurons terminé s'il n'y a plus de plages cibles ou s'il n'y a pas de plages de recherche pour commencer.

return unless @$target && @$search; 

Lorsque $i est défini, cela signifie que nous avons trouvé un chevauchement et itérer par incrémenter $i jusqu'à ce qu'il soit plus grand que le point final soit de la fourchette cible actuelle ou la plage de recherche en cours.

if (defined $i) { 
     # iterating within a target range 

     if ($i > $tb || $i > $sb) { 
     ++$si; 
     undef $i; 
     return $it->(); 
     } 
     else { 
     return $i++; 
     } 
    } 

Sinon, nous devons déterminer si la plage cible suivante chevauche une plage de recherche. Cependant, si $i n'est pas défini et que nous avons déjà pris en compte toutes les plages de recherche, nous rejetons la plage cible actuelle et recommençons.

else { 
     # does the next target range overlap? 

     if ($si >= @$search) { 
     shift @$target; 
     $si = 0; 
     return $it->(); 
     } 

Ici nous nous retirons le début et de fin à la fois la fourchette cible actuelle (toujours à l'avant de @$target) et la plage de recherche en cours (indexé par $si).

 ($ta,$tb) = @{ $target->[0] }; 
     ($sa,$sb) = @{ $search->[$si] }{qw/ start end /}; 

test maintenant pour le chevauchement est simple. Pour les plages de recherche disjointes, nous ignorons et passons à autre chose. Sinon, nous trouvons le point le plus à gauche dans le chevauchement et itérer à partir de là.

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

Enfin, nous revenons l'itérateur:

$it; 
} 

Pour un exemple similaire à celui de votre question

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

Sa sortie avec des points internes élidés est

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