RE: union of times algorithm

yes...it won't work if it overlaps...but again it was assumed that the @start 
time would be in ascending order.
the example that you have cited...the start @start array will just need to be 
sorted in ascending order.


 my @start = (25,10, 5);
 my @stop  = (45,35,30);

# Sort the start /stop array to be in ascending order

 foreach(0..$#start){
   $sortHash{$start[$_]}{$stop[$_]} = ();
 }

 foreach (sort {$a <=> $b}  keys %sortHash) {
    foreach $inIndex (sort {$a <=> $b} keys %{$sortHash{$_}} ) {
       push (@startA, $_);
       push (@stopA, $inIndex);
    }
 }
 # The rest will work fine!!!!!


 # Assuming that the start and the stop array have the
 # same number of elements and each start corresponds with
 # each stop

 $i = 0;

 $hash{$startA[0]} = $stopA[0];
 $refStart = $startA[0];
 $refStop  = $stopA[0];

 for ($i = 1; $i <= $#startA; $i++) {

     if ($refStop >= $startA[$i]) {
        $refStop = $stopA[$i];
        $hash{$refStart} = $stopA[$i];
     } else {
        $refStart = $startA[$i];
        $refStop  = $stopA[$i];
        $hash{$refStart} = $stopA[$i];
     }


 }

foreach (sort { $a <=> $b } keys %hash) {

   print $_, "   ", $hash{$_}, "\n";

} 



-----Original Message-----
From: Jonathan E. Paton [mailto:jonathanpaton@xxxxxxxxx]
Sent: Friday, May 31, 2002 2:18 PM
To: beginners@xxxxxxxx
Subject: RE: union of times algorithm


 --- "Shishir K. Singh" <sksingh@xxxxxxxxxxxxxxxx> wrote:
> Is there something wrong with this algo ??

Yes, it isn't valid perl.  You didn't debug yours either,
did you?  :P  Anyway, yes there is a problem... I think.
What happens if your timeslices overlap?  E.g.

my @start = (25, 10,  5);
my @stop  = (40, 35, 30);

I don't think your algorithm produces the correct
results, and there is no provision to fix this... I'm
more in a algorithm writing mood rather than a algorithm
validating mood.  Can you comment please?

Jonathan Paton

