Сравнение больших текстовых файлов

Есть два больших (сотни метров) тексовых файла. Они содержат набор коротких (до 100 символов) строк. Количество строк 2-5 миллионов.
Задача - найти все строки одного файла, отсутсвующие во втором.
Кто-то знает более менее быстрый способ для такой процедуры?

ЗЫ Реализация на Delphi или C

В какой-нибудь базе данных это запечь и потом составить 1-2 умных запроса на поиск уников и все

Заказчик упирается. Запихивать в базу не хочет категорически

Если поможет, то сейчас это сделано на Delphi через TFileStream и алгоритм Бойера-Мура. Сам поиск работает достаточно быстро, но перед каждой проверкой необходимо передвинуть внутренний указатель файла, в котором ищем, на начало. Вот эта процедура и жрет время.

Решение 1:
Строки в обоих файлах сортируются. При этом используется сортировка слиянием (merge sort) + поразрядная сортировка (radix sort).
Потом открываются оба отсортированных файла, и последовательно считываются строки в каждом файле, при этом в один проход определяются строки в первом файле, отсутствующие во втором.
В общем, основная задача тут сводится к реализации быстрой сортировки.

Решение 2:
Использование DBM хеша.
Сначала нужно поместить все строки из второго файла в DBM хеш, а потом для каждой строки первого файла проверить факт её наличия в DBM хеше.
Данный метод удобен тем, что получится весьма небольшая программа, нескольких десятков строк на Си должно быть достаточно (при наличии либы для работы с DBM файлами, конечно).

tvv
по 1. Файлы уже отсортированы. Но это мало что дает. Поясню на примере.
1 файл
a1
a2
a3
а4
2 файл
a1
a2
a4
а5
После нахождения а1 можно продолжить поиск а2 с текущей позиции в во втором файле, т.к. любой следующий элемент будет заведо расположен после а1.
После НЕ нахождения а3 мы будем находиться в конце второго файла, и для поиска а4 необходимо откатить указатель в как минимум до позиции а2. Какой-то эффект это начнет давать только ближе к концу файла.

по2. С DBM вообще не желательно связываться. Неизвестно где будет работать программа и что там будет стоять.

elosoft, если файлы уже отсортированы, то задача становится тривиальной.
Достаточно читать из двух файлов параллельно. Допустим, Ваш пример:

1. Читаем строку из первого файла: a1
2. Читаем строку из второго файла: a1, сравниваем a1==a1, это значит что a1 присутствует во втором файле
3. Читаем строку из первого файла: a2
4. Читаем строку из второго файла: a2, сравниваем a2==a2, это значит что a2 присутствует во втором файле
5. Читаем строку из первого файла: a3
6. Читаем строку из второго файла: a4, сравниваем a3 < a4, значит a3 отсутствует во втором файле, выводим a3
7. Читаем строку из первого файла: a4, сравниваем a4==a4, это значит что a4 присутствует во втором файле
8. И т.д.

Обратите внимание, если строка из первого файла "меньше" строки из второго файла, то читать следующую строку из второго файла не нужно, нужно читать следующую строку из первого файла и снова сравнивать с текущей строкой из второго.
И наоборот, если строка из первого файла "больше", то читаем следующую строку только из второго файла, и не читаем из первого.

Итого, достаточно одного прохода, "откатывать указатель" не нужно вообще. Примитивный и максимально быстрый алгоритм.

Алгоритм Бойера-Мура не позволяет сравнить строки. По-крайней мере явно, хотя изголиться конечно можно. Он просто читает блок и по байтно ищет в нем присутствие искомой строки. К тому же, если начать менять направление поиска из1 файла в 2, из 2 в 1, то мне кажется никакого выигрыша это не даст.

Цитата ("elosoft"):

После НЕ нахождения а3 мы будем находиться в конце второго файла, и для поиска а4 необходимо откатить указатель в как минимум до позиции а2. Какой-то эффект это начнет давать только ближе к концу файла.

То есть смотрите выше, если файлы уже отсортированы, то после НЕ нахождения a3 нужно читать не до конца файла, а лишь до тех пор, пока прочитанная строка из второго файла меньше или равна a3. Например, в Вашем случае прочитается a4, a4>a3, значит дальше уже читать не нужно, можно просто вывести "a3 во втором файле не найден".

Цитата ("elosoft"):

Алгоритм Бойера-Мура не позволяет сравнить строки. По-крайней мере явно, хотя изголиться конечно можно. Он просто читает блок и по байтно ищет в нем присутствие искомой строки. К тому же, если начать менять направление поиска из1 файла в 2, из 2 в 1, то мне кажется никакого выигрыша это не даст.

Для данной задачи с поиском совпадающих строк не нужно использовать алгоритм Бойера-Мура. Этот алгоритм предназначен для других задач, а именно, для поиска подстрок в строках.

Цитата ("tvv"):

Для данной задачи с поиском строк не нужно использовать алгоритм Бойера-Мура.

Более быстрого я не знаю. По сравнению, например, с построчным чтением там разница по времени поиска в порядки. К тому же он значительно меньше грузит систему.

ЗЫ Но Вашей идее что-то есть. Найти бы что именно...

Цитата ("elosoft"):

Более быстрого я не знаю. По сравнению, например, с построчным чтением там разница по времени поиска в порядки. К тому же он значительно меньше грузит систему.

Повторюсь, алгоритм Бойера-Мура предназначен для поиска подстрок в строках.
Он НЕ предназначен для решения задачи, которую Вы описали в первом посте.

Цитата ("elosoft"):

ЗЫ Но Вашей идее что-то есть. Найти бы что именно...

В моей идее (хотя что значит моей... это же тривиальный алгоритм на уровне 2+2=4) есть то, что это - оптимальное решение данной задачи. В отличие от алгоритма Бойера-Мура, который тут вообще не к месту.

Цитата ("tvv"):

хотя что значит моей... это же тривиальный алгоритм на уровне 2+2=4

Идея была в том, чтобы отловить момент, когда мы проскочили весь список, где МОГ находиться искомый элемент, и остановиться а не идти до конца. Я, например, не до пер...

Цитата ("elosoft"):

Идея была в том, чтобы отловить момент, когда мы проскочили весь список, где МОГ находиться искомый элемент, и остановиться а не идти до конца. Я, например, не до пер...

Очень просто.
Если текущая прочитанная строка из второго файла больше, чем текущая прочитанная строка из первого, то нужно остановиться, и из второго файла не читать следующую строку.
Вместо этого текущую строку в первом файле отметить как "отсутствует во втором файле", и читать следующую строку из первого файла.

Если возможны дублирующиеся строки в одном файле, то нужно делать еще одну дополнительную проверку, но это уже детали.

ШИНГЛЫ. помяните мое слово.
в принципе на атоме330 2.2млн сравнений можно сделать в секунду