У меня есть база данных из примерно 30 000 диапазонов, каждый из которых представлен в виде пары начальной и конечной точек:
[12,80],[34,60],[34,9000],[76,743],...
Я хотел бы написать подпрограмму Perl этого диапазона (не из базы данных)и возвращает количество диапазонов в базе данных, которые полностью «включают» данный диапазон.
Например, если у нас было только эти 4 диапазона в базе данных, а диапазон запроса равен [38,70], подпрограмма должнаreturn 2, так как первый и третий диапазоны полностью содержат диапазон запроса.
Проблема: Я хочу сделать запросы как можно более дешевыми, я невоздержитесь от предварительной обработки, если это поможет.
Несколько замечаний:
Я свободно использовал слово «база данных», я не имею в видуфактическая база данных (например, SQL);это просто длинный список диапазонов.
Мой мир круговой ... Есть заданное значение max_length (например, 9999), а диапазоны типа [8541,6] являются законными (выможно думать об этом как об одном диапазоне, который является объединением [8541,9999] и [1,6]).
Спасибо, Дейв
ОБНОВЛЕНИЕ Это был мой первоначальный код:
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 -СРАВНИТЕЛЬНОЕ РЕШЕНИЕ ПРЕДЛАГАЕМЫХ РЕШЕНИЙ
До сих пор у меня не было сравнительного анализа двух целевых решений: наивного , предложенного cjm, который похож на мои оригинальные решения, и требующий памяти один , предложенный Аристотелем Пагальцисом. Еще раз спасибо вам обоим!
Для сравнения я создал следующие пакеты, которые используют один и тот же интерфейс:
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
Поздравляем Аристотеля Пагальтзиса!Ваша реализация очень быстрая!Однако, чтобы использовать это решение, я, очевидно, хотел бы выполнить предварительную обработку (создание) объекта один раз.Могу ли я сохранить (nstore) этот объект после его создания?Я никогда не делал этого раньше.И как мне retrieve это?Что-нибудь особенное?Надеемся, что поиск будет быстрым, поэтому он не повлияет на общую производительность этой великолепной структуры данных.
ОБНОВЛЕНИЕ 3
Я попробовал простой nstore и получилдля объекта RangeMap.Кажется, это работает нормально.Единственная проблема - результирующий файл размером около 1 ГБ, и у меня будет около 1000 таких файлов.Я мог бы жить с ТБ хранилища для этого, но мне интересно, есть ли способ хранить его более эффективно без значительного снижения производительности поиска.Также смотрите здесь: http://www.perlmonks.org/?node_id=861961.
ОБНОВЛЕНИЕ 4 - RangeMap ошибка
К сожалению, RangeMap имеет ошибку.Спасибо BrowserUK от PerlMonks за указание на это.Например, создайте объект с $max_lenght=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;
Ваши комментарии будут приветствоваться.