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

[oiskuu]

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.