Для предыдущего SE вопроса"Какой алгоритм использовать для удаления дубликатов?" Я описал алгоритм для, вероятно, аналогичной проблемы, за исключением файлов 50 ГБ вместо 20 ГБ. Метод быстрее, чем сортировка больших файлов в этой задаче.
Вот адаптация метода к вашей проблеме. Давайте назовем исходные два файла A и B, и предположим, что A больше, чем B. Я не понимаю из вашего описания проблемы, что должно произойти, если или когда будет обнаружен дубликат, но в следующем я предполагаю, что вы хотите оставить файл A без изменений, и удалить из B все элементы, которые также находятся в A. Я также предполагаю, что записи в пределах A определены с самого начала как уникальные в пределах A, и аналогично для B. Если это не так, метод требует больше адаптация и примерно вдвое больше ввода / вывода.
Предположим, что вы можете поместить 1 / k'th файла A в память и по-прежнему иметь место для других необходимых структур данных. Весь файл B затем может быть обработан за k или менее проходов, как показано ниже, и это может быть намного быстрее, чем сортировка любого файла, в зависимости от длины строки и констант алгоритма сортировки. Сортировка средних значений O (n ln n) и приведенный ниже процесс - это O (k n) наихудший случай. Например, если строки в среднем состоят из 10 символов и имеется n = 2G строк, ln (n) ~ 21,4, вероятно, будет примерно в 4 раза хуже, чем O (k n), если k=5. (Константы алгоритма все равно могут изменить ситуацию в любом случае, но с быстрой хэш-функцией метод имеет хорошие константы.)
Процесс:
- Пусть Q = B ( т.е. переименовать или скопировать B в Q)
- Выделите несколько гигабайт для рабочего буфера W и около гигабайта для хэш-таблицы H. Откройте входные файлы A и Q, выходной файл O и временный файл T. Перейдите к шагу 2.
- Заполнить рабочий буфер W чтением из файла A.
- Для каждой строки L в W хеш L в H такой, что H [hash [L]] индексирует строку L.
- Считать все Q, используя H, чтобы обнаружить дубликаты, записать недубликаты во временный файл T.
- Закройте и удалите Q, переименуйте T в Q, откройте новый временный файл T.
- Если EOF (A), переименуйте Q в B и выйдите, иначе перейдите к шагу 2.
Обратите внимание, что после каждого прохода (, то есть в начале шага 6) ни одна из строк в Q не является дубликатами того, что до сих пор считывалось из A. Таким образом, 1 / k'th исходного файла обрабатывается за проход, и обработка занимает k проходов. Также обратите внимание, что хотя обработка будет связана с вводом / выводом, вы можете читать и писать в несколько раз быстрее с большими буферами ( например 8MB), чем построчно.
Алгоритм, как указано выше, не включает в себя детали буферизации или способы обработки частичных строк в больших буферах.
Вот простой пример производительности: предположим, что A, B - это файлы размером 20 ГБ, каждый из которых содержит около 2 ГБ паролей, а дубликаты встречаются довольно редко. Также предположим, что 8 ГБ ОЗУ достаточно для того, чтобы рабочий буфер W был размером 4 ГБ, оставляя достаточно места для хэш-таблицы H, чтобы можно было сказать .6G 4-байтовые записи. Каждый проход (шаги 2-5) читает 20% A и читает и записывает почти весь B, на каждом проходе отсеивая любой пароль, уже замеченный в A. I / O составляет приблизительно 120 ГБ чтения (1 * A + 5 * B) , 100 ГБ написано (5 * B).
Вот более сложный пример производительности: предположим, что около 1G случайно распределенных паролей в B продублировано в A, а все остальное, как в предыдущем примере. Тогда ввод / вывод составляет около 100 ГБ для чтения и 70 ГБ для записи (20 + 20 + 18 + 16 + 14 + 12 и 18 + 16 + 14 + 12 + 10 соответственно).