Re: Range overlap (with a lot of ranges)

[moritz]

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.

[BioLion]

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.