> ####################################################
>  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";
> }
> ######################################################
> -----Original Message-----
> From: Jonathan E. Paton [mailto:jonathanpaton@xxxxxxxxx]
> Sent: Friday, May 31, 2002 1:58 PM
> To: beginners@xxxxxxxx
> Subject: RE: union of times algorithm
> 
> 
>  --- Wagner-David@xxxxxxxxxxxxxxxxx wrote:
> >     What we have is as stated a union of times. So all I do is take the
> > timeslices and generate a hash element for each time. I don't check to see
> > if it is already there, but just set to one. Then I sort the hash down
> > numerically and total where current minus previous equal 1.  Here is a shot:
> > 
> > use Data::Dumper;
> > 
> > my @timeslices = (
> >     [4, 9],
> >     [3, 6],
> >     [2, 4],
> >     [11,12],
> >     [14,14],
> >     [17,19]
> > );
> > 
> > my %MyHashCounts = ();
> > 
> > for(my $MyId=0;$MyId<=$#timeslices;$MyId++){
> >    for($MyId1=$timeslices[$MyId][0];$MyId1<=$timeslices[$MyId][1];$MyId1++)
> > {
> >       $MyHashCounts{$MyId1}=1;
> >     }
> >  }
> > print Dumper(\@timeslices);
> > print Dumper(\%MyHashCounts);
> > 
> > my $MyPrev = -10;
> > my $MyTotal = 0;
> > foreach my $MyKeys (sort {$a <=> $b} keys %MyHashCounts) {
> >    printf "%3d ", $MyKeys;
> >    $MyTotal++ if ( ($MyKeys - $MyPrev) == 1 );
> >    $MyPrev = $MyKeys; 
> >  }
> > printf "\n";
> > printf "Total: %4d\n", $MyTotal;
> > 
> > Output:
> >   2   3   4   5   6   7   8   9  11  12  14  17  18  19
> > Total:   10
> 
> Which is wrong, since the 14 sneaked in even though the
> contribution of [14,14] should be zero.  Notice:
> 
>       0                 1                   2
>       1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
> >     |    [4,      | 9], | |
> >     |  [3,    6], | | | | |
> >     |[2,| 4], | | | | | | |
> >     | | | | | | | | | |[11,
> >     | | | | | | | | | | | 12],
> >     | | | | | | | | | | | | |[14,
> >     | | | | | | | | | | | | | 14],
> >     | | | | | | | | | | | | | | | |[17, 
>       | | | | | | | | | | | | | | | | | |19]
>          X X X X X X X     X X         X X = 11
> 
> Looking at my algorithm, I can remove the use of the
> hash.
> 
> The algorithm you are using is inferiour to the approach
> I tried (even though BOTH our algorithms are wrong).  If
> I start using numbers in the region of Unix timestamps,
> (i.e. large) it is an impossible to satisfy memory/CPU hog.
> 
> The algorithm I use is pictorally:
> 
>      XXXXXXXXXXXXXXXXXXX
>                                 YYYYYYYYYYYYYYYYYYYYYYY
>                      ZZZZZZZZZZZZZZZZZZZZZZ
>      ^                          ^         ^
>      start X         ^          start Y   end Z       ^
>                      start Z                        end Y
>                        ^
>                        end X
> 
> Sorting results in the following events:
> 
>      ^start X
>                      ^start Z
>                        ^end X
>                                 ^start Y
>                                           ^end Z
>                                                        ^ end Y
> 
> And we can find the number of overlapping sections now:
> ACTIVE
> V
> 1    ^start X
> 12                   ^start Z
> 12                     ^end X
>  23                             ^start Y
>  2                                        ^end Z
>   3                                                    ^ end Y
> 
> So, by sorting we can loop through, starting and stopping "active"
> timeslots.  We need to do this in order, otherwise we will get
> incorrect results.  I sort the second column to always get a start
> event before a stop event.
> 
> Jonathan Paton
> 
> =====
> $_=q|.,&@$$. ,.@$&@$. .&$$@. ,,$ ....!$_=$p.'&$@.',y'&$@' ...,';for(/\S+/g){
> !|.q| .$ .,@, ,$, .,.. @, ,$ ,,@ ...,,.!++$.<22?${'y'.$_}=chr$.+64:[$$=${'y'
> !|.q| ,@$@&.,. $$$&, ..@&&$,,, $., ....!.$_},$y.=($.=~/22\|26\|3(3\|7)/x?' '
> !|.q|. @  ., ,.&,,, , .$..&. .,$  .,,!.$$:"\l$$")]};$y=~/ (.*)/;warn"$1\n"
> !|.q|. $ .,. .,$$&&$...&., @.,.&@$@ ...|,map{-$|--?$r:$p.=$_}split'!';eval$r
> 
> __________________________________________________
> Do You Yahoo!?
> Everything you'll ever need on one web page
> from News and Sport to Email and Music Charts
> http://uk.my.yahoo.com
> 
> -- 
> To unsubscribe, e-mail: beginners-unsubscribe@xxxxxxxx
> For additional commands, e-mail: beginners-help@xxxxxxxx
> 
> 
> --
> To unsubscribe, e-mail: beginners-unsubscribe@xxxxxxxx
> For additional commands, e-mail: beginners-help@xxxxxxxx
>  

=====
$_=q|.,&@$$. ,.@$&@$. .&$$@. ,,$ ....!$_=$p.'&$@.',y'&$@' ..,';for(/\S+/g){
!|.q| .$ .,@, ,$, .,.. @, ,$ ,,@ ..,,.!++$.<22?${'y'.$_}=chr$.+64:[$$=${'y'
!|.q| ,@$@&.,. $$$&, ..@&&$,,, $., ...!.$_},$y.=($.=~/22\|26\|3(3\|7)/x?' '
!|.q|. @  ., ,.&,,, , .$..&. .,$  .,,!.$$:"\l$$")]};$y=~/ (.*)/;warn"$1\n"
!|.q|. $ .,. .,$$&&$...&., @.,.&@$@ ..|,map{-$|--?$r:$p.=$_}split'!';eval$r

__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com

-- 
To unsubscribe, e-mail: beginners-unsubscribe@xxxxxxxx
For additional commands, e-mail: beginners-help@xxxxxxxx