Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

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

by oiskuu (Hermit)
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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1066668]
[Discipulus]: c'mon bro' 20 begincheck and you are ok..

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (7)
As of 2017-10-16 22:35 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (217 votes). Check out past polls.