deffss wrote:
> файлы содержат текстовые строки (5000-150000 шт.). Задача: сравнить 2
> файла. на выходе получить результат -строки которые есть в первом файле,
> но нет во втором и наоборот.
> Подскажите, пожалуйста, есть ли какие быстрые алгоритмы сравнения для
> данной задачи? Важна скорость выполнения операции.

На мой взгляд, недостаточно информации о задаче. Упорядоченны ли строки
в файлах, или нет? Как быть с одинаковыми строками? Что считать
совпадающими строками? В каком виде интересует результат - содержимое
строк или номера строк?
Posted via ActualForum NNTP Server 1.4

deffss wrote:
> Автор: "deffss"
> teras
>
> На мой взгляд, недостаточно информации о задаче. Упорядоченны ли строки
> в файлах, или нет? Как быть с одинаковыми строками? Что считать
> совпадающими строками? В каком виде интересует результат - содержимое
> строк или номера строк?
> Posted via ActualForum NNTP Server 1.4
>
>
>
> Результат 2 файла. В первом файле строки, которых нет во втором. Во
> втором файле наоборот.
> Строки не упорядочены, т.е. позиция строки в первом файле может не
> совпадать с позицией этой же строки во втором. Совпадающие строки - две
> одинаковых строки. Одинаковые строки в выходных файлах не нужны.

Тогда два варианта: отсортировать оба файла, удалив совпадающий строки,
затем, выполняем слияние отсортированных последовательностей с
небольшими модификациями относительно выхода: из файлов считываем по
одной строке. равны - значит строка присутствует в обоих файлах,
считываем следующие строки из ОБОИХ файлов. Не нервны - если строка из
первого файла меньше второй - значит она отсутствует во втором
(сохраняем ее). Затем считываем строку из того файла, в котором строка
была меньше.
Второй вариант - создать хеш-таблицу из второго файла, затем - проход по
первому и проверка совпадения. Для уменьшения объема памяти - можно
хешировать не сами строки а их контрольные суммы (например - CRC, SHA,
MD4) в этом случае придется подчитывать строки для сравнения из файла.
для реализации второго подхода можно использовать готовые библиотеки
типа dbm, gdbm, etc...
Posted via ActualForum NNTP Server 1.4

> AndreiNz wrote:
>
> А не проще ли создать два листа и загрузить в каждый строки из
> соответствующих файлов. Затем бежим по первому листу, берем первую
> строку и ищем ее во втором листе простым перебором.

Вообще-то это зависит от перспектив. Тут строк немного, поэтому все
пойдет. Если файлы будут расти, то разница во времени станет заметнее, и
чем дальше - тем больше.

Линейные поиски по несортированному списку - O(n^2),
сортировки и слияние - O(2*log(n)+n),
хеширование - O(n).
Где n - количество строк в обоих файлах.
Posted via ActualForum NNTP Server 1.4