Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: Request help on optimizing a loop for looking up numbers

by oiskuu (Friar)
on Dec 11, 2013 at 17:33 UTC ( #1066668=note: print w/ replies, xml ) Need Help??


in reply to Request help on optimizing a loop for looking up numbers

This problem is solvable with an Interval tree. Google search points to Set::IntervalTree and Tree::Interval. I haven't used either and could not give a recommendation, though.

Your code might look like this:

my $r = $tree->fetch($x->lo, $x->hi); if (@{$r}) ... # overlap case: perform the necessary checks $tree->insert($x, $x->lo, $x->hi);

Edit: If ranges can overlap in any manner and appear in any order, you'll need to figure out which are to be kept and which rejected. If you merge the overlapping ranges, then the interval tree ought to perform well.


Comment on Re: Request help on optimizing a loop for looking up numbers
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (8)
As of 2014-12-20 02:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (95 votes), past polls