如何優化內循環搜索？

Question

我再次需要你的幫助！

有這樣的分隔的文件標籤：

chr10.10.2  scaffold1116 94.92 394  13  1  16  409  10474 10860 4.1e-201  697.0 
chr10.10.2  scaffold1116 100.00 14  0  0  1  14  10453  10466 1.9e+01 27.0 
………………………… 

和類似的其他文件：

chr10.10.1  283 
chr10.10.2  409 
chr10.10.3  572 
chr10.10.4  248 
chr10.10.5  143 
………………………… 

我想保持從第一個文件中的某些特定行的基礎上的數字第二個。

例如，如果我必須保留「chr10.10.2」這一行，我必須檢查「chr10.10.2」在第二個文件中的編號。 我寫了一個腳本，但由於這兩個文件相當大，需要很長時間。 （對於第一個文件的每一行，它將搜索第二個文件的所有行）。 有沒有什麼辦法以更有效的方式搜索第二個文件？

這裏是我的代碼：

#!/usr/bin/perl 
use strict; 
use warnings; 

my $blat_out = $ARGV[0]; 
my $sizes = $ARGV[1]; 

#Cheking the output of "HCEs Vs Genomes" alignments (blat) based on the sizes of the HCEs.... 

open my $blat_file, $blat_out or die "Could not open $blat_out: $!"; 
while (my $line = <$blat_file>) { 
    chomp $line; 
    # while(my $size_line = <$size_file>) { 
    if ($line =~ m/^chr/) { 
     my @lines = split('\t', $line); 
     #my @size_lines = split('\t', $size_line); 
     my $hce  = $lines[0]; 
     #print "$hce\n"; 
     my $scaf  = $lines[1]; 
     my $persent = $lines[2]; 
     my $al_length = $lines[3]; 
     my $hce_start = $lines[6]; 
     my $hce_end = $lines[7]; 
     my $scaf_start = $lines[8]; 
     my $scaf_end = $lines[9]; 
     my $score  = $lines[10]; 
     open my $size_file, $sizes or die "Could not open $sizes: $!"; 

     while (my $size_line = <$size_file>) { 
      chomp $size_line; 
      my @size_lines = split('\t', $size_line); 
      my $hce_name = $size_lines[0]; 
      my $hce_size = $size_lines[1]; 
      #print "$hce_size\n"; 

      if ($hce eq $hce_name) { 
       my $al_ratio = $al_length/$hce_size; 
       if (($persent >= 98) && ($al_ratio >= 0.9)) { 
        print "$line\n"; #print only the lines that satisfies the previous criteria 
       } 

      } 
     } 
     #close $size_file; 
    } 
} 

非常感謝你提前， 瓦西利斯。

Answer 1

我會推薦給存儲$ size_file存儲器（散），這樣你就不會需要打開它的$ blat_file每一行。這是I/0重。

您可以創建自己的腳本來執行該操作，也可以使用File::Slurp模塊。

紅利：您還可以使用Text::CSV_XS模塊進行更快速的解析，並使用製表符作爲分隔符而不是逗號。

此外，這是不相關的，但一個供參考，你可以將這些行：

my $hce  = $lines[0]; 
my $scaf  = $lines[1]; 
my $persent = $lines[2]; 
my $al_length = $lines[3]; 
my $hce_start = $lines[6]; 
my $hce_end = $lines[7]; 
my $scaf_start = $lines[8]; 
my $scaf_end = $lines[9]; 
my $score  = $lines[10]; 

到：

my ($hce, $scaf, $persent, $al_length, undef, undef, $hce_start, $hce_end, $scaf_start, $scaf_end, $score) = @lines; 

Answer 2

如何使用存儲的第二個文件的哈希：

# Build hash of hce_name => hce_size 
my %size = do { 
    open my $fh, '<', $sizes or die "Could not open $sizes: $!"; 
    map { chomp; split "\t", $_, 2 } <$fh>; 
}; 

open my $blat_file, '<', $blat_out or die "Could not open $blat_out: $!"; 
while (my $line = <$blat_file>) { 
    chomp $line; 

    next if $line !~ m/^chr/; 

    my @fields  = split "\t", $line; 
    my $hce  = $fields[0]; 
    my $scaf  = $fields[1]; 
    my $persent = $fields[2]; 
    my $al_length = $fields[3]; 
    my $hce_start = $fields[6]; 
    my $hce_end = $fields[7]; 
    my $scaf_start = $fields[8]; 
    my $scaf_end = $fields[9]; 
    my $score  = $fields[10]; 

    next if !exists $size{$hce}; 

    my $al_ratio = $al_length/$size{$hce}; 
    if ($persent >= 98 && $al_ratio >= 0.9) { 
     print "$line\n"; #print only the lines that satisfies the previous criteria 
    } 
} 

Answer 3

如果你的兩個文件都非常大，那麼不要使用散列表。使用排序。

首先，排序都基於第一列文件：

$ sort -k 1,1 first.tsv > first.sorted 
$ sort -k 1,1 second.tsv > second.sorted 

然後通過線上設置第一和第二檔線行走，尋找兩者之間的匹配。

當有比賽，打印出來 - 否則，穿行第一或第二個文件，這取決於字符串比較結果：

#!/usr/bin/perl 

use strict; 
use warnings; 

my $firstFn = "first.sorted"; 
my $secondFn = "second.sorted"; 
open my $firstFh, "<", $firstFn or die "could not open first file\n"; 
open my $secondFh, "<", $secondFn or die "could not open second file\n"; 
my $firstLine = <$firstFh>; 
chomp $firstLine; 
my @firstElems = split("\t", $firstLine); 
my $firstChr = $firstElems[0]; 
while (<$secondFh>) { 
    chomp; 
    my ($secondChr, $secondNum) = split("\t", $_); 

    # 
    # Test *chr string equality: 
    # 
    # 1. If secondChr is less than ("lt") firstChr, then we 
    #  retrieve the next secondChr. 
    # 
    # 2. If secondChr is the same as ("eq") firstChr, then we 
    #  print out the first file's current line and retrieve the 
    #  next line from the first file, then re-test. 
    # 
    # 3. If secondChr is greater than ("gt") firstChr, then we 
    #  retrieve the next line from the first file until there 
    #  is a match. 
    # 

    if ($secondChr lt $firstChr) { 
     next; 
    } 
    while ($secondChr eq $firstChr) { 
     print STDOUT "$firstLine\n"; 
     $firstLine = <$firstFh>; 
     chomp $firstLine; 
     @firstElems = split("\t", $firstLine); 
     $firstChr = $firstElems[0]; 
    } 
    while ($secondChr gt $firstChr) { 
     $firstLine = <$firstFh>; 
     chomp $firstLine; 
     @firstElems = split("\t", $firstLine); 
     $firstChr = $firstElems[0]; 
     while ($secondChr eq $firstChr) { 
      print STDOUT "$firstLine\n"; 
      $firstLine = <$firstFh>; 
      chomp $firstLine; 
      @firstElems = split("\t", $firstLine); 
      $firstChr = $firstElems[0]; 
     } 
    } 
} 
close $secondFh; 
close $firstFh; 

這是未經測試，但我認爲它應該工作（或至少解釋會讓你接近）。

這種方法比使用散列表的好處是你只需要足夠的內存來存儲兩行，每行文件一行。除非你的線路也很長，否則你的記憶開銷實際上不成問題。如果你有非常大的文件，這可能是一個重要的優勢。

缺點是排序兩個（大）文件的前期時間成本。但是，如果其中一個文件沒有更改，那麼如果您在兩個文件之間頻繁查找，則可以快速分期排列一些文件。