• XSS.stack #1 – первый литературный журнал от юзеров форума

Алгоритмы сортировки и удаления дублей строк в больших TXT файлах объемом от 1ГБ

Отслеживать
obtim сказал(а):
Этот же файл мультипроцессорный обновленный скрипт не съел.
Почистите папку темп после неуспешной отработки последнего скрипта. У вас должна быть пустая папка темп, по идее файлы сами удаляются полностью, но при условии если скрипт отработал полностью правильно! Попрошу по работе мултипроцессорного скрипта в соответствующей ветке отписываться
 
ради интереса попробовал реализовать это в Postgresql 17

вес файла 14GB
всего строк 1,015,124,933

VPS:
2 CPU
4GB RAM
200GB ssd

cJURG@gmail.com
WOpBc2qqsx@gmail.com
Wpfu6r@hotmail.com
wpOclsa3x@hotmail.com
gnjPO@gmail.com
W34bOs21sac@hotmail.com
VffjS6@hotmail.com
b7y8mx@hotmail.com
72k@gmail.com

SQL: 
CREATE TABLE user_email (
    mail text
);

CREATE UNLOGGED TABLE tmp_table (
    mail text
);

COPY tmp_table FROM '/var/lib/pgsql/14GB.txt'; -- 3m 24s or 204s


--EXPLAIN ANALYZE
INSERT INTO user_email
SELECT DISTINCT mail
FROM tmp_table
ON CONFLICT DO NOTHING;  -- 34m 20s or 2060s

-- count initial    1,015,124,933
-- count after          639,839,160
tmp_table - 42GB
user_email - 27GB

иморт в дб - 3m 24s
удаление дублей - 34m 20s
заняло 40 минут, нашлись 375,285,773 дублей
 
RWTH сказал(а):
ради интереса попробовал реализовать это в Postgresql 17



cJURG@gmail.com
WOpBc2qqsx@gmail.com
Wpfu6r@hotmail.com
wpOclsa3x@hotmail.com
gnjPO@gmail.com
W34bOs21sac@hotmail.com
VffjS6@hotmail.com
b7y8mx@hotmail.com
72k@gmail.com

SQL: 
CREATE TABLE user_email (
    mail text
);

CREATE UNLOGGED TABLE tmp_table (
    mail text
);

COPY tmp_table FROM '/var/lib/pgsql/14GB.txt'; -- 3m 24s or 204s


--EXPLAIN ANALYZE
INSERT INTO user_email
SELECT DISTINCT mail
FROM tmp_table
ON CONFLICT DO NOTHING;  -- 34m 20s or 2060s

-- count initial    1,015,124,933
-- count after          639,839,160
tmp_table - 42GB
user_email - 27GB

иморт в дб - 3m 24s
удаление дублей - 34m 20s
заняло 40 минут, нашлись 375,285,773 дублей
Через DISTINCT в SQL не быстро..... А что будет на файле в 300 гигабайт или хотя-бы в 100?:)
 
Выше сказали про утилиту duplicut
спасибо Eject, 174region174

вес файла 14GB
всего строк 1,015,124,933

Bash: 
VPS:
        2 CPU
        4GB RAM
        200GB ssd 

[txx@host]$ ./duplicut --line-max-size=25 14GB.txt -o 14GB.txt_
duplicut successfully removed 375278762 duplicates and 748140152 filtered lines in 14:24 minutes
[txx@host]$ wc -l 14GB.txt_
639776239 14GB.txt_


VPS:
        8 CPU
        64GB RAM
        200GB ssd

[txx@host]$ ./duplicut --line-max-size=25 14GB.txt -o 14GB.txt_
duplicut successfully removed 375278762 duplicates and 69932 filtered lines in 03:46 minutes
[txx@host]$ wc -l 14GB.txt_
639776239 14GB.txt_

заняло 3.46 минут с 64GB RAM

p.s есть баг с filtered lines, но не критично
 
rand сказал(а):
Через DISTINCT в SQL не быстро..... А что будет на файле в 300 гигабайт или хотя-бы в 100?:)
конфиги для Postgresql не трогал, просто установил и запустил
сделаю тест на 100GB, сегодня выложу
 
Отличная тема
Сталкивался с такой задачей, сортировал 600 гб после слияния нескольких огромных словарей
Решил также методом с heapq и merge, только поскромнее, без мультипроцессорности.
Жаль, было бы неплохо попробовать ваш код.
У меня сначала шла сортировка большого файла, а потом удаление дублей, то есть без set(), но с нагрузкой на диск
 
тест с дб не получился,
но есть другие результаты

посоветовали еще утилиту rling

вес файла: 100GB
всего строк: 5,589,961,999

Bash: 
VPS:
        32 CPU
        128GB RAM
        1TB ssd


