Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

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 the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (12)
As of 2016-10-24 13:26 GMT
Find Nodes?
    Voting Booth?
    How many different varieties (color, size, etc) of socks do you have in your sock drawer?

    Results (305 votes). Check out past polls.