Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?

Re: Range overlap (with a lot of ranges)

by moritz (Cardinal)
on May 24, 2010 at 11:30 UTC ( #841369=note: print w/replies, xml ) Need Help??

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

I haven't read the references you posted earlier, so please forgive me if that one was already suggested.

You could store for each location an array of ranges that contain it:

# range A : 1-3 # range B : 5-6 # leads to my @ranges = [ [], # 0 ['1-3'], # 1 ['1-3'], # 2 ['1-3'], # 3 [], # 4 ['5-6'], # 5 ['5-6'], # 6 ];

Once this table is built, for every range it's very fast to test which other ranges overlap.

To save memory, you can also use a string in each location, so that if you have ranges 1-5 and 4-6, the entry for for 5 would be 1-5,4-6.

One million strings should fit into memory. If the array is rather sparse, you could also use a hash instead.

Perl 6 - links to (nearly) everything that is Perl 6.

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

    I think this is similar to my 'stringify' idea (I intended to use substr to pull out each ID), and one I did try (using Number::Range objects, to populate the array). This proved too heavyweight, but your simple approach might be a winner. Thanks for the advice.

    Just a something something...

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2019-12-10 04:34 GMT
Find Nodes?
    Voting Booth?

    No recent polls found