我有一个包含3万个范围的数据库，每个范围都由一对起始点和结束点表示：
[12,80],[34,60],[34,9000],[76,743],...
我想编写一个Perl子例程，它接受一个范围（不是来自数据库），并返回数据库中完全“包含”给定范围的范围数量。
例如，如果我们只有这4个范围在数据库中，而查询范围是
[38,70]，则子例程应该返回2，因为第一个和第三个范围都完全包含查询范围。问题：我希望尽可能地使查询“便宜”，如果有助于解决问题，我不介意进行大量的预处理。
一些注意事项：
1. 我自由使用了“数据库”一词，我并不是指实际的数据库（例如SQL）；它只是一长串范围。 2. 我的世界是循环的...有一个给定的
max_length（例如9999），像[8541,6]这样的范围是合法的（你可以把它看作是[8541,9999]和[1,6]的并集形成的单个范围）。谢谢， Dave 更新： 以下是我的原始代码：
use strict;
use warnings;
my $max_length = 200;
my @ranges = (
{ START => 10, END => 100 },
{ START => 30, END => 90 },
{ START => 50, END => 80 },
{ START => 180, END => 30 }
);
sub n_covering_ranges($) {
my ($query_h) = shift;
my $start = $query_h->{START};
my $end = $query_h->{END};
my $count = 0;
if ( $end >= $start ) {
# query range is normal
foreach my $range_h (@ranges) {
if (( $start >= $range_h->{START} and $end <= $range_h->{END} )
or ( $range_h->{END} <= $range_h->{START} and $range_h->{START} <= $end )
or ( $range_h->{END} <= $range_h->{START} and $range_h->{END} >= $end)
)
{
$count++;
}
}
}
else {
# query range is hanging over edge
# only other hanging over edges can contain it
foreach my $range_h (@ranges) {
if ( $start >= $range_h->{START} and $end <= $range_h->{END} ) {
$count++;
}
}
}
return $count;
}
print n_covering_ranges( { START => 1, END => 10 } ), "\n";
print n_covering_ranges( { START => 30, END => 70 } ), "\n";
是的，我知道这些if语句很丑，可以做得更好、更高效。
更新2 - 建议的解决方案基准测试
到目前为止，我已经对两个提出的解决方案进行了一些基准测试：naive one，由cjm提出，类似于我的原始解决方案，以及memory-demanding one，由Aristotle Pagaltzis提出。再次感谢你们两个！
为了比较这两种方法，我创建了以下使用相同接口的程序包：
use strict;
use warnings;
package RangeMap;
sub new {
my $class = shift;
my $max_length = shift;
my @lookup;
for (@_) {
my ( $start, $end ) = @$_;
my @idx
= $end >= $start
? $start .. $end
: ( $start .. $max_length, 0 .. $end );
for my $i (@idx) { $lookup[$i] .= pack 'L', $end }
}
bless \@lookup, $class;
}
sub num_ranges_containing {
my $self = shift;
my ( $start, $end ) = @_;
return 0 unless defined $self->[$start];
return 0 + grep { $end <= $_ } unpack 'L*', $self->[$start];
}
1;
并且：
use strict;
use warnings;
package cjm;
sub new {
my $class = shift;
my $max_length = shift;
my $self = {};
bless $self, $class;
$self->{MAX_LENGTH} = $max_length;
my @normal = ();
my @wrapped = ();
foreach my $r (@_) {
if ( $r->[0] <= $r->[1] ) {
push @normal, $r;
}
else {
push @wrapped, $r;
}
}
$self->{NORMAL} = \@normal;
$self->{WRAPPED} = \@wrapped;
return $self;
}
sub num_ranges_containing {
my $self = shift;
my ( $start, $end ) = @_;
if ( $start <= $end ) {
# This is a normal range
return ( grep { $_->[0] <= $start and $_->[1] >= $end }
@{ $self->{NORMAL} } )
+ ( grep { $end <= $_->[1] or $_->[0] <= $start }
@{ $self->{WRAPPED} } );
}
else {
# This is a wrapped range
return ( grep { $_->[0] <= $start and $_->[1] >= $end }
@{ $self->{WRAPPED} } )
# This part should probably be calculated only once:
+ ( grep { $_->[0] == 1 and $_->[1] == $self->{MAX_LENGTH} }
@{ $self->{NORMAL} } );
}
}
1;
我接着使用了一些真实数据：
$max_length=3150000，大约有17000个范围，平均大小为几千个，最后进行了大约10000个查询。我计时了对象的创建（添加所有范围）和查询。结果如下：cjm creation done in 0.0082 seconds
cjm querying done in 21.209857 seconds
RangeMap creation done in 45.840982 seconds
RangeMap querying done in 0.04941 seconds
恭喜Aristotle Pagaltzis！您的实现速度非常快！ 然而，为了使用这个解决方案，我显然希望在创建对象时进行预处理（创建）一次。我可以在创建后存储（
nstore）这个对象吗？我以前从未做过这样的事情。我该如何检索它？有什么特别的地方吗？希望检索速度很快，这样就不会影响这个伟大数据结构的整体性能。
更新3：
我尝试了一个简单的nstore和检索RangeMap对象。这似乎运行良好。唯一的问题是生成的文件大小约为1GB，并且我将有大约1000个这样的文件。我可以接受这个存储量，但我想知道是否有更有效的方法来存储它，而不会对检索性能产生太大影响。还请参见此处：http://www.perlmonks.org/?node_id=861961。
更新4 - RangeMap bug
很遗憾，RangeMap 存在一个错误。 感谢 PerlMonks 的 BrowserUK 指出这一点。 例如，创建一个对象，其 $max_length = 10，并且具有单个范围 [6,2]。 然后查询 [7,8]。 答案应该是 1，而不是 0。
我认为这个更新的包应该可以解决问题：
use strict;
use warnings;
package FastRanges;
sub new($$$) {
my $class = shift;
my $max_length = shift;
my $ranges_a = shift;
my @lookup;
for ( @{$ranges_a} ) {
my ( $start, $end ) = @$_;
my @idx
= $end >= $start
? $start .. $end
: ( $start .. $max_length, 1 .. $end );
for my $i (@idx) { $lookup[$i] .= pack 'L', $end }
}
bless \@lookup, $class;
}
sub num_ranges_containing($$$) {
my $self = shift;
my ( $start, $end ) = @_; # query range coordinates
return 0
unless ( defined $self->[$start] )
; # no ranges overlap the start position of the query
if ( $end >= $start ) {
# query range is simple
# any inverted range in {LOOKUP}[$start] must contain it,
# and so does any simple range which ends at or after $end
return 0 + grep { $_ < $start or $end <= $_ } unpack 'L*',
$self->[$start];
}
else {
# query range is inverted
# only inverted ranges in {LOOKUP}[$start] which also end
# at of after $end contain it. simple ranges can't contain
# the query range
return 0 + grep { $_ < $start and $end <= $_ } unpack 'L*',
$self->[$start];
}
}
1;
欢迎您的评论。