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

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

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

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

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

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

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

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

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

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


существует.

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

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

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

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

Это сообщение отредактировал(а) korob2001 - 14.5.2007, 01:13

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

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

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

Это сообщение отредактировал(а) e7x - 14.5.2007, 06:59

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

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

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


Это сообщение отредактировал(а) amg - 14.5.2007, 09:22

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

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

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

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

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

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

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

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