Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

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]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (2)
As of 2018-01-20 05:22 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (226 votes). Check out past polls.