Новая тема   Ответить

 atrius
Надо на сервере сортировать на уникальность большие текстовые файлы.
Сейчас работает sort -u, но это не быстро как-то.
При этом видно, что практически все ресурсы сервера простаивают.
Есть какие-нибудь современные аналоги сорта?
сервер dual e5 xeon, 96 ram
текстовые файлы содержат строки до 256 символов
размер файлов от 300 до 700 гигабайт
Спасибо

 Дартаньян
Скинь, несколько строк из лога.

 atrius
бро, из какого лога?
сорт логов не ведет, принцип его работы виден в папке /tmp

 Дартаньян
atrius: пардон я имел введу txt =).

 atrius
абсолютно случайный набор символов. только буквы и цифры и знаки препинания. бинарных данных нет. разделитель строк \n, язык английский.
если грубо, то это списки урлов.

 Дартаньян
atrius:
вечером отпишу если навояю python скрипт =), для "размер файлов от 300 до 700 гигабайт ", а сколько хоть в нем строк wc -l имя файла.

 uname_
на питоне??? 700Гб?? ну-ну

а можно задачу целиком? только удалить дублирующиеся строки? или сортировка тоже нужна?

 Yacc
500 гиговые файлы быстро не получится в любом случае. Сам по себе sort достаточно эффективен, узкое место - дисковый ввод/вывод от которого с файлами такого размера никуда не денешься. Отсюда вывод: сортировать файлы которые полностью помещаются в памяти. То есть нужно пересмотреть механизм получения этих файлов на предмет их размера: накопился гиг - сортируй. Если это технически сложно или не возможно, а также если такая задача встаёт на регулярной основе правильным будет использовать базу данных.

 uname_
если задача - только удалить дубликаты и на сервере реально 96 ram оперативки, есть решение намного быстрее sort'а. Если надо, могу написать на плюсах (бесплатно, люблю такие задачи...)

 ibiz
где-то у меня был .sh скрипт для такой сортировки
большой файл делится на файлы размером RAM/4 и затем несколько алгоритмов на выбор bubble, merge sort и еще два
я отказался, и решил задачу через LOAD DATA и выборкой нужных мне данных из базы

 atrius
спасибо всем.
расскажу подробнее. разбивать файлики на маленькие - мысль хорошая, но проблема в том, что потом полученные файлы надо между собой уникализировать. в принципе, именно так сорт и работает, вот только совсем не понятно как его научить его полученные маленькие файлы в память грузить и сортировать там?. сорт-же тупо в /tmp складывает файлы. причем память юзает очень ограниченно.
по поводу написать на питоне - спасибо конечно, но вряд ли получится быстрее сорта стандартного.
по поводу с++ - наверное тоже самое, но если интересно, то исходнику буду рад.
родилась идея, но админа нет в онлайне...
может есть способ подмантировать /tmp как ramfs? может это ускорит процесс? P.S. памяти реально 96 гигов, и правда 2 e5-4620 процессора

 atrius
в добавку.
не пробовал конечно, но есть идея, что вставить файл такого размера в маську с уникальным полем - затея гораздо худшая чем сортировка посредством стандартной утилиты.
и еще добавка
задача - только уникализировать, сортировать по алфавиту или еще как не надо.

 Дартаньян
atrius:, количество строк, это и есть индекс, запускаем по процессу на ядро, делим количество строк файлов на количество процессов. ищем из исходного файла совпадения, если есть записываем номер строки. в конце заменяем дубляжи на перенос строк, после чего удаляем двойной перенос.

Или пробегаем в процессах удаляем дубляжи и записываем в другой файл одну строчку. Строку она будет уникальной.

Другой более ебанутый вариант, SQL база с но уник значением, записываешь туда она не пропустит наверняка, только база станет весить уже несколько терабайт.

Спасибо за минуса я им так рад.

 uname_
всё проще если не нужна сортировка

1. первый read проход по файлу
в памяти создать хэш
crc32(строки) -> массив вхождений строки (оффсеты)

2. второй read проход файла
читаем входной и пишем в выходной файл
если оффсет "дублирующийся", сохраняем саму строку в памяти (для дальнейшей проверки) и копируем только первое вхождение строки

тут многое зависит от процента дупликатов, если их ОЧЕНЬ много то будут проблемы.
если нет - должно быть сильно быстрее

 uname_
если есть такая инфа - размер входного и выходного файла, и wc -l + размер файла, это бы помогло. Просто так в пустоту писать тоже неохота...

 atrius
Кста, а кто реально минусует?
мне вон тоже минусик проставили =))

 atrius
wc -l сделаю ближе к вечеру. сейчас уехал до дома

 johndoe2
1. Разбиваешь один большой файл на файлы примерно по N байт.
1.1. Открываешь файл, fseek(N,SEEK_SET), по байту читаешь, пока не найдешь конец строки в позиции N1, сохраняешь 0..N1 в F1.
1.2. fseek(N,SEEK_CUR) ... N2, N1+1..N2 -> F2
...
2. Сортируешь файлы F1..Fm любым способом
3. Сливаешь отсортированные маленькие файлы в один большой
3.1. Открываешь все файлы, указатель на начало.
3.2. Считываешь из каждого файла первую строку.
3.3. Сравниваешь строки и пишешь на выход самую "маленькую".
3.4. Из файла, строка которого пошла на выход, читаешь новую строку.
3.5. Переход на 3.3

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

 uname_
uname_ писал:

нет, не получается быстрее, выходит практически 1-1 со стандартным sort

кстати у меня на ubuntu 12.10 sort использует несколько ядер процессора, а памяти ему много и не надо...

 Дартаньян
uname_: если выгрузить частично в память то будет шустрей или тот трюх с хешами.

 uname_
Я вот походил, подумал - короче, всё зависит от циферок, о которых я спрашивал.

Если дубликатов < 1-2%, то можно сделать сильно быстрее, и я придумал как.

Если дубликатов больше, то без сортировки не обойтись, и c наскока быстрее не сделаешь... юниксовый сорт уже наверное лет 30 пилят

 Дартаньян
uname_: что да, то да, 10 лет назад народ ждал что вот-вот запилят, а воз и тут посей день.

 uname_
Да я б не сказал, что он медленный. 400 мегабайт сортирует за 2 минуты (ssd). Это плохо разве? Быстрее хрен сделаешь...

 Дартаньян
uname_: только если выгружать пачку в память.

 idk2045
уникальные строки - это значит строить индекс. а кто может строить индекс по строке быстрее СУБД?
самописный скрипт точно вряд ли.
так что я за базу. по крайней мере надо сравнить производительность с sort'ом.