~/dedup$ ./duplicut 100GB.txt  -o out.txt
time: 0:00:00:02  0.22% step 1/3: creating output file ...
time: 0:00:00:11  1.19% step 1/3: creating output file ...
time: 0:00:00:48  4.00% step 2/3: cleaning chunk 1/3 (task 1/6) ...
time: 0:00:06:08 41.96% step 2/3: cleaning chunk 2/3 (task 2/6) ...
time: 0:00:13:19 95.25% step 3/3: removing tagged lines ...

duplicut successfully removed 809313207 duplicates and 1618626414 filtered lines in 14:31 minutes



~/dedup$ time ./rling -s -f  -M 92G    100GB.txt out.txt
Memory for cache set to 98784247808 bytes (was 52428800)
   - but this will have no effect, unless -2 is in use
Reading "100GB.txt"... 107442843254 bytes total in 36.8488 seconds
Counting lines...Found 5589961999 lines in 133.5438 seconds
Estimated memory required: 104,857,632 (100.00Mbytes)
Sorting... took 392.3794 seconds
De-duplicating: 4780648792 unique (809313207 duplicate lines) in 24.0934 seconds

0 total lines removed in 24.0934 seconds
Writing to "out.txt"

Wrote 4,780,648,792 lines in 114.2575 seconds
Total runtime 705.5832 seconds

real    11m45.595s

CREATE UNLOGGED TABLE user_password (
password text
);

CREATE UNLOGGED TABLE tmp_table2 (
password text
);


BEGIN;
TRUNCATE tmp_table2;
COPY tmp_table2 FROM '/var/lib/postgresql/17/100GB.txt' FREEZE; -- 12m 28s
END;

CREATE INDEX tmp_table2_password_idx ON public.tmp_table2 ("password"); -- 29m 14s

INSERT INTO user_password
SELECT DISTINCT password
FROM tmp_table2
ON CONFLICT DO NOTHING; -- 21m 08s
ERROR: could not extend file "base/5/16395.369": No space left on device
HINT: Check free disk space.
Time: 1268484.453 ms (21:08.484)

вес файла: 109GB
всего строк: 6,245,142,616

Bash: 
VPS:
        96 CPU
        256GB RAM
        200GB ssd


$ ./rling output.txt out1.txt
Reading "output.txt"...117026130163 bytes total in 46.0359 seconds
Counting lines...Found 6245142616 lines in 31.4355 seconds
Optimal HashPrime is 1610612741
Estimated memory required: 229,938,171,579 (214.15Gbytes)
Processing input list... 4303441907 unique (1941700709 duplicate lines) in 53.9380 seconds
Occupancy is 1499293666/1610612741 93.0884%, Maxdepth=17

0 total lines removed in 0.0000 seconds
Writing to "out1.txt"

Wrote 4,303,441,907 lines in 38.4931 seconds
Total runtime 169.9039 seconds


./rling: 109GB ~ 6,245,142,616 за 3 минуты удалит все дубли если есть много оперативы
./duplicut: 100GB ~ 5,589,961,999 - 15 минут
 
