Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Re: Range overlap (with a lot of ranges)

by Marshall (Abbot)
on May 24, 2010 at 12:19 UTC ( #841379=note: print w/replies, xml ) Need Help??

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

This looks like a similar problem to one of my posts, Re: match with elements in array. Recently, I remember running some benchmarks with 100 million hash keys. Takes about 90 seconds on my not so fast machine to create a hash that big and about 25 seconds on a more up-to-date machine.

If the hash table will fit into memory without paging, running 10^7 queries will be real fast once you have the table built. For the simplest approach to work, the number of unique values is what matters. Of course some encoding of the ranges is possible (problem above just had non-overlapping ranges, but hash value could be an array of range ID #'s or a single ID that represents multiple ranges.). Curious, how many unique values do you have that fit within one or more of the valid ranges?

  • Comment on Re: Range overlap (with a lot of ranges)

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2019-12-10 08:08 GMT
Find Nodes?
    Voting Booth?

    No recent polls found