Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Общие вопросы > Сравнения больших файлов

Автор: Gazprom 10.4.2009, 18:39

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

Код


#!/usr/bin/perl -w

open my $input1, "< in1.txt" or die "Ошибка открытия: $!";
open my $output1, "> out1.txt" or die "Ошибка открытия: $!";
open my $input2, "< in2.txt" or die "Ошибка открытия: $!";
while (my $line = <$input1>) {    
    $temp=0;
    while (my $line1 = <$input2>) {
        if ($line eq $line1) { 
            $temp=1;
            @temp_array=(@temp_array,$line);
            last;
        }
    }    
    if ($temp==0) { 
        print $output1 $line; 
    }
 }
close $input2 or die "Ошибка закрытия: $!";
close $output1 or die "Ошибка закрытия: $!";
close $input1 or die "Ошибка закрытия: $!";
open my $output2, "> out2.txt" or die "Ошибка открытия: $!";
open my $input2, "< in2.txt" or die "Ошибка открытия: $!";
 while (my $line2= <$input2>) {
    $temp1=0;    
    foreach $val (@temp_array) {        
        if ($val eq $line2) {
            $temp1=1;
            last;
        }        
    }
    if ($temp1==0) { 
        print $output2 $line2; 
    }
}
close $input2 or die "Ошибка закрытия: $!";
close $output2 or die "Ошибка закрытия: $!";

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

Подскажи какую нить идею для решения...

Автор: tolkien 11.4.2009, 03:22

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

Автор: Gazprom 13.4.2009, 09:19

Данная задача больше является теоретической, чем практической=(

Цитата

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

Как примерно это делается? И мож ноли будет брать определенные куски файла, например все которые начинаются на определенный символ? (в файле строки отсортированы)

Автор: amg 13.4.2009, 10:05

А зачем кусками файлы зачитывать? Можно каждый раз по одной строке.
Зачтываем по строке из каждого файла, сравниваем их оператором cmp, в зависимости от результата сравнения
0: пропускаем эти строки (они одинаковые)
1: читаем следующую строку из первого файла (или из второго, см. справку по cmp)
-1: читаем следующую строку из второго файла

Как то так, реализовать, вроде, несложно.

Автор: Gazprom 13.4.2009, 14:48

Цитата(amg @ 13.4.2009, 10:05)

Зачтываем по строке из каждого файла, сравниваем их оператором cmp, в зависимости от результата сравнения
0: пропускаем эти строки (они одинаковые)
1: читаем следующую строку из первого файла (или из второго, см. справку по cmp)
-1: читаем следующую строку из второго файла

Как то так, реализовать, вроде, несложно.

Так и сделал, вроде получилось.
Вот хотелось бы чтоб прокомментировать, если есть какие нить недоработки, хотя ои скорей всего есть!!1
Заранее спасибо

Код


open my $input1, "< in1.txt" or die "Ошибка открытия: $!";
open my $input2, "< in2.txt" or die "Ошибка открытия: $!";
open my $output1, "> out1.txt" or die "Ошибка открытия: $!";
open my $output2, "> out2.txt" or die "Ошибка открытия: $!";

my $line=<$input1>; my $line1=<$input2>;
$str_temp="";
$str_temp1="";
$bul=0;
while ($bul==0) {    
    if ($str_temp eq $line) {
        $line=<$input1>;
        next;
    }
    if ($str_temp1 eq $line1) {
        $line1=<$input2>;
        next;
    }    
    $temp=$line cmp $line1 ;
    if ($temp==0) { 
        $str_temp=$line;
        $str_temp1=$line1;
        $line=<$input1>;
        $line1=<$input2>;
    }
    if ($temp==-1) {
        print $output1 $line; 
        $str_temp=$line;
        $line=<$input1>;
    }
    if ($temp==1) {
        print $output2 $line1;
        $str_temp1=$line1;
        $line1=<$input2>;
    }
    unless ($line) {
        while ($line1) {
            if ($str_temp1 eq $line1) {
                $line1=<$input2>;
                next;
            }    
            print $output2 $line1;
            $str_temp1=$line1;
            $line1=<$input2>;
        }
        last;    
    }
    unless ($line1) {
        while ($line) {
            if ($str_temp eq $line) {
                $line=<$input1>;
                next;
            }    
            print $output1 $line;
            $str_temp=$line;
            $line=<$input1>;
        }
        last;    
    }
    
}
close $output2 or die "Ошибка закрытия: $!";
close $output1 or die "Ошибка закрытия: $!";
close $input2 or die "Ошибка закрытия: $!";
close $input1 or die "Ошибка закрытия: $!";

Автор: sir_nuf_nuf 13.4.2009, 20:54

Тут есть тонкость:

Что значит "нет во втором файле" ? Нет вообще ?
Тогда в любом случае вам для того что бы определить что строки нет в файле нужно его полностью просмотреть, а он в память не поместится..

В Случае если файлы отсортированы, так что строки в порядке возрастания - то решение предложил товарищ amg

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

Автор: amg 14.4.2009, 04:56

Gazprom, перед безусловным зачитыванием строки из файла необходимо делать проверку на конец файла
if (eof($input1)) {...}
и не пытаться зачитывать очередную строку, если файл уже кончился.