Range lookup

[Yash]

I have a set of ranges such as
<0.1%
0.1-0.2%
0.2-0.3%
0.3-0.4%
0.4-0.5%
0.5-0.6%
0.6-0.7%
0.7-0.8%
0.8-0.9%
0.9-1.0%
1.0-1.5%
1.5-2.0%
2.0-2.5%
2.5-3.0%
3-20%
20-30%
30-40%

40%

and I have to identify the range that contains an input value such as
1.25. The above set of ranges is not fixed and is configurable in a
text file.
Can somebody suggest the most efficient way to do this, in terms of
the data structure to use and the lookup technique to apply.

Thanks

 

[Tad McClellan]

I have a set of ranges such as
<0.1%

It will be a bit easier if you normalize the range representation:

0.0-0.1%

0.1-0.2%
0.2-0.3%

Errr, so which one of those ranges is 0.2 supposed to be in?

and I have to identify the range that contains an input value such as
1.25. The above set of ranges is not fixed and is configurable in a
text file.

---------------------------------------
#!/usr/bin/perl
use warnings;
use strict;

my @desc = <DATA>;
chomp @desc;
my @ranges = map { [ /([\d.]+)-([\d.]+)/ ] } @desc; # extract lo/hi

my $num = 1.25;
print "$num is in range $desc[ in_range($num) ]\n";

sub in_range {
my($n) = @_;

foreach my $i ( 0 .. $#ranges ) {
return $i if $num >= $ranges[$i][0] and $num < $ranges[$i][1];
}
return -1;
}

__DATA__
0.0-0.1%
0.1-0.2%
0.2-0.3%
0.3-0.4%
0.4-0.5%
0.5-0.6%
0.6-0.7%
0.7-0.8%
0.8-0.9%
0.9-1.0%
1.0-1.5%
1.5-2.0%
2.0-2.5%
2.5-3.0%
3-20%
20-30%
30-40%
40-100%

 

[Anno Siegel]

Yash ([email protected]) wrote on MMMMLXI September MCMXCIII in
<URL:"" I have a set of ranges such as
"" <0.1%
"" 0.1-0.2%
"" 0.2-0.3%
"" 0.3-0.4%
"" 0.4-0.5%
"" 0.5-0.6%
"" 0.6-0.7%
"" 0.7-0.8%
"" 0.8-0.9%
"" 0.9-1.0%
"" 1.0-1.5%
"" 1.5-2.0%
"" 2.0-2.5%
"" 2.5-3.0%
"" 3-20%
"" 20-30%
"" 30-40%
"" >40%
""
"" and I have to identify the range that contains an input value such as
"" 1.25. The above set of ranges is not fixed and is configurable in a
"" text file.
"" Can somebody suggest the most efficient way to do this, in terms of
"" the data structure to use and the lookup technique to apply.


What a good method is depends on a couple of things. First, does the
set of ranges overlap each other, that is, are there points that belong
to more than one range? Second, how many queries per set of ranges
will you do? If you just have a couple, there's no point in doing any
preprocessing. Otherwise, building a datastructure might pay off.

The number of ranges would be another consideration. A handful or
two, as in the example, would probably be treated differently than
a million.

Lots of possibilities. I'll bet, binary search will figure large
in many of the more efficient ones.

BTW, note that your question has nothing at all to do with Perl. Finding
the most appropriate datastructure for this problem is independent of
the language being used.

That said, I'd take a look at Tie::RangeHash, and probably other
CPAN modules with "range" in their description, either for direct
applicability or for inspiration.

Anno