Сравнение диапазона значений в 2 столбцах 2 файлов

Question

У меня есть 2 больших файла (с разделителями табуляции).

первый файл ->

Col1           Col2    Col3 Col4     Col5        Col6       Col7    Col8
101_#2          1       2    F0       263        278        2       1.5
102_#1          1       6    F1       766        781        1       1.0
103_#1          2       15   V1       526        581        1       0.0
103_#1          2       9    V2       124        134        1       1.3
104_#1          1       12   V3       137        172        1       1.0
105_#1          1       17   F2       766        771        1       1.0

второй файл ->

Col1    Col2    Col3             Col4
97486   9   262               279
67486   9   118           119
87486   9   183           185
248233  9   124           134

Я хочу сравнить col5и col6 файла 1 (например, значение диапазона) с col3 и col4 файла2.Если диапазон файла 1 присутствует в файле 2, верните эту строку (из файла file1).

Ожидаемый результат ->

Col1        Col2    Col3 Col4     Col5        Col6       Col7    Col8
101_#2        1       2    F0       263        278        2       1.5
103_#1        2       9    V2       124        134        1       1.3

Пока я пытался ->

@ARGV or die "No input file specified";

open my $first, '<',$ARGV[0] or die "Unable to open input file: $!";
open my $second,'<', $ARGV[1] or die "Unable to open input file: $!";


print scalar (<$first>);

while (<$first>) {
    @cols = split /\s+/;
    $p1 = $cols[4];
    $p2 = $cols[5];

   while(<$second>) {
   @sec=split /\s+/;
   print join("\t",@cols),"\n" if ($p1>=$sec[2] && $p2<=$sec[3]);
}

}

Но это работает только для первого ряда.Также файлы очень большие (около 6 ГБ).

Я только что попробовал что-то с хешами.

@ARGV or die "No input file specified";
open my $first, '<',$ARGV[0] or die "Unable to open input file: $!";
open my $second,'<', $ARGV[1] or die "Unable to open input file: $!";
print scalar (<$first>);
while(<$second>){
chomp;
@line=split /\s+/;
$hash{$line[2]}=$line[3];
}
while (<$first>) {
    @cols = split /\s+/;
    $p1 = $cols[4];
    $p2 = $cols[5];
foreach $key (sort keys %hash){

if ($p1>= "$key"){
if ($p2<=$hash{$key})
{
print join("\t",@cols),"\n";
}
}
else{next;}
}
}

Но это также занимает много времени и памяти. Кто-нибудь может подсказать, как яможет сделать это быстро с помощью хэшей. Большое спасибо.

Answer 1

Взгляните на http://search.cpan.org/dist/Data-Range-Compare-Stream/lib/Data/Range/Compare/Stream.pod

Вот пример, основанный на ваших исходных файлах. Удивительно, что Perl-скрипт никогда не становится больше, чем несколько мегабайт в памяти, независимо от размера исходных файлов! Просто убедитесь, что у вас есть Data :: Range :: Compare :: Stream версии 3.023 или выше!

Примечания:

Этот скрипт выполняет сортировку ваших входных файлов, используя сортировку слиянием на диске. Сортировка на диске может занимать много времени с действительно большими файлами. Вы можете настроить производительность, настроив аргумент bucket_size в конструкторе Data :: Range :: Compare :: Stream :: Iterator :: File :: MergeSortAsc. Подробнее см. http://search.cpan.org/dist/Data-Range-Compare-Stream/lib/Data/Range/Compare/Stream/Iterator/File/MergeSortAsc.pod#OO_Methods.

use Data::Range::Compare::Stream;
use Data::Range::Compare::Stream::Iterator::File::MergeSortAsc;
use Data::Range::Compare::Stream::Iterator::Compare::Asc;
use Data::Range::Compare::Stream::Iterator::Consolidate::OverlapAsColumn;

my $cmp=new Data::Range::Compare::Stream::Iterator::Compare::Asc;

sub parse_file_one {
  my ($line)=@_;
  my @list=split /\s+/,$line;
  return [@list[4,5],$line]
}

sub parse_file_two {
   my ($line)=@_;
   my @list=split /\s+/,$line;
   return [@list[2,3],$line]
}

sub range_to_line {
  my ($range)=@_;
  return $range->data;
}

my $file_one=new Data::Range::Compare::Stream::Iterator::File::MergeSortAsc(
  result_to_line=>\&range_to_line,
  parse_line=>\&parse_file_one,
  filename=>'custom_file_1.src',
);

my $file_two=new Data::Range::Compare::Stream::Iterator::File::MergeSortAsc(
  result_to_line=>\&range_to_line,
  parse_line=>\&parse_file_two,
  filename=>'custom_file_2.src',
);

my $set_one=new Data::Range::Compare::Stream::Iterator::Consolidate::OverlapAsColumn(
  $file_one,
  $cmp
);

my $set_two=new Data::Range::Compare::Stream::Iterator::Consolidate::OverlapAsColumn(
  $file_two,
  $cmp
);

$cmp->add_consolidator($set_one);
$cmp->add_consolidator($set_two);

