2010-09-24 11 views
3

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:

  1. 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.

  2. Mon monde est circulaire ... Il y a une donnée max_length (par exemple 9999) 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.

+1

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

+0

@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 ... –

Répondre

2

Avez-vous beaucoup de mémoire disponible?

my $max_length = 9999; 
my @range = ([12,80],[34,60],[34,9000]); 

my @lookup; 

for (@range) { 
    my ($start, $end) = @$_; 
    my @idx = $end >= $start ? $start .. $end : ($start .. $max_length, 0 .. $end); 
    for my $i (@idx) { $lookup[$i] .= pack "L", $end } 
} 

Maintenant, vous avez un tableau de listes de numéros emballés dans @lookup où la liste emballés à chaque index contient les extrémités de toutes les gammes qui comprennent ce point. Donc, pour vérifier combien de plages contiennent une autre plage, vous recherchez son index de départ dans le tableau, puis comptez le nombre d'entrées de la liste compressée à cet index, qui sont plus petits ou égaux que l'index de fin. Cet algorithme est O (n) par rapport au nombre maximum de plages couvrant un point quelconque (avec la limite étant le nombre total de plages), avec un très léger sur-débit par itération.

sub num_ranges_containing { 
    my ($start, $end) = @_; 

    return 0 unless defined $lookup[$start]; 

    # simple ranges can be contained in inverted ranges, 
    # but inverted ranges can only be contained in inverted ranges 
    my $counter = ($start <= $end) 
     ? sub { 0 + grep { $_ < $start or $end <= $_ } } 
     : sub { 0 + grep { $_ < $start and $end <= $_ } }; 

    return $counter->(unpack 'L*', $lookup[$start]); 
} 

Non testé.

Pour neatness supplémentaire,

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]; 

    # simple ranges can be contained in inverted ranges, 
    # but inverted ranges can only be contained in inverted ranges 
    my $counter = ($start <= $end) 
     ? sub { 0 + grep { $_ < $start or $end <= $_ } } 
     : sub { 0 + grep { $_ < $start and $end <= $_ } }; 

    return $counter->(unpack 'L*', $self->[$start]); 
} 

package main; 
my $rm = RangeMap->new(9999, [12,80],[34,60],[34,9000]); 

De cette façon, vous pouvez avoir un certain nombre de gammes.

Également non testé.

+0

+1 Merci Aristote Pagaltzis. J'aime l'idée, mais cela pourrait être un peu problématique, car 'max_length' pourrait atteindre 10 millions, mais le nombre de plages est relativement faible (environ 30k), ce qui signifie que nous avons des données éparses. En outre, je ne suis pas sûr que cela fonctionne correctement pour les plages wrap-around. –

+0

Ensuite, le pire des cas serait de 10 millions de sous-réseaux, qui à 110 octets chacun devrait être d'environ 1 Go. Un tableau vide de 10 millions d'éléments n'atteint que 40 Mo. Ajoutez une surcharge pour le contenu des sous-tableaux ... vous allez probablement dépasser la limite de mémoire de 32 bits, mais au moins sur une machine 64 bits, vous êtes facilement OK. :-) Esp. si la plupart des points ne sont couverts que par quelques plages. Et vous avez besoin d'autant moins de sous-matrices si de grandes parties de votre espace ne sont couvertes par aucune plage. –

+0

Egalement - le bit '$ end> ​​= $ start' implémente des plages de bouclage. –

1

Dans quelle partie rencontrez-vous des problèmes? Qu'avez-vous essayé jusqu'à présent? Il est une tâche assez simple:

* Iterate through the ranges 
    * Foreach range, check if the test range is in it. 
    * Profile and benchmark 

Il est assez simple Perl:

my $test = [ $n, $m ]; 
my @contains = map { 
     $test->[0] >= $_->[0] 
     and 
     $test->[1] <= $_->[1] 
     } @ranges 

Pour les gammes wrap-around, l'astuce consiste à décomposer les gammes dans séparés avant de les regarder. C'est un travail de force brute. Et, tout comme une note sociale, le taux de votre question est assez élevé: plus élevé que ce que j'attendrais de quelqu'un qui essaie vraiment de résoudre ses propres problèmes. Je pense que vous courez trop vite vers Stackoverflow et au lieu d'obtenir de l'aide, vous sous-traitez votre travail. Ce n'est pas vraiment bien. Nous ne sommes pas payés du tout, et surtout pas payés pour faire le travail qui vous est assigné. Cela peut être très différent si vous avez au moins essayé une implémentation de votre problème, mais beaucoup de vos questions semblent indiquer que vous n'avez même pas essayé.

