[FWP] Horrible algorithm

[Peter Scott <Peter@PSDT.com>]

Ugh.  I have just written something I am not proud of.  I barely saved 
myself from having to use array indexes everywhere, and barely squeaked by 
the fencepost problem.

I'm sure you can do better :-)  Go ahead, humiliate me.

I was working on a problem of correlating events from two sets of logs.  I 
wanted to print out  all events from one list that occurred within a 
certain time interval of an event from another list.  Simplified example: 
list A and B contain events occurring at these times:

	A			B
	10:00			10:03
	10:01			10:04
	10:02			10:06
	10:05			10:11
	10:23			10:35
	10:36			10:38

and I want to print out events occurring in B within 5 minutes after events 
in A, I want to get the lists:

A: 10:00, 10:01, 10:02, 10:05		B: 10:03, 10:04, 10:06
A: 10:36				B: 10:38

The reason the first list contains 10:06 yet the interval is 5 minutes is 
because there are events in the same group in A occurring later than 
10:00.  The process is: given an event in A at time a, find the next event 
b in B occurring in [a,a+5]; if any events in A occur in (a,b] then add 
them to the group, let the latest one be a', and adjust the interval for 
finding new events in B for the group to be [a',a'+5].

If any of you are still reading :-) my solution owes little to the beauty 
of Perl :-(
In the code below, I'm using numbers instead of times, and $D is the interval.

my @A = qw(1 2 4 7    21 37 38 39        51 52 53  71              90  100);
my @B = qw(   3 6 9 18           42 43 44        54  80 81 82 83 84  91   117);
my $D = 10;

while (@A && @B) {
   my $a = shift @A;
   my @alist = ($a);
   my $b;
   shift @B while @B && $B[0] < $a;
   next unless @B && $B[0] <= $a + $D;
   my @blist = ($b = shift @B);
   while ((@B && $B[0] <= $a + $D) || (@A && $A[0] <= $b)) {
     push @blist, $b = shift @B if (@B && $B[0] <= $a + $D);
     push @alist, $a = shift @A if (@A && $A[0] <= $b);
   }
   print "alist = @alist   blist = @blist \n";
}

Output:

alist = 1 2 4 7   blist = 3 6 9
alist = 37 38 39   blist = 42 43 44
alist = 51 52 53   blist = 54
alist = 71   blist = 80 81
alist = 90   blist = 91

It works, but it doesn't exactly score points for maintainability :-)

Any ideas for something better?


--
Peter Scott
Pacific Systems Design Technologies


==== Want to unsubscribe from Fun With Perl?
==== Well, if you insist... Send mail with body "unsubscribe" to
==== fwp-request@technofile.org