while($cmp->has_next) {
  my $result=$cmp->get_next;
  next if $result->is_empty;

  my $ref=$result->get_root_results;
  next if $#{$ref->[0]}==-1;
  next if $#{$ref->[1]}==-1;

  foreach my $overlap (@{$ref->[0]}) {
    print $overlap->get_common->data;
  }

}

Единственное, что нужно, это вывод в другом порядке:

103_#1          2       9    V2       124        134        1       1.3
101_#2          1       2    F0       263        278        2       1.5

Answer 2

Вы пытаетесь снова прочитать второй файл, когда он уже находится в конце файла .Чтобы это работало, вам нужно написать seek $second, 0, 0 непосредственно перед внутренним циклом while.

Однако этот метод будет очень медленным и значительно улучшит ситуацию, если вы будете читать все диапазоны извторой файл в память первый.Этот код делает это.Я предлагаю вам попробовать, чтобы увидеть, будет ли он работать в вашей доступной памяти.

use strict;
use warnings;

use List::Util;

my @ranges;

open my $fh, '<', 'f2.txt' or die $!;

while (<$fh>) {
  my ($beg, $end) = (split)[2,3];
  next if $beg =~ /\D/ or $end =~ /\D/;
  push @ranges, [$beg, $end];
}

open $fh, '<', 'f1.txt' or die $!;

while (<$fh>) {
  my ($beg, $end) = (split)[4,5];
  next if $beg =~ /\D/ or $end =~ /\D/;
  print if first { $beg >= $_->[0] and $end <= $_->[1] } @ranges;
}

Answer 3

Другое решение, которое я нашел, значительно ускоряет процесс - это использование подпрограммы: предположим, вы сравниваете первый и второй столбцы обоих файлов, что и было моим намерением.Сначала вам нужно отсортировать оба файла по первому, а затем по второму столбцу. Затем вы читаете первый диапазон файлов в массив и вызываете подпрограмму, чтобы выполнить сопоставление во втором файле и записать совпадающие строки в файл во время сопоставления.найден.В подпрограмме вы также сохраняете номер строки, в которой было найдено последнее совпадение, чтобы perl напрямую переходил на эту строку без задержки!Обратите внимание, что я начинаю с первой строки во втором файле.

</p>

<code>use warnings;
use strict;

open my $first,  '<', "first_file.txt" or die$!; 
open my $second, '<', "second_file" or die$!;
 open output, ">output.txt" or die$!;

my $line_number=1;

foreach (<$first>) {
my  @cols=();
chomp $_;
   my  @cols = split( /\s+/, $_ );
   my $p1   = $cols[0];
   my $p2   = $cols[1];
   match($p1,$p2,$line_number);
}


sub match{
 while  (<$second>) {
    next if ($. < $line_number);
    chomp $_;
    my @list = @_;
    my $p1=(@list[0]);
    my $p2=(@list[1]);
    my $line_number=(@list[2]);
         my @sec = split( /\s+/, $_ );
       if ( $p1 == $sec[0] && $p2 == $sec[1] ) { 
       print output2 $_."\n"; 
       return $line_number;
       next;}

       } }
</code>

Answer 4

С помощью двойной петли вы понимаете, что создаете алгоритм с эффективностью O ² .Например, если оба файла содержат по 100 строк в каждом файле, вы будете повторять свой внутренний цикл 10000.Если оба файла содержат 1000 элементов, вы будете не в 10 раз дольше, а в 1000 раз дольше.Если эти файлы настолько большие, насколько вы утверждаете, вы будете долго ждать завершения вашей программы.

Лучше всего поместить ваши данные в базу данных SQL (что-то, что сделанодля работы с большими источниками данных).

В противном случае вам придется сохранить первый файл в формате, в котором вы сможете быстро найти нужный диапазон, например, в двоичном дереве.

Сохраните ваш первый файл в виде двоичного дерева, основываясь на нижнем диапазоне, но сохраняя для сравнения нижний и верхний диапазоны в узлах двоичного дерева.

Для каждой строки во втором файле вы будете искать черезваше двоичное дерево для правильного нижнего диапазона, сравните верхний диапазон, и, если это совпадение, вы нашли свой узел.

Это слишком сложно для меня, чтобы написать быстрый алгоритм.Однако в CPAN есть несколько модулей двоичного дерева, которые должны значительно упростить хранение и поиск вашего дерева.К сожалению, я никогда не использовал один, поэтому я не могу дать рекомендации.Однако вам, вероятно, следует найти алгоритм сбалансированного дерева, такой как Tree :: AVL .

Использование такой структуры, безусловно, сложнее, чем ваш двойной цикл, но гораздо, намного быстрее.При этом эффективность будет немного больше, чем размер двух файлов вместе взятых.

---

Другая возможность состоит в том, чтобы отсортировать два файла в два отдельных массива.Алгоритм сортировки Perl где-то рядом с OlogO, который намного эффективнее, чем двойной цикл, но не так эффективен, как построение двоичного дерева.Однако, если два файла более или менее уже в порядке, он будет ближе к бинарному дереву по эффективности и намного быстрее для реализации.

Если вы сортируете оба массива, вы можете последовательно отключаться вфайл № 2, и найдите строку в файле № 1.Поскольку оба файла в порядке, вам не нужно начинать с начала файла # 1 при поиске следующей подходящей строки в файле № 2.

Надеюсь, это поможет.Извините за отсутствие примеров кодирования.

Answer 5

Это, кажется, работает очень хорошо (и это довольно близко к вашему исходному коду)

</p>

<code>@ARGV or die "No input file specified";

open my $first,  '<', $ARGV[0] or die "Unable to open input file: $!";
open my $second, '<', $ARGV[1] or die "Unable to open input file: $!";

print scalar(<$first>);

my $secondHeader = <$second>;

while (<$first>) {
    @cols = split /\s+/;
    $p1   = $cols[4];
    $p2   = $cols[5];

    my $secondLine = <$second>;
    if ( defined $secondLine ) {
        @sec = split( /\s+/, $secondLine );
        print join( "\t", @cols ), "\n" if ( $p1 >= $sec[2] && $p2 <= $sec[3] );
    }
}
</code>

Answer 6

Это базовая «оптимизация запросов» в том смысле, что это делает оптимизатор SQL.У вас есть несколько вариантов.

Один из вариантов - читать файл1 по одной строке и читать файл2 для каждой строки файла1, распечатывая соответствующие данные.Понятно, что это медленно.Это не самый медленный способ: он читает каждую строку File2 по очереди и сканирует File1 (файл большего размера) на совпадения.Этот метод работает независимо от порядка содержимого в файлах.

Другой вариант, который также не зависит от упорядочиваемых данных, - это чтение меньшего файла в память, а затем чтение большего файла.линия за раз, вытягивая соответствующие данные.В простейшей форме вы используете линейный поиск данных в памяти;было бы лучше организовать его так, чтобы можно было быстрее остановить поиск по данным в памяти (возможно, отсортированным по значениям Col3, а затем по значениям Col4).

Если данные на диске ужеПри надлежащей сортировке вы можете обойтись без одного из файлов в памяти и просто выполнить операцию слияния с файлами.Возможно, вы захотите, чтобы File1 сортировался в порядке Col5 (во вторую очередь на Col6), в то время как File2 будет сортироваться в порядке Col3 и Col4.Это уменьшает объем данных в памяти за счет предварительной сортировки данных.Вы должны тщательно обдумать это: вы стремитесь избежать чтения слишком большого количества данных в память, но поскольку условие соответствия находится в диапазонах, вам, вероятно, потребуется сохранить некоторое количество строк хотя бы в одном из файлов.в памяти для повторного использования.

Если у вас достаточно памяти и данные предварительно не отсортированы, вы можете решить прочитать оба файла в памяти, выполнить соответствующую сортировку и затем выполнить параметры слияния.

Поскольку вы сортируете по диапазонам, теоретически вы можете вместо этого задействовать механизм индексации R-Tree.Тем не менее, это может быть излишним для пары текстовых файлов, если вы не собираетесь делать это часто.

Наконец, поскольку я определил это как то, что оптимизаторы SQL делают все время, выможет лучше всего загрузить фактическую базу данных с данными и затем выполнить запрос:

SELECT F1.*, F2.*
  FROM File1 AS F1 JOIN File2 AS F2
    ON F1.Col5 <= F2.Col4 AND F1.Col6 >= F2.Col3

Условие проверяет, что F1.Col5 .. F1.Col6 перекрывается с F2.Col3 .. F2.Col4.Предполагается, что если у вас есть [129..145] и [145..163], то вам нужно совпадение.Если это неверно, отрегулируйте <= и >= соответственно.См. Как сравнить перекрывающиеся значения в строке и, в частности, Определить, перекрываются ли два диапазона дат .Хотя в обоих случаях речь идет о датах и ​​времени, ответы также применимы к числовым диапазонам (или к любому другому диапазону).

Из представленных вариантов наиболее простым является вариант с приемлемой характеристикой производительности: второй:

• Считайте файл меньшего размера в память и организуйте его для быстрого доступа, затем просканируйте файл большего размера по одной строке за раз.

Однако, если существуют ограничения памяти или времяограничения, которые мешают этому работать, тогда вам нужно будет выбрать один из других механизмов.

Answer 7

Ваше чтение всего второго файла, как только вы прочитаете вторую запись первого файла. Изменения:

while(<$second>) {

что-то вроде:

if (defined($_ = <$second>)) {

Итак, у вас есть:

#!/usr/bin/env perl
use strict;
use warnings;
my ( @cols, $p1, $p2, @sec );
@ARGV or die "No input file specified";
open my $first , '<',$ARGV[0] or die "Unable to open input file: $!";
open my $second,'<', $ARGV[1] or die "Unable to open input file: $!";
print scalar <$first>;
<$second>; #...throw away first line...
while (<$first>) {
    @cols = split /\s+/;
    $p1   = $cols[4];
    $p2   = $cols[5];

    if (defined($_ = <$second>)) {
        @sec=split /\s+/;
        print join("\t",@cols),"\n" if ($p1>=$sec[2] && $p2<=$sec[3]);
    }
}