我有一个大约 30k 范围的数据库，每个范围都作为一对起点和终点给出：
[12,80],[34,60],[34,9000],[76,743],...
我想编写一个 Perl 子例程来表示一个范围（不是来自数据库），并返回数据库中完全“包含”给定范围的范围数。
例如，如果数据库中只有这 4 个范围，并且查询范围是[38,70]，子程序应该返回2，因为第一个和第三个范围都完全包含查询范围。
问题：我希望使查询尽可能“便宜”，如果有帮助的话，我不介意进行大量预处理。
一些注意事项：
我随意使用了“数据库”这个词，我并不是指实际的数据库（例如 SQL）；这只是一长串范围。
我的世界是圆形的...有一个给定的max_length (e.g. 9999）和范围如[8541,6]是合法的（您可以将其视为单个范围，它是[8541,9999] and [1,6]).
谢谢，
戴夫
UPDATE这是我原来的代码：
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 - 基准测试建议的解决方案
到目前为止，我已经对两种专用解决方案进行了一些基准测试：天真的一个 https://stackoverflow.com/questions/3790166/how-can-i-efficiently-count-ranges-that-cover-a-given-range-in-perl/3790411#3790411，由cjm建议，这与我原来的解决方案类似，并且对记忆力要求较高的一 https://stackoverflow.com/questions/3790166/how-can-i-efficiently-count-ranges-that-cover-a-given-range-in-perl/3790446#3790446，由 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;
and:
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
恭喜亚里士多德·帕加尔齐斯！您的实施速度非常快！
但是，要使用此解决方案，我显然希望对对象进行一次预处理（创建）。我可以存储（nstore）这个对象创建后？我以前从来没有这样做过。而我该怎么办retrieve它？有什么特别的吗？希望检索速度会很快，这样就不会影响这个伟大数据结构的整体性能。
UPDATE 3
我尝试了一个简单的nstore并检索RangeMap目的。这似乎工作正常。唯一的问题是生成的文件大约 1GB，我会有大约 1000 个这样的文件。我可以接受 1 TB 的存储空间，但我想知道是否有办法更有效地存储它，而不会对检索性能产生太大影响。另请参阅此处：http://www.perlmonks.org/?node_id=861961 http://www.perlmonks.org/?node_id=861961.
更新 4 -RangeMap bug
很遗憾，RangeMap有一个错误。感谢 PerlMonks 的 BrowserUK 指出了这一点。例如，创建一个对象$max_lenght=10和作为单一范围[6,2]。然后查询[7,8]。答案应该是1, not 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;
欢迎您提出意见。
