Как в php сравнить два огромных txt файла до 100гб, удалив дубликаты?

Question

[NedoKoder]

Есть ли на PHP возможность, хотя бы растянув процесс на время, сравнив два огромных txt файла по 100гб, удалить дубликаты в нём?

Файлы например имеют следующий формат:

ВОТ ТАК

Файл 1 ||| Файл 2
aaa ||| bbb
bbb ||| 123
ccc ||| aaa

Нужно чтобы остались только уникальные.

ВОТ ТАК

Файл 1:
aaa
bbb
ccc
123

Если бы это были какие то небольшие файлы на несколько десятков тысяч строк, было бы логично. Разбил файлы построчно на массивы функцией file() ...сравнил два массива и готово. Ну или велосипед через mysql с уникальным полем, в который добавляешь все строки в базу, а уже MySQL не дает записывать дубликаты. Потом выгружаешь все данные.

Но как можно на локальной машине запустить php скрипт, который обработает два огромных файла? Хотя бы поработав пол часа, час

Comments

[Дмитрий]

а они отсортированные?

[NedoKoder]

Дмитрий, нет, рандомные

[Дмитрий]

NedoKoder, а надо именно в php?

что нибудь типа такого не покатит?
diff file1 file2 > file3

упс - вам не диф нужен, а удаление дубликатов тогда так:

sort -u file1 file2 > file3

Answer 1

[d'Ivan]

На POSIX системах можно использовать fgrep:

$ cat /tmp/file1.txt
aaa
bbb
ccc
$ cat /tmp/file2.txt
bbb
123
aaa
$ fgrep -f /tmp/file1.txt /tmp/file2.txt
bbb
aaa

Так что на PHP как-то так:

$output = shell_exec('fgrep -f /tmp/file1.txt /tmp/file2.txt > /tmp/dups.txt');

Однако, если требуется выполнять какие-то дополнительные манипуляции, тогда, возможно, лучше сразу импортировать в СУБД.

Добавлено:
упустил факт, что помимо дубликатов нужно оставить и неповторяющиеся значения. Тогда так:

$ sort -u /tmp/file1.txt /tmp/file2.txt
123
aaa
bbb
ccc

$output = shell_exec('sort -u /tmp/file1.txt /tmp/file2.txt > /tmp/dups.txt');

Answer 2

[Wataru]

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

Сортировка очень больших файлов - тоже стандартная тема. Лучше всего, наверно, подойдет radix sort. Правда, нужно будет свободного места на диске чтобы копии файлов тоже помещались, да лучше с запасом. Тут надо будет 3 раза (или какая там у вас длина строки) прочитать файл. Прочитанные строки надо распихивать по 256 (или сколько там символов различных может быть) файлам. Потом все эти файлы надо собрать воедино в нужном порядке.

Надо только хорошо порыться в документации - нужны функции php которые читают файл построчно и не грузят его весь целиком в память. Если, конечно, у вас не ~128гб оперативки. Тогда лучше каждый файл загрузить в память целиком и сортировать quick sort'ом.

Answer 3

[Slava Rozhnev]

Мне кажется проще засунуть файны в базу данных и уже в ней выполнять манипуляции

Comments

[mayton2019]

Такое задание иногда задается на собеседованиях в google, microsoft. И собеседующие
обычно ждут какого-то алгоритмического решения. Хотя база данных является вполне себе
очевидным и промышленным решением.

Тоесть все зависит от амбиций соискателя. Куда он идет. В разработку или в админы.

[Slava Rozhnev]

mayton2019, ну тут да согласен или шашечки или ехать

Answer 4

[Руслан Федосеев]

Запускайте php скрипты не из броузера - и пусть они хоть неделями работают. Ограничение на время работы скрипта - это ограничение для web сервера, чтобы не держать зря коннекты и ресурсы...