Вариант 1, гибридный. Работает, если файл образцов (т.е. 1.txt) не очень большой. Грузишь 1.txt в память. Другой файл читаешь построчно и проверяешь против списка строк в памяти.
Вариант 2. Считаешь хэши для строк в обоих файлах. Причем для файла 2.txt сохраняешь и сам хэш, и позицию строки. Сравниваешь хэши, для неотсеяных хэшей потом по позиции строки переписываешь нужные строки в выходной файл.
Кстати, примерный расчет по памяти в случае второго варианта.
Пусть средняя длинна строки будет 40 байт. Размер хэша - 128 бит, т.е. 16 байт. Плюс 32 бита (4 байта) на позицию строки. Т.о. получаем 20 байт. Т.е. сокращение объема данных в 2 раза. Если средняя длинна строки больше, то и выигрыш по пямяти больше.
ЗЫ. Кстати, если грузить в память только один файл, то, как мне кажется, вполне можно уместиться. Пусть у нас 32-битное приложение, т.е. мы можем адресовать 2Гб памяти (вариант расширенной адресации до 3Гб не рассматриваем, хотя он тоже есть). На загрузку одного из файлов уйдет 1Гб, на маппинг системы и самой программы уйдет, ну пусть по макс, еще где-то 0.5Гб. Соответсвенно, у тебя остается около 0.5Гб для данных из второго файла.
ЗЗЫ. Кстати, читать файл, который фильтруешь, можно и блоками. Допустим, читаешь блок из 1000 строк, проверяешь их, потом читаешь следующий блок.
ЗЗЗЫ. Сорри, сумбурно немного. Просто накидывал идеи, все идеи надо проверять против реальных данных, какая эвристика даст лучший результат.
|