> I'm trying to come up with an algorithm that seems like it
> ought to be really easy, but it's turning out to be pretty tough...
>
> Basically I have three pairs of start/stop times, e.g.:
>
> 3, 5
> 4, 10
> 15, 20
>
> I want the total time covered by all these ranges. I can't
> just say (5-3 + 10-4 + 20-15) because the 3,5 and 4,10 ranges
> overlap. The desired answer for this case is 13, 3 to 10 and
> 15 to 20. I have the start times in two arrays, @starts and @stops.
>
> I have to do this probably a million+ times. Any ideas on
> how I could go about this?
Building on Janek's response:
> Let's change my algorithm from:
>
> my %timings;
> $timings{$_}++ for (3 .. 5, 4 .. 10, 15 .. 20);
> my $total_time = scalar values %timings;
>
> to:
>
> my %timings;
> $timings{$_}++ for (4 .. 5, 5 .. 10, 16 .. 20);
> my $total_time = scalar values %timings;
And adding some code from Felix from a while ago:
> #! /usr/bin/perl -w
> use strict;
>
> sub generator {
> my $lref = shift;
> my $minseq = shift;
> my $nextfun = shift;
> my $curpos = 0;
> my $lastpos = scalar(@$lref)-1;
> return sub {
> while ($curpos <= $lastpos) {
> my $result = [$lref->[$curpos]];
> push @$result, $lref->[$curpos]
> while ++$curpos<=$lastpos &&
> $lref->[$curpos] == $nextfun->($lref->[$curpos-1]);
> return $result if scalar(@$result) >= $minseq;
> }
> return;
> }
> }
>
> my @list = (1, 2, 3, 4, 10, 14, 15, 16, 20, 34, 35, 36);
> my $iter = generator(\@list, 3, sub {$_[0]+1});
> while (my $r = $iter->()) {
> print "Found: @$r\n";
> }
We end up with:
----begin code----
#!perl -w
use strict;
my %timings = ();
# load up this array with your input
my @pairs = ( [3,5], [4,10], [15,20] );
for my $ra (@pairs) {
# load up hash using slice syntax
@timings{($ra->[0]..$ra->[1])} = 1;
}
my @list = sort {$a<=>$b} keys %timings;
my $num_ranges = 0;
# use sequence detector with 2 as minimum sequence
my $iter = generator(\@list, 2, sub {$_[0]+1});
while (my $r = $iter->()) {
# echo matches
print "Found: @$r\n";
$num_ranges++;
}
my $timeunion = scalar @list - $num_ranges;
print "Time Union is: $timeunion\n";
sub generator {
my $lref = shift;
my $minseq = shift;
my $nextfun = shift;
my $curpos = 0;
my $lastpos = scalar(@$lref)-1;
return sub {
while ($curpos <= $lastpos) {
my $result = [$lref->[$curpos]];
push @$result, $lref->[$curpos]
while ++$curpos<=$lastpos &&
$lref->[$curpos] == $nextfun->($lref->[$curpos-1]);
return $result if scalar(@$result) >= $minseq;
}
return;
}
}
----end code----
I'll leave the benchmarking alone unless someone else feels like it...
Good Luck,
-dave
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
