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

#c #c #algorithm #data-structures #comparison

#c #c #алгоритм #структуры данных #сравнение

Вопрос:

Если у вас есть два в основном идентичных файла с 1000 записей, как вы будете писать код, чтобы найти различия между ними. Предположим, что команды unix / linux не разрешены для использования.

Моя идея:

Поскольку большинство записей одинаковы, мы можем отсортировать записи двух файлов, а затем сравнить каждую запись одну за другой, например, запись i в file1 сравнивается с записью i в file2. Это O (n lg n), n — размер файла.

Есть ли O (n) решение?

1. Это звучит ужасно похоже на домашнее задание…

2. До определенного размера входных данных хэш-таблицы могут дать вам линейное время.

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

4. Возможно и то, и другое, нам нужно рассмотреть 2 случая.

5. @GWW Я так не думаю, но тогда я никогда не посещал уроки программирования.

Ответ №1:

Хэш-таблицы — ваши друзья.

Получить запись из файла 1.
Хэшируйте его.
Получите соответствующий адрес памяти.
Установите его на 1 .
Повторите для всех записей в файле 1.
Повторите для всех записей в файле 2, но добавьте 2 вместо значения 1.

Теперь вы знаете, какая запись существует в обоих файлах (значение 3), которая существует только в первом файле (значение 1), а которая существует только во втором файле (значение 2). И за линейное время.

Примечание: Если вы реализуете свою собственную хэш-таблицу, вам придется обрабатывать увеличение размера вашей таблицы по мере необходимости, а также коллизии. Я уверен, что если бы вы могли это сделать, то вам не составило бы труда ответить на этот вопрос, поэтому используйте библиотеку.

1. Если у вас нет идеального хэша, вы, вероятно, получите значения выше 3. Что вы планируете делать в этом случае?

2. Обнаружение столкновений должно быть реализовано с помощью хэш-таблицы, я упрощал… хотя, если бы кто-нибудь попросил меня реализовать это, я бы просто сохранил другой хэш каждого объекта вместе с его счетчиком (подверженный ошибкам, но настолько маловероятный, что я бы не беспокоился о домашней работе).

3. Вы всегда можете хэшировать хэш. (Это быстрее.)

4. @paxdiablo: поскольку мы здесь говорили о коллизиях, я бы предположил, что у вас есть две записи E1 и E2 и это h(E1) == h(E2) , однако это не означает, что E1 == E2 и, следовательно, решение Арне имеет смысл.

5. @bdares О, упс. 🙂 Ну, вы всегда можете создать хэш из половины данных, а также ваш «полный хэш». Это все еще быстрее и не так подвержено ошибкам, как мое первоначальное предложение. 😉