Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

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 chanting in the Monastery: (6)
As of 2018-06-25 11:43 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (126 votes). Check out past polls.