Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

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

by Corion (Patriarch)
on May 24, 2010 at 12:59 UTC ( [id://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
Domain Nodelet?
Node Status?
node history
Node Type: note [id://841384]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (5)
As of 2024-03-28 16:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found