4

我有两组范围。每个范围都是一对整数（开始和结束），表示单个较大范围的某个子范围。两组范围的结构与此类似（当然 ...s 将替换为实际数字）。

$a_ranges =
{
  a_1 =>
  {
    start => ...,
    end   => ...,
  },
  a_2 =>
  {
    start => ...,
    end   => ...,
  },
  a_3 =>
  {
    start => ...,
    end   => ...,
  },
  # and so on
};

$b_ranges =
{
  b_1 =>
  {
    start => ...,
    end   => ...,
  },
  b_2 =>
  {
    start => ...,
    end   => ...,
  },
  b_3 =>
  {
    start => ...,
    end   => ...,
  },
  # and so on
};

我需要确定集合 A 中的哪些范围与集合 B 中的哪些范围重叠。给定两个范围，很容易确定它们是否重叠。我只是使用双循环来执行此操作——在外循环中遍历集合 A 中的所有元素，在内循环中遍历集合 B 的所有元素，并跟踪哪些元素重叠。

这种方法有两个问题。首先是重叠空间非常稀疏——即使每个集合中有数千个范围，我希望集合 A 中的每个范围都与集合 B 中的 1 或 2 个范围重叠。我的方法列举了每一种可能性，即矫枉过正。这导致了我的第二个问题——它的扩展性非常差。当每组中有数百个范围时，代码会很快（不到一分钟）完成，但当每组中有数千个范围时，代码会花费很长时间（+/- 30 分钟）。

有没有更好的方法可以索引这些范围，这样我就不会做太多不必要的重叠检查？

更新：我正在寻找的输出是两个散列（每组范围一个），其中键是范围 ID，值是与该集合中的给定范围重叠的另一组范围的 ID。

4

5 回答 5

10

这听起来像是区间树的完美用例，它是一种专门设计用于支持此操作的数据结构。如果您有两组大小为 m 和 n 的区间，那么您可以在时间 O(m lg m) 内将其中一组构建成区间树，然后在时间 O(n lg m + k) 内进行 n 次交集查询，其中k 是您找到的交叉点的总数。这给出了 O((m + n) lg m + k) 的净运行时间。请记住，在最坏的情况下 k = O(nm)，所以这并不比你所拥有的更好，但是对于交叉点数量稀疏的情况，这可能比你正确的 O(mn) 运行时要好得多现在。

我没有太多使用区间树的经验（Perl 的经验为零，抱歉！），但从描述看来，它们不应该那么难构建。如果一个还不存在，我会感到非常惊讶。

希望这可以帮助！

于 2011-01-13T08:34:10.120 回答
4

如果您不完全依赖于 perl；R 中的 IRanges 包处理区间算术。它有非常强大的原语，用它们编写解决方案可能很容易。

第二点是，如果间隔有额外的结构，问题可能会变得非常容易。例如，如果在每组范围内没有重叠（在这种情况下，可以同时筛选两个有序组的线性方法）。即使在没有这种结构的情况下，您至少可以按起点对一组范围进行排序，并按终点对另一组范围进行排序，然后一旦不再可能匹配就跳出内部循环。当然，现有的和通用的算法和数据结构如前面提到的区间树是最强大的。

于 2011-01-13T11:47:24.207 回答
3

有几个现有的 CPAN 模块可以解决这个问题，我开发了其中的 2 个：Data::Range::Compare 和 Data::Range::Compare::Stream

Data::Range::Compare 仅适用于内存中的数组，但支持泛型范围类型。

Data::Range::Compare::Stream 通过迭代器处理数据流，但它需要了解 OO Perl 才能扩展到通用数据类型。如果您正在处理非常非常大的数据集，建议使用 Data::Range::Compare::Stream。

这是 Data::Range::Compare::Stream 的示例文件夹的摘录。

鉴于这 3 组数据：

Numeric Range set: A contained in file: source_a.src
+----------+
| 1 - 11   |
| 13 - 44  |
| 17 - 23  |
| 55 - 66  |
+----------+

Numeric Range set: B contained in file: source_b.src
+----------+
| 0  - 1   |
| 2  - 29  |
| 88 - 133 |
+----------+

Numeric Range set: C contained in file: source_c.src
+-----------+
| 17  - 29  |
| 220 - 240 |
| 241 - 250 |
+-----------+

预期的输出将是：

