I ont une base de données de certaines gammes 30k, chacun est administré en une paire de points de début et de fin:Comment puis-je compter efficacement les plages couvrant une plage donnée en Perl?
je voudrais écrire un sous-programme Perl qu'une plage (non à partir de la base de données), et les retours le nombre de plages dans la base de données qui "incluent" complètement la plage donnée. Par exemple, si nous n'avions que ces 4 plages dans la base de données et que la plage de requête est [38,70]
, le sous-programme doit renvoyer 2
, car les première et troisième plages contiennent toutes deux la plage de requête.
Le problème: Je souhaite que les requêtes soient aussi "bon marché" que possible, cela ne me dérange pas de faire beaucoup de pré-traitement, si ça aide.
Quelques notes:
J'ai utilisé le mot "base de données" librement, je ne veux pas dire une base de données réelle (par exemple SQL); c'est juste une longue liste de gammes.
Mon monde est circulaire ... Il y a une donnée
max_length
(par exemple9999
) et varie comme[8541,6]
sont légaux (vous pouvez penser comme une seule plage qui est l'union de[8541,9999]
et[1,6]
).
Merci, Dave
MISE À JOUR Ce fut mon code d'origine:
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";
et, oui, je sais que les if
s sont laids et peuvent être beaucoup plus agréable et plus efficace.
MISE À JOUR 2 - REPÈRES SOLUTIONS SUGGÉRÉES
J'ai Lacez analyse comparative pour les deux solutions proposais à ce jour: la naive one, proposées par CJM, qui est similaire à mes solutions originales et la memory-demanding one, a suggéré par Aristotle Pagaltzis Merci encore pour vous deux!
Pour comparer les deux, j'ai créé les packages suivants qui utilisent la même interface:
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;
et:
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;
J'ai ensuite utilisé certaines données réelles: $max_length=3150000
, environ 17000 gammes avec un taille moyenne de quelques milliers, et enfin interrogé les objets avec quelques 10 000 requêtes. J'ai chronométré la création de l'objet (en ajoutant toutes les plages) et l'interrogation. Les résultats:
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
Félicitations Aristotle Pagaltzis! Votre implémentation est super-rapide! Pour utiliser cette solution, cependant, je vais évidemment faire le pré-traitement (création) de l'objet une fois.Puis-je stocker (nstore
) cet objet après sa création? Je n'ai jamais fait cela auparavant. Et comment devrais-je le retrieve
? Rien de spécial? Espérons que la récupération sera rapide, cela n'affectera pas la performance globale de cette grande structure de données.
MISE A JOUR 3
J'ai essayé simple nstore
et pour récupérer l'objet RangeMap
. Cela semble fonctionner correctement. Le seul problème est le fichier résultant est d'environ 1 Go, et je vais avoir un tel fichier 1000. Je pourrais vivre avec un TB de stockage pour cela, mais je me demande s'il y a de toute façon à le stocker plus efficacement sans trop affecter les performances de récupération. Voir aussi ici: http://www.perlmonks.org/?node_id=861961.
MISE A JOUR 4-RangeMap
bug
Malheureusement, RangeMap
a un bug. Merci à BrowserUK de PerlMonks pour le signaler. Par exemple, créez un objet avec $max_lenght=10
et comme plage unique [6,2]
. Puis demander [7,8]
. La réponse devrait être 1
, pas 0
.
Je pense que ce paquet mis à jour doit faire le travail:
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;
Vos commentaires seront les bienvenus.
Nous allons avoir besoin de savoir comment cette "base de données" est stockée. Est-ce un fichier texte, un tableau de arrayrefs, ou autre chose? – cjm
@cjm Je le construis, donc tout va bien. Actuellement, il est dans un hachage de hachages (chaque gamme est un hachage, qui contient 'start',' end', et beaucoup d'autres choses dont je n'ai pas besoin pour cette tâche). Une partie du prétraitement peut être en train de convertir cela en par ex. un tableau de hachages plus simples, ou un tableau 2-d, ou ... –