我有一个包含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;
欢迎您的评论。