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

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

Форум программистов > Perl: Общие вопросы > "вычитание" файлов.

Автор: e7x 13.5.2007, 19:25

дано:
текстовый файл A,
текстовый файл B

задача:
строки файла А, остутствующие в файле B записать в файл С. причем сделать это _оптимальным_ способом, затратив как можно меньше памяти и как можно меньше времени. имеется 2 решения, но они неудовлетворительны при больших объемах входных файлов.

решение #1 (опишу словами, быстрее будет)
в цикле читаем строки из A и во вложенном цикле сравниваем со строками из B. если совпадений нет, пишем в файл С
при количестве записей, например, в 100к на файл, количество итераций становится равным 10Г, времени тратится ОЧЧЕНЬ много

решение #2 (кодом и словами)
1. читаем все строки из А в хеш, причем ключем хеша является прочитанная строка: $shash{$line} = 1;
2. читаем построчно файл B, и если defined($shash{$line}), то элемент удаляется (т.е. нашли дубль), иначе читаем следующую строку
3. пишем хеш в С

если плохо объяснил, вот примерный код:

Код


my %shash = ();
open A, 'a.txt';
while (<A>) {$shash{$_} = 1}
close A;
open B, 'b.txt';
while (<B>) {
   if (defined($shash{$_})) {delete $shash($_)}
}
close B;
open C, '>c.txt';
foreach (keys(%shash)) {print C $_}
close C;

решение #2 лучше первого в плане производительности, но хуже в плане расходования памяти. жрет просто неимоверно и вываливается с нехваткой памяти на сервере с 2Г оперативы, при тех же, в 100к строк, объемах

вопрос: существует ли какое-нибудь изящное и не очень ресурсоемкое решение?

Автор: Nab 13.5.2007, 19:51

Цитата(e7x @ 13.5.2007, 19:25

)

вопрос: существует ли какое-нибудь изящное и не очень ресурсоемкое решение?

Конечно сущетвует smile

и не одно ....
но для полного ответа мало данных :(
что это за строки, и упорядочены ли они, то есть 1 строка из A может встретиться в конце B, а 2 строка из A может встретиться в начале B? Это самый тяжелый вариант, но и он имеет не одно решение.....

То есть главный вопрос строки как то упорядочены? И упорядочены ли они одинаково?

Автор: nitr 13.5.2007, 19:54

e7x, ух... не хотел отвечать, очень, так сказать, вы "некультурны".

Цитата(e7x @ 13.5.2007, 19:25

)

вопрос: существует ли какое-нибудь изящное и не очень ресурсоемкое решение?

существует.

В тех же рецептах про это написано как минимум 4 решения. Здесь на форуме воспользуйтесь поиском, найдете эти и множетсва других - оптимальных - решений.

Автор: e7x 13.5.2007, 20:25

обычные строки в ASCII (допустим, предложения английского языка), разделяются переводом строки =)
неупорядочены

Автор: Nab 13.5.2007, 21:31

а средняя длина строк?

Автор: korob2001 14.5.2007, 01:10

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

Автор: e7x 14.5.2007, 06:51

размер строк - менее 255 символов, в среднем - 128 пусть будет smile

уважаемый nitr, не подскажите что за "те же рецепты"? а то я на форуме совсем недавно. поиск по обработке объемных файлов, к сожалению, ничего не дал.

korob2001, спасибо огромное, пойду пробовать =)

Автор: amg 14.5.2007, 07:32

Могу посоветовать хэшировать не сами строки, а их MD5-суммы (модуль Digest::MD5). MD5-сумма вычисляется очень быстро и занимает 16 байт. При количестве строк порядка 100 k вероятность совпадения MD5-сумм для разных строк ничтожно мала. Я сейчас проверил - на хэш из 2 М элементов (ключи - MD5-суммы) хватает 1 Г памяти (на хэш из 2.5 М элементов - уже нет).

Автор: e7x 14.5.2007, 08:57

amg, мд5 был бы классным решением, но исходные строки тоже надо где-то хранить

Автор: amg 14.5.2007, 09:21

Можно просто сделать второй проход по файлу В, это быстро будет.

Код


use Digest::MD5 qw(md5);
my %shash = ();
open A, 'a.txt';
while (<A>) {$shash{md5($_)} = 1}
close A;
open B, 'b.txt';
while (<B>) {
   my $md5 = md5($_);
   if (exists($shash{$md5})) {delete $shash($md5)}
}
seek (B, 0, 0);
open C, '>c.txt';
while (<B>) {
    print C if exists $shash{md5($_)};
}
close B;
close C;

Автор: e7x 14.5.2007, 10:18

amg, респект! =) буду надеяться, что хеши не будут совпадать для разных строк

(шепотом) только в примере надо наверное А перечитывать, ибо его строки нам нужны

Спасибо всем!

Автор: amg 14.5.2007, 11:01

Цитата(e7x @ 14.5.2007, 10:18

)

только в примере надо наверное А перечитывать, ибо его строки нам нужны

Да, конечно. Я не проверял код, прямо в форум писал.

Еще можно хэшировать файл В и пройтись по файлу А, занося все строки, которых нет в хэше, в файл С. Если файлов А и В только по одному, то это менее затратно.

И еще, думаю, имеет смысл при хэшировании подсчитывать кол-во строк и бросать все, если их становится слишком много (или переходить на другой алгоритм, как korob2001 советовал).

Автор: tishaishii 15.5.2007, 14:05

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

Т.е. такая задача: файл A="abdefs", файл Б="abAebs", различия="ab*e*s"? Если я правильно понял, то таких различий должно быть множество.