Friday, December 24, 2010

Day 24: working with integer spans - Set::IntSpan::Fast

At my previous job I had to work with time ranges. Systems would go down ("red" event) and would come up again ("green" event). And later I had to decide if a new time span was adding new outage time or was already completely contained.

I thought about using sorted start and end times (as epoch time) and compare it via binary search. But the code would have been complex and nobody would understand it. I remembered the integer span modules on CPAN (Set::IntSpan). I could represent all previous time ranges as integer spans and then simply check for intersection with the new time span. If the intersection had the same amount of elements as my new time range, it was already completely contained. Otherwise it added some new outage time.

I choose Set::IntSpan::Fast, which also exists as XS version (Set::IntSpan::Fast::XS):
#!/usr/bin/perl
use strict;
use warnings;
use Set::IntSpan::Fast;
my @outage = (
[1293000000, 1293000060],
[1293000000, 1293000030],
[1293000030, 1293000080],
);
my $prev = Set::IntSpan::Fast->new;
$prev->add_range(@{shift @outage});
foreach (@outage) {
    my $new = Set::IntSpan::Fast->new($_->[0].'-'.$_->[1]);
    my $diff = $new->diff($prev);
    next if $diff->is_empty;
    printf("Added %d seconds outage time.\n", $diff->cardinality);
    $prev->merge($diff);
}
printf("Total outage time: %s seconds.\n", $prev->cardinality);

Instead of intersection I used diff, which is empty if no new outage time is added.

If you misspell the complement method like this:
Set::IntSpan::Fast->new->compliment
you get a nice error message. Try it. :)


This is the end of my Perl Advent calendar. Thanks for all your comments. I learned some new things, which I will try in the coming weeks. I can't promise to post again this year, because I'm quite exhausted. But I have some ideas for new blog entries (update on the UUID benchmark and my reason for switching from RDBO to DBIC).

I wish you a merry Christmas and an happy New Year.

Links:

No comments:

Post a Comment