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

Question

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

Моя идея:

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

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

Answer 1

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

1. Получить запись из файла 1.
2. Hash it.
3. Получить соответствующий адрес памяти.
4. Установить ее на 1.
5. Повторите для всех записей в файле 1.
6. Повторите для всех записей в файле 2, но добавьте 2 вместо значения 1.

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

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