+0

Merci pour la réponse brian. Ré. votre note, je suis désolé que vous ressentiez de cette façon. Vous pouvez être assuré que je ne sous-traite rien. Je suis dans un contexte où aucun collègue programmeur n'est disponible, alors peut-être que j'utilise ce forum plus souvent que ce que l'on pourrait attendre pour des choses que vous pourriez simplement demander au gars à côté de vous au bureau. Quoi qu'il en soit, j'apprécie vraiment SO, apprendre beaucoup de vous tous, et apprécie toute votre aide. –

+0

Comme je l'ai dit, montrez-nous ce que vous avez essayé jusqu'ici et je me sentirais différent. –

+0

Par respect pour vous, j'ai mis à jour le message original. –

1

À peu près sûr qu'il ya une meilleure façon de faire, mais voici un point de départ:

Prétraitement:

  • Créer deux listes, l'une trié par la valeur de départ des plages, une à la fin .

Une fois que vous obtenez votre gamme:

  • Utilisez une recherche binaire pour correspondre COMMENÇONS dans la liste triée démarrage
  • Utilisez une autre recherche binaire pour correspondre sa fin dans la liste triée fin
  • Trouvez les plages qui apparaissent dans les deux listes (@start [0 ..$ start_index] et @end [$ end_index .. $ # end]).
2

Voici une approche à la solution de force brute:

use strict; 
use warnings; 

my @ranges = ([12,80],[34,60],[34,9000],[76,743]); 

# Split ranges between normal & wrapped: 
my (@normal, @wrapped); 

foreach my $r (@ranges) { 
    if ($r->[0] <= $r->[1]) { 
    push @normal, $r; 
    } else { 
    push @wrapped, $r; 
    } 
} 

sub count_matches 
{ 
    my ($start, $end, $max_length, $normal, $wrapped) = @_; 

    if ($start <= $end) { 
    # This is a normal range 
    return (grep { $_->[0] <= $start and $_->[1] >= $end } @$normal) 
     + (grep { $end <= $_->[1] or $_->[0] <= $start } @$wrapped); 
    } else { 
    # This is a wrapped range 
    return (grep { $_->[0] <= $start and $_->[1] >= $end } @$wrapped) 
     # This part should probably be calculated only once: 
     + (grep { $_->[0] == 1 and $_->[1] == $max_length } @$normal); 
    } 
} # end count_matches 

print count_matches(38,70, 9999, \@normal, \@wrapped)."\n"; 
+0

S'il vous plaît ne pas downvote sans explication. – cjm

+0

+1 Merci cjm, c'est très similaire à ce que j'ai fait, et ça marche, mais je me demande si un peu de pré-traitement peut rendre les choses plus rapides et éviter d'itérer toutes les portées. 'mais je suppose que c'est pareil ... ou est-ce?). En y repensant, peut-être ai-je mis la voiture devant le cheval - peut-être que c'est assez bon. Je devrais probablement tester la performance sur de vraies données à grande échelle. –

+0

La question était de savoir comment faire mieux que l'algorithme le plus naïf possible, et non comment l'écrire (ce qui équivaudrait à une requête «fais mon codage pour moi» étant donné qu'il s'agit d'une translittération directe de la prose au code). –

2

Il y a un moyen plus facile que rouler vos propres gammes: utiliser Number::Interval:

my @ranges  = (
    { START => 10, END => 100 }, 
    { START => 30, END => 90 }, 
    { START => 50, END => 80 }, 
    { START => 180, END => 30 } 
); 
my @intervals; 
for my $range (@ranges) { 
    my $int = new Number::Interval(Min => $range->{START}, 
            Max => $range->{END}); 
    push @intervals, $int; 
} 

Ensuite, vous pouvez utiliser la méthode intersection() pour savoir si deux plages se chevauchent:

my $num_overlap = 0; 
my $checkinterval = new Number::Interval(Min => $min, Max => $max); 
for my $int (@intervals) { 
    $num_overlap++ if $checkinterval->intersection($int); 
} 

Je ne suis pas Vous savez exactement ce que cela va faire avec vos gammes «circulaires» (elles seraient classées comme des intervalles «inversés» par Number::Interval) alors vous devriez faire un peu d'expérimentation. Mais en utilisant un module bat vraiment vos propres méthodes de comparaison de gamme.

Edit: En fait, en regardant la documentation un peu plus près, intersection() ne fera pas ce que vous voulez (en fait, il modifie l'un des objets d'intervalle). Vous voulez probablement utiliser sur les valeurs de début et de fin, et si ces deux valeurs sont contenues dans un autre intervalle, alors ce premier intervalle est contenu par le second.

Bien sûr, vous pouvez mettre à jour Number::Interval ajouter cette fonctionnalité ... :-)

+0

+1 merci, c'est bon à savoir. Il y a un module Perl pour à peu près tout, n'est-ce pas? –

+0

Il y a, c'est juste une question de trouver. :-) – CanSpice

1

Je pense que des problèmes comme celui-ci illustrent les avantages de maintenabilité de briser un emploi vers le bas dans de petites pièces faciles à saisir (certes, avec un coût étant plus de lignes de code).

L'idée la plus simple est celle d'une gamme ordinaire, sans emballage.

package SimpleRange; 

sub new { 
    my $class = shift; 
    my ($m, $n) = @_; 
    bless { start => $m, end => $n }, $class; 
} 

sub start { shift->{start} } 
sub end { shift->{end} } 

sub covers { 
    # Returns true if the range covers some other range. 
    my ($self, $other) = @_; 
    return 1 if $self->start <= $other->start 
      and $self->end >= $other->end; 
    return; 
} 

Utilisation que bloc de construction, on peut créer la classe de plage de l'emballage, qui est constitué de 1 ou 2 chaînes simples (2 si la plage entoure le bord de l'univers). Comme la classe pour les plages simples, cette classe définit une méthode covers.La logique de cette méthode est assez intuitive car nous pouvons utiliser la méthode covers fournie par nos objets SimpleRange.

package WrappingRange; 

sub new { 
    my $class = shift; 
    my ($raw_range, $MIN, $MAX) = @_; 
    my ($m, $n) = @$raw_range; 

    # Handle special case: a range that wraps all the way around. 
    ($m, $n) = ($MIN, $MAX) if $m == $n + 1; 

    my $self = {min => $MIN, max => $MAX}; 
    if ($m <= $n){ 
     $self->{top} = SimpleRange->new($m, $n); 
     $self->{wrap} = undef; 
    } 
    else { 
     $self->{top} = SimpleRange->new($m, $MAX); 
     $self->{wrap} = SimpleRange->new($MIN, $n);  
    } 
    bless $self, $class; 
} 

sub top { shift->{top} } 
sub wrap { shift->{wrap} } 
sub is_simple { ! shift->{wrap} } 

sub simple_ranges { 
    my $self = shift; 
    return $self->is_simple ? $self->top : ($self->top, $self->wrap); 
} 

sub covers { 
    my @selfR = shift->simple_ranges; 
    my @otherR = shift->simple_ranges; 
    while (@selfR and @otherR){ 
     if ($selfR[0]->covers($otherR[0])){ 
      shift @otherR; 
     } 
     else { 
      shift @selfR; 
     } 
    } 
    return if @otherR; 
    return 1; 
} 

quelques tests:

package main; 
main(); 

sub main { 
    my ($MIN, $MAX) = (0, 200); 

    my @raw_ranges = (
     [10, 100], [30, 90], [50, 80], [$MIN, $MAX], 
     [180, 30], 
     [$MAX, $MAX - 1], [$MAX, $MAX - 2], 
     [50, 49], [50, 48], 
    ); 
    my @wrapping_ranges = map WrappingRange->new($_, $MIN, $MAX), @raw_ranges; 

    my @tests = ([1, 10], [30, 70], [160, 10], [190, 5]); 
    for my $t (@tests){ 
     $t = WrappingRange->new($t, $MIN, $MAX); 

     my @covers = map $_->covers($t) ? 1 : 0, @wrapping_ranges; 

     my $n; 
     $n += $_ for @covers; 
     print "@covers N=$n\n"; 
    } 
} 

Sortie:

0 0 0 1 1 1 1 1 1 N=6 
1 1 0 1 0 1 1 1 0 N=6 
0 0 0 1 0 1 0 1 1 N=4 
0 0 0 1 1 1 0 1 1 N=5 
+0

+1 Merci FM, c'est une belle décomposition qui rend les choses plus claires. En fait, j'ai écrit quelque chose de similaire en Java ('classe SimpleRange' et' class Range' qui implémentent la même interface, où 'Range' est composé de deux' SimpleRange's.) Cependant, je ne suis pas sûr de savoir comment résout le problème d'interrogation efficace. –