что бы проверять через rling нужно количество оперативной памяти равное проверяемому файлу, не для всех подходит(
 
Zeta сказал(а):
что бы проверять через rling нужно количество оперативной памяти равное проверяемому файлу, не для всех подходит(
Duplicut неплохо я смотрю работает, интересно в прямом сравнении с многопроцессорным алгоритмом на питоне по времени отработки в одинаковых условиях.
 
вес файла: 100GB
всего строк: 5,645,671,539

M@RJ0ry
M4rjoRy
MarjORy
M4rj0rY@20
M4rj0rY@2020
M4rj0rY2021
M4rj0rY21
M4rj0rY_2021
M4rj0rY@2021
M4rj0rY@21

VPS:
16 CPU
64GB RAM
1TB ssd

Bash: 
$ ./duplicut 100GB.txt -o out.txt
time: 0:00:01:04  4.00% step 2/3: cleaning chunk 1/7 (task 1/28) ...
time: 0:00:02:14  6.52% step 2/3: cleaning chunk 1/7 (task 1/28) ...
time: 0:00:04:58 27.31% step 2/3: cleaning chunk 2/7 (task 8/28) ...
time: 0:00:08:16 45.67% step 2/3: cleaning chunk 3/7 (task 13/28) ...
time: 0:00:12:33 63.03% step 2/3: cleaning chunk 4/7 (task 19/28) ...
time: 0:00:15:18 75.44% step 2/3: cleaning chunk 5/7 (task 23/28) ...
time: 0:00:19:29 97.30% step 3/3: removing tagged lines ...
duplicut successfully removed 1181192640 duplicates and 6714090245 filtered lines in 20:19 minutes ~ 1200s



Bash: 
$ ./main.py 100GB.txt -o out.txt
INFO - Параллельное слияние 3 временных файлов с использованием 16 потоков
INFO - Слияние завершено. Уникальных строк: 4464478899, дублей удалено: 727677004
INFO - Финальное слияние завершено. Уникальных строк: 4464478899, дублей удалено: 727677004
INFO - Временная папка /root/dedup/TEMP успешно удалена.
INFO - Все временные файлы удалены. Уникальных строк: 4464478899, Дублей удалено (на всех этапах процессов слияния): 1181192640
INFO - Всего обработано строк: 5645671539
INFO - Удаление дублей и сортировка заняли 5259.70 секунд



Bash: 
$ ./rling -f 100GB.txt out.txt
Reading "100GB.txt"... 106706305012 bytes total in 25.2937 seconds
Counting lines...Found 5645671539 lines in 120.8671 seconds
Estimated memory required: 104,857,632 (100.00Mbytes)
Sorting... took 809.2972 seconds
De-duplicating: 4464478899 unique (1181192640 duplicate lines) in 65.1923 seconds

0 total lines removed in 65.1927 seconds
Final sort in 224.5970 seconds
Writing to "out.txt"

Wrote 4,464,478,899 lines in 150.7413 seconds
Total runtime 1399.6377 seconds


Zeta сказал(а):
что бы проверять через rling нужно количество оперативной памяти равное проверяемому файлу, не для всех подходит(
работает и с большими файлами
-f Use files instead of memory (slower, but small memory)
 
RWTH сказал(а):
Bash:
INFO - Удаление дублей и сортировка заняли 5259.70 секунд
Чёт ты неправильно готовишь, у меня 300 гиговый файл без дублей 8000 секунд обрабатывало на конфиге в 2-3 раза ниже по cpu и озу чем у тебя. А тут с дублями такой печальный результат. В районе 2000~ должно быть.
 
Последнее редактирование:
OS - Ubunutu 24,
python3 завернут в virtualenv
SWAP раздел выключен
файл для теста сделан так - первые 90GB уникальные, и в конце 10GB дубли
while read p; do ./psudohash.py -w "$p" -cpa -y 2020-2024 -q; done <username.txt

заметил что в конце при слиянии не все ядра использовались
 
RWTH сказал(а):
OS - Ubunutu 24,
python3 завернут в virtualenv
SWAP раздел выключен
файл для теста сделан так - первые 90GB уникальные, и в конце 10GB дубли


заметил что в конце при слиянии не все ядра использовались
Это нормально. Узкое место этого алгоритма. Как это побороть питоном я так и не придумал. В процессе обработки параллельно ничего не крутилось?
 
rand сказал(а):
Это нормально. Узкое место этого алгоритма. Как это побороть питоном я так и не придумал. В процессе обработки параллельно ничего не крутилось?
нет в фоне ничего не было, запустил по очереди каждый тест
забыл упомянуть - Ubuntu было в docker
 
RWTH сказал(а):
нет в фоне ничего не было, запустил по очереди каждый тест
забыл упомянуть - Ubuntu было в docker
может в этом причина, на физических тачках скорость раза в 2-3 на таких размерах должна быть выше, тестировалось на винде и на линуксе.
 
rand сказал(а):
Как реализовать такой функционал
Тоже очень хочу посмотреть алгоритмы.
Не знаю как работает "sort" и "sort -u" в *nix системах (есть код на гитхабе, но я тупой не могу разобратся).

Еще один интересный алгоритм удаления дублей в больших файлах реализован в тулзе App.Merge от BlandyUK
Берется строка
Генерируется файл с именем md5(string) и урезается до 2-4 символов, например 0de4f
В него записываются строка

Таким образом у нас есть много мелких файлов с которых уже по очереди удаляются дубли
После чего все это дело объединяется обратно в один файл без дублей.

Ждем еще идей...

p.s. Понял. Вы тут тестируете программы, а я думал алгоритмы их работы обсуждаете.
 
Последнее редактирование:
Guron_18 сказал(а):
Тоже очень хочу посмотреть алгоритмы.
Не знаю как работает "sort" и "sort -u" в *nix системах (есть код на гитхабе, но я тупой не могу разобратся).

Еще один интересный алгоритм удаления дублей в больших файлах реализован в тулзе App.Merge от BlandyUK
Берется строка
Генерируется файл с именем md5(string) и урезается до 2-4 символов, например 0de4f
В него записываются строка

Таким образом у нас есть много мелких файлов с которых уже по очереди удаляются дубли
После чего все это дело объединяется обратно в один файл без дублей.

Ждем еще идей...

p.s. Понял. Вы тут тестируете программы, а я думал алгоритмы их работы обсуждаете.
Гурончик, это ты какой-то урезанный bloom filter описываешь.
 
Rling
Bash: 
rling inputfile.txt outputfile.txt
rling clean-list.txt clean-list.txt

This will read clean-list.txt, remove all duplicate lines, and re-write it (in original order) back to clean-list.txt. This use is permitted (maybe not recommended, but permitted), because all of the input file is read into memory prior to opening the output file for writing. Great if you are short on disk space, too.

Но к нему вопросы тоже есть ,Emeditor после сортинга тоже находит дубли.
Тестил работу на строках из логов .
 
admin


Напишите ответ...
  • Вставить:
Прикрепить файлы
Верх