我有一个排序坐标列表(我们称之为 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 方法在这个问题上可能不可行?
最佳答案
一些建议:
您可以将数据存储在数据库中,例如 MySQL 或 SQLite。然后您可以使用一个简单的请求,例如:
"SELECT * FROM coordinates WHERE x<"+xp+" AND y>"+yp
如果您在 x 和 y 上有索引,这应该非常快。
您还可以查看 R-Trees .几年前我用 R-trees 存储了数万个城市坐标,我可以在几分之一秒内找到距离给定点最近的城市。在您的示例中,您正在存储一维范围,但我很确定 R 树也能正常工作。您可能会发现 Perl 的 R 树实现 here .或者你可以使用 RectanglesContainingDot ,这似乎可以满足您的需求。
您可以在内存中缓存坐标:每个数字看起来都需要 4 个字节来存储,因此如果您有 10^7 对数字,这将导致大约 80 MB 的内存使用。这就是 firefox 在我的机器上使用的!当然,如果您这样做,则需要运行某种守护进程,以避免每次需要检查坐标时都重新加载整个文件。
您可以混合使用解决方案 2 和 3。
我更喜欢解决方案 1:它具有良好的效率/复杂性比。
关于perl - 在 Perl 中检查一对数字在大 (x,y) 坐标中的成员资格的快速算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1565402/