perl - 在 Perl 中检查一对数字在大 (x,y) 坐标中的成员资格的快速算法

Question

我有一个排序坐标列表(我们称之为 xycord.txt)，如下所示:

chr1    10003486        10043713
chr1    10003507        10043106
chr2    10003486        10043713
chr2    10003507        10043162
chr2    10003532        10042759

实际上这个文件非常大，有 10^7 行。

我想做的是给出另一个两点坐标我想检查它们是否落在 xycord.txt 文件中的任何坐标之间。

我目前的方法非常慢。因为对于这个大型 xycord.txt 文件，还有许多其他两点坐标。

有什么快速的方法吗？

#!/usr/bin/perl -w

my $point_to_check_x = $ARGV[0] || '10003488';
my $point_to_check_y = $ARGV[1] || '10003489';
my $chrid = $ARGV[2] || "chr1";

my %allxycordwithchr;   
# skip file opening construct
while (<XYCORD_FILE>) {
  my ($chr,$tx,$ty) = split(/\s+/,$_);
  push @{$allxycordwithchr{$chr}},$tx."-".$ty;
}


 my @chosenchr_cord = @{$allxycordwithchr{$chrid}};

 for my $chro_cords (@chosenchr_cord){

  my ($repox,$repoy) = split("-",$chro_cord);
   my $stat = is_in_xycoordsfile($repox,$repoy,$point_to_check_x,$point_to_check_y);
   if ($stat eq "IN"){
      print "IN\n";
   }
 }

sub is_in_xycoordsfile  {

    my      ($x,$y,$xp,$yp) = @_;  
    if ( $xp >= $x && $yp <= $y ) {
        return "IN";
    }
    else {
        return "OUT";
    }

}

更新:对于更正此问题，我深表歉意。在我之前的帖子中，我过于简单化了问题。

实际上，还有一个查询字段(例如染色体名称)。因此，DB/RB-trees/SQL 方法在这个问题上可能不可行？

Answer 1

一些建议:

1. 您可以将数据存储在数据库中，例如 MySQL 或 SQLite。然后您可以使用一个简单的请求，例如:

   "SELECT * FROM coordinates WHERE x<"+xp+" AND y>"+yp
   

   如果您在 x 和 y 上有索引，这应该非常快。

2. 您还可以查看 R-Trees .几年前我用 R-trees 存储了数万个城市坐标，我可以在几分之一秒内找到距离给定点最近的城市。在您的示例中，您正在存储一维范围，但我很确定 R 树也能正常工作。您可能会发现 Perl 的 R 树实现 here .或者你可以使用 RectanglesContainingDot ，这似乎可以满足您的需求。

3. 您可以在内存中缓存坐标:每个数字看起来都需要 4 个字节来存储，因此如果您有 10^7 对数字，这将导致大约 80 MB 的内存使用。这就是 firefox 在我的机器上使用的!当然，如果您这样做，则需要运行某种守护进程，以避免每次需要检查坐标时都重新加载整个文件。

4. 您可以混合使用解决方案 2 和 3。

我更喜欢解决方案 1:它具有良好的效率/复杂性比。