+--------------------------------------------------------------------+
| Common Range | Numeric Range A | Numeric Range B | Numeric Range C |
+--------------------------------------------------------------------+
| 0 - 0        |   No Data       |   0 - 1         |   No Data       |
| 1 - 1        |   1 - 11        |   0 - 1         |   No Data       |
| 2 - 11       |   1 - 11        |   2 - 29        |   No Data       |
| 12 - 12      |   No Data       |   2 - 29        |   No Data       |
| 13 - 16      |   13 - 44       |   2 - 29        |   No Data       |
| 17 - 29      |   13 - 44       |   2 - 29        |   17 - 29       |
| 30 - 44      |   13 - 44       |   No Data       |   No Data       |
| 55 - 66      |   55 - 66       |   No Data       |   No Data       |
| 88 - 133     |   No Data       |   88 - 133      |   No Data       |
| 220 - 240    |   No Data       |   No Data       |   220 - 240     |
| 241 - 250    |   No Data       |   No Data       |   241 - 250     |
+--------------------------------------------------------------------+

源代码可以在这里找到。

#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;
use lib qw(./ ../lib);

# custom package from FILE_EXAMPLE.pl
use Data::Range::Compare::Stream::Iterator::File;


use Data::Range::Compare::Stream;
use Data::Range::Compare::Stream::Iterator::Consolidate;
use Data::Range::Compare::Stream::Iterator::Compare::Asc;

my $source_a=Data::Range::Compare::Stream::Iterator::File->new(filename=>'source_a.src');
my $source_b=Data::Range::Compare::Stream::Iterator::File->new(filename=>'source_b.src');
my $source_c=Data::Range::Compare::Stream::Iterator::File->new(filename=>'source_c.src');

my $consolidator_a=new Data::Range::Compare::Stream::Iterator::Consolidate($source_a);
my $consolidator_b=new Data::Range::Compare::Stream::Iterator::Consolidate($source_b);
my $consolidator_c=new Data::Range::Compare::Stream::Iterator::Consolidate($source_c);


my $compare=new  Data::Range::Compare::Stream::Iterator::Compare::Asc();

my $src_id_a=$compare->add_consolidator($consolidator_a);
my $src_id_b=$compare->add_consolidator($consolidator_b);
my $src_id_c=$compare->add_consolidator($consolidator_c);



print "  +--------------------------------------------------------------------+
  | Common Range | Numeric Range A | Numeric Range B | Numeric Range C |
  +--------------------------------------------------------------------+\n";

my $format='  | %-12s |   %-13s |   %-13s |   %-13s |'."\n";
while($compare->has_next) {
  my $result=$compare->get_next;
  my $string=$result->to_string;
  my @data=($result->get_common);
  next if $result->is_empty;
  for(0 .. 2) {
     my $column=$result->get_column_by_id($_);
     unless(defined($column)) {
      $column="No Data";
    } else {
      $column=$column->get_common->to_string;
    }
     push @data,$column;


   }
  printf $format,@data;

  } 
 print "  +--------------------------------------------------------------------+\n";
于 2012-03-30T16:37:27.623 回答
1

尝试 Tree::RB 但要找到互斥范围，没有重叠

如果我有大约 10000 个段并且必须为每个离散数字找到段，那么性能还不错。我的输入有 3 亿条记录。我需要将它们放入单独的桶中。就像对数据进行分区一样。Tree::RB 效果很好。

$var = [
[0,90],
[91,2930],
[2950,8293]
.
.
.
]

我的查找值为 10、99、991 ...

基本上我需要给定数字的范围位置

使用下面的比较功能，我的使用如下：

my $cmp = sub
{
    my ($a1, $b1) = @_;

    if(ref($b1) && ref($a1))
    {
        return ($$a1[1]) <=> ($$b1[0]);
    }

    my $ret = 0;

    if(ref($a1) eq 'ARRAY')
    {
        #
        if($$a1[0] <= $b1 && $b1 >= $$a1[1])
        {
            $ret =  0;
        }
        if($$a1[0] < $b1)
        {
            $ret =  -1;
        }
        if($$a1[1] > $b1)
        {
            $ret =  1;
        }
    }
    else
    {
        if($$b1[0] <= $a1 && $a1 >= $$b1[1])
        {
            $ret =  0;
        }
        if($$b1[0] > $a1)
        {
            $ret =  -1;
        }
        if($$b1[1] < $a1)
        {
            $ret =  1;
        }
    }

    return $ret;
}
于 2011-04-01T19:03:38.453 回答
1

我应该检查时间以了解它是否是最快的方式，但根据您的数据结构，您应该尝试以下操作：

use strict;

my $fromA = 12;
my $toA = 15;
my $fromB = 7;
my $toB = 35;

my @common_range = get_common_range($fromA, $toA, $fromB, $toB);
my $common_range = $common_range[0]."-".$common_range[-1];

sub get_common_range {
  my @A = $_[0]..$_[1];
  my %B = map {$_ => 1} $_[2]..$_[3];
  my @common = ();

  foreach my $i (@A) {
    if (defined $B{$i}) {
      push (@common, $i);
    } 
  }
  return sort {$a <=> $b} @common;
}
于 2013-09-17T08:13:35.127 回答