laziness, impatience, and hubris | |
PerlMonks |
Efficient algorithm needed to split Set::IntSpan objectsby tim.bunce (Scribe) |
on Sep 23, 2009 at 13:22 UTC ( [id://796962]=perlquestion: print w/replies, xml ) | Need Help?? |
tim.bunce has asked for the wisdom of the Perl Monks concerning the following question: I humbly seek the wisdom of the Monks. Given a list of Set::IntSpan objects I'd like to find the number of overlapping ranges for any given value. For example, given the three ranges represented here: --XXXXXXXXX--- a = 3-11 ----XXXX------ b = 5-8 ------XXXXX--- c = 7-11 I'd like to end up with these values: 00112233222000 For my use-case I know that each span is just one contiguous range - there are no holes in the spans. Also, the spans may be large so iterating over the elements of a span isn't an option. I think the first step would be to split ranges which overlap other ranges into separate non-overlapping ranges: --XX---------- a1 = 3-4 ----XXXX------ a2 = 5-8 --------XXX--- a3 = 9-11 ----XXXX------ b = 5-8 ------XX------ c1 = 7-8 --------XXX--- c2 = 9-11 then a simple $hash{ $stringified_span }++ would give me the counts. Any suggestions for how to do this efficiently? Or a different approach? (I've thousands of spans representing events with durations from a log)
Back to
Seekers of Perl Wisdom
|
|