ха

fcompare-md5.pl

#!/usr/bin/perl

# ------------------------------------------------------------------------------
# Написать программу которая сравнивает два текстовых файла (например терабайтных) 
# и выводит в третий файл строки, которые есть в первом, но нет во втором.
#
# Мой вариант, конечно, немного хулиганский. Но возьмём, к примеру, два одинаковых файла 
# с "Войной и миром", да поправим в одном из них пару строк для контроля. Вариант
# "в лоб", с двумя циклами а-ля
#
# while( <$f1> ) {
#   while( <$f2> ) {
#     ...
#   }
#   seek $f2, 0, 0;
# }
#
# real 1m8.267s
# user 1m5.931s
# sys  0m2.237s
#
# И никакая буферизация тут не спасёт.
#
# А этот вариант на тех же данных (даже с учётом таких тяжестей, как Encode и Digest,
# Devel::NYTProf не даст соврать!)
#
# real 0m0.481s
# user 0m0.476s
# sys  0m0.004s

# ------------------------------------------------------------------------------
use Modern::Perl;
use open qw/:std :utf8/;
use Digest::MD5 qw/md5/;
use Encode qw/encode_utf8/;
use constant MIN_LENGTH => 4;

# ------------------------------------------------------------------------------
my $RX = '^(' . '.' x MIN_LENGTH . ')(.+)$';

# ------------------------------------------------------------------------------
usage() unless $ARGV[1];
usage("Can not open '$ARGV[0]'")
    unless open my $f1, '<:encoding(utf-8)', $ARGV[0];
close $f1, usage("Can not open '$ARGV[1]'")
    unless open my $f2, '<:encoding(utf-8)', $ARGV[1];

# Антиколлизионная мера 1: храним не просто контрольные суммы строк, а группируем
# их по первым MIN_LENGTH символам. То есть для строки 'abcdef' при MIN_LENGTH => 4
# $sums{ 'abcd' }{ md5('ef') } = 1.
my %sums;

# Антиколлизионная мера 2: строки до MIN_LENGTH символов храним целиком. Конечно, есть
# вероятность хорошего отжора памяти - если гигантский файл состоит только из них...
my %lines;

while (<$f2>) {
    chomp;
    next unless $_;
    if ( length $_ <= MIN_LENGTH ) {
        $lines{$_} = 1;
        next;
    }

    my ( $first, $last ) = (/$RX/);
    $sums{$first}{ md5( encode_utf8($last) ) } = 1;
}

while (<$f1>) {
    chomp;
    next unless $_;
    next if $lines{$_};

    if ( length $_ > MIN_LENGTH ) {
        my ( $first, $last ) = (/$RX/);
        next if $sums{$first}{ md5( encode_utf8($last) ) };
    }
    say $_;
}

close $f1;
close $f2;

# ------------------------------------------------------------------------------
sub usage {
    die @_ ? @_ : "Usage: $0 file1 file2";
}

# ------------------------------------------------------------------------------
# That's All, Folks!
# ------------------------------------------------------------------------------