How about this- my %timings = (); my @start = (3,4, 15, 23, 29, 34, 37); my @stop = (5,10,20, 29, 33, 36, 37);
# Assuming that the start and the stop array have the # same number of elements and each start corresponds with # each stop my $i = 0; my $hash{$start[0]} = $stop[0]; my $refStart = $start[0]; my $refStop = $stop[0]; for ($i = 1; $i <= $#start; $i++) { if ($refStop >= $start[$i]) { $refStop = $stop[$i]; $hash{$refStart} = $stop[$i]; } else { $refStart = $start[$i]; $refStop = $stop[$i]; $hash{$refStart} = $stop[$i]; } } foreach (sort { $a <=> $b } keys %hash) { print $_, " ", $hash{$_}, "\n"; } __END__ prints something like this 3 10 15 20 23 33 34 36 37 37 You can do whatever is required with this difference. -----Original Message----- From: David Gray [mailto:[EMAIL PROTECTED]] Sent: Thursday, May 30, 2002 11:53 AM To: [EMAIL PROTECTED] Cc: 'Bryan R Harris'; 'Janek Schleicher'; 'Felix Geerinckx' Subject: RE: union of times algorithm > 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] -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]