Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re^2: Range overlap (with a lot of ranges)

by Corion (Pope)
on May 24, 2010 at 12:59 UTC ( #841384=note: print w/replies, xml ) Need Help??


in reply to Re: Range overlap (with a lot of ranges)
in thread Range overlap (with a lot of ranges)

As "both" of your ranges are contingous, I think you can get away by testing whether the start and end points are "close enough" to a start/end point of a range. I would look at the "inversion lists" that the Unicode consortium proposes as an efficient way to implement (tests against) Unicode character ranges.

Some features that inversion lists provide, like fast negation, are not useful to you, so maybe you can get by with even less than what they provide. Maybe even just storing pairs (offset, length) for all your ranges and then doing a binary search for the range at hand already is enough. Maybe there even is a better data structure that allows you to simulatneously track start and end of your range and find the intervals they fall into, but I'm not aware of that.

Replies are listed 'Best First'.
Re^3: Range overlap (with a lot of ranges)
by BioLion (Curate) on May 24, 2010 at 13:09 UTC

    Cool, thanks - I'll follow this up and post anything I find useful...

    Just a something something...

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://841384]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (7)
As of 2019-11-12 10:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Strict and warnings: which comes first?



    Results (65 votes). Check out past polls.

    Notices?