Какой самый быстрый способ в Perl получить все строки файла file1, которые не отображаются в файле file2?

Question

У меня есть два (очень больших) текстовых файла. Какой самый быстрый способ - с точки зрения времени выполнения - создать третий файл, содержащий все строки файла1, которые не отображаются в файле2?

Итак, если file1 содержит:

Sally  
Joe  
Tom  
Suzie

И file2 содержит:

Sally  
Suzie  
Harry  
Tom

Тогда выходной файл должен содержать:

Joe

Answer 1

Создайте хэш-карту, содержащую каждую строку из файла 2. Затем для каждой строки в файле 1, если ее нет в хэш-карте, выведите ее. Это будет O (N), который является лучшим классом эффективности, которого вы можете достичь, если будете читать входные данные.

Реализация Perl:

#!/usr/bin/env perl
use warnings;
use strict;
use Carp ();

my $file1 = 'file1.txt';
my $file2 = 'file2.txt';

my %map;
{
    open my $in, '<',$file2 or Carp::croak("Cant open $file2");
    while (<$in>) {
      $map{$_} = 1;
    }
    close($in) or Carp::carp("error closing $file2");
}
{
   open my $in,'<', $file1 or Carp::croak("Cant open $file1");
   while (<$in>) {
    if (!$map{$_}) {
      print $_;
    }
   }
   close $in or Carp::carp("error closing $file1");
}

Если файл 2 настолько велик, что хэш-карта не помещается в памяти, у нас есть другая проблема. Тогда возможное решение состоит в том, чтобы использовать вышеупомянутое решение для фрагментов файла 2 (достаточно малых, чтобы поместиться в память), выводя результаты во временные файлы. При условии достаточного соответствия между файлом 1 и файлом 2, общий объем вывода должен быть разумного размера. Чтобы вычислить окончательные результаты, мы выполняем пересечение строк во временных файлах, т. Е. Чтобы строка была в окончательных результатах, она должна появляться в каждом временном файле.

Answer 2

Не Perl, но эффективно:

diff <(sort file1) <(sort file2)

Answer 3

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

sort < file1 > file1.sorted
sort < file2 > file2.sorted
comm -2 -3 file1.sorted file2.sorted > differences

Если файлы настолько велики, что Perl должен создать страницу VM, чтобы загрузить все строки в хеш-таблицу, этот метод будет намного быстрее. В противном случае подход на основе хеш-таблицы должно быть быстрее.

Если вы работаете в Unix, лучше использовать внешнюю команду sort вашей системы, поскольку она разумно относится к использованию памяти - использование Perl sort() влечет за собой чтение всего содержимого файла в память.

Если вы работаете в Windows, учтите, что в поставляемой команде sort регистр не учитывается , и ее нельзя отключить! Также в Windows нет команды comm, так что вы Вам нужно будет свернуть свой собственный - заменить третью строку выше на:

perl subtract_sets.pl file1.sorted file2.sorted > differences.txt

subtract_sets.pl

#!/usr/bin/perl
open my $f1, '<', $ARGV[0] or die;
open my $f2, '<', $ARGV[1] or die;

my $x = <$f1>;
my $y = <$f2>;

while (defined $x && defined $y) {
    if ($x lt $y) {
        print $x;
        $x = <$f1>;
    } elsif ($y lt $x) {
        print $y;
        $y = <$f2>;
    } else {
        # Lines match
        $x = <$f1>;
        $y = <$f2>;
    }
}

while (defined $x) {
    print $x;
    $x = <$f1>;
}

while (defined $y) {
    print $y;
    $y = <$f2>;
}

Answer 4

#!/usr/bin/perl                                                                 

use warnings; 
use strict;

open(my $alpha, '<', 'file1') || die "Couldn't open file1";
open(my $beta, '<' , 'file2') || die "Couldn't open file2";

my %data;
map {$data{$_} = 1} <$alpha>;
map {print $_ unless $data{$_}} <$beta>;

Answer 5

Только некоторые показатели эффективности:

10 тыс. Строк, максимум 10 символов в каждой строке.

          Rate slipset marcog
slipset 47.6/s      --   -16%
marcog  56.7/s     19%     --

100 тыс. Строк, максимум 10 символов в каждой строке.

          Rate slipset marcog
slipset 3.02/s      --   -34%
marcog  4.60/s     52%     -

1000 тыс. Строк, максимум 10 символов в каждой строке.

        s/iter slipset marcog
slipset   4.09      --   -33%
marcog    2.75     49%     --

1 тыс. Строк, не более 100 символов в каждой строке.

         Rate  slipset marcog
slipset 379/s      --   -12%
marcog  431/s     14%     --

100 тыс. Строк, максимум 100 символов в каждой строке

          Rate slipset  marcog
slipset 2.15/s      --    -30%
marcog  3.08/s     44%      --

1 000 строк, не более 1000 символов в каждой строке максимум

         Rate slipset  marcog
slipset 133/s      --    -10%
marcog  148/s     11%      --

100 тыс. Строк, не более 1000 символов в каждой строке максимум

          Rate slipset  marcog
slipset 1.01/s      --    -18%
marcog  1.22/s     22%      --

Эффективность памяти

Marcog: 100 000 строк, не более 1000 символов в каждой строке:

Memory usage summary: heap total: 163_259_635, heap peak: 61_536_800, stack peak: 17_648
         total calls     total memory   failed calls
 malloc|     307_425      162_378_090              0
realloc|       1_461           96_878              0  (nomove:1_218, dec:1_026, free:0)
 calloc|      12_762          784_667              0
   free|     307_598      155_133_460

Slipset: 100 000 строк, не более 1000 символов в каждой строке:

Memory usage summary: heap total: 647_103_469, heap peak: 118_445_776, stack peak: 17_648
         total calls     total memory   failed calls
 malloc|     508_089      186_752_811              0
realloc|     399_907      459_553_775              0  (nomove:334_169, dec:196_380, free:0)
 calloc|      12_765          796_883              0
   free|     507_584      256_315_688

Answer 6

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