Мы сортируем файл объемом 5 ГБ с 37 полями и сортируем его по 5 клавишам. Большой файл состоит из 1000 файлов по 5 МБ каждый.
Через 190 минут все еще не закончилось.
Мне интересно, есть ли другие способы ускорить сортировку. Мы выбираем unix-сортировку, потому что мы не хотим, чтобы она использовала всю память, поэтому любой подход на основе памяти не подходит.
В чем преимущество сортировки каждого файла независимо, а затем использовать параметр -m для его сортировки?
Буферируйте его в памяти с помощью -S. Например, чтобы использовать (до) 50% вашей памяти в качестве буфера сортировки:
sort -S 50% file
Обратите внимание, что современный Unix sort может сортироваться параллельно. Мой опыт в том, что он автоматически использует как можно больше ядер. Вы можете установить его напрямую, используя --parallel. Сортировка с использованием 4 потоков:
sort --parallel=4 file
Итак, в общем, вы должны поместить все в один файл и выполнить что-то вроде:
sort -S 50% --parallel=4 file
sort -m files
...; -m - POSIX и должны поддерживаться всеми видами, предназначенными для каламбура). Сортировка каждого файла потребляет гораздо меньше ресурсов.Одним из основных потребителей с Unix sort является поиск ключей; это ничего, кроме простой операции сравнения, которую вы обычно видите в простых упражнениях сортировки. Даже найти один из ключей - довольно медленный процесс.
Итак, один из способов ускорить работу - это облегчить поиск sort ключами путем предварительной обработки файла, чтобы 5 ключей, о которых вы упоминаете, находились в передней части каждой строки, а затем сортировали данные ( возможно, используя операции разделения и слияния, предложенные другими), а затем удаление ключей.
Например, если у вас есть поля, разделенные двоеточиями, а ключи сортировки - 1, 3, 7, 10, 12, и они являются обычными алфавитными сортировками, то вы можете использовать:
awk -F: '{print "%s:%s:%s:%s:%s:%s\n", $1, $3, $7, $10, $12, $0; }' monster-file |
sort -t: -k1,1 -k2,2 -k3,3 -k4,4 -k5,5 |
sed 's/^[^:]*:[^:]*:[^:]*:[^:]*:[^:]*://'
Вы даже можете обойтись без пяти опций -k и просто запустить sort -t:. Фактически, вы можете, вероятно, организовать использование другого разделителя (возможно, контрольного символа, такого как ^ A), чтобы упростить код. Вы разделяете ключевые поля из основной записи с помощью этого альтернативного символа:
awk -F: '{print "%s:%s:%s:%s:%s^A%s\n", $1, $3, $7, $10, $12, $0; }' monster-file |
sort -t$'\001' |
sed 's/^[^^A]*^A//'
Здесь используется bash -ism (ANSI-C Quoting) в аргументе $'\001' до sort; элементы ^A в сценариях awk и sed - это то, что вы получаете от ввода Control-A, хотя вы также можете назначить ноту bash для предоставления символа тоже:
awk -F: '{print "%s:%s:%s:%s:%s'$'\001''%s\n", $1, $3, $7, $10, $12, $0; }' monster-file |
sort -t$'\001' |
sed "s/^[^$'\001']*$'\001'//"
(Предупреждение: непроверенные скрипты.)
Там есть увлекательная статья о реорганизации сортировки Unix ( "Теория и практика в построении рабочей упорядоченной рутины", JP Linderman, AT & T Bell Labs Tech Journal, Oct 1984), которая не доступна (I ' вы не нашли его в Интернете, несмотря на несколько попыток его поиска), который описывает, как /bin/sort было улучшено. Даже после всех улучшений одна из его рекомендаций для сложных сортов была именно в этом направлении.
Сортировка Unix не самая быстрая сортировка там любым способом. Он использует странную реализацию, которая легко может быть обогнана над наборами данных, которые достаточно велики, чтобы требовать множественные проходы слияния, как ясно. Я бы посмотрел вокруг на замену. Вы даже можете подумать о загрузке файла в базу данных: вы можете получить лучшую производительность таким образом, и после этого у вас наверняка будут данные в более удобной форме.
Для полноты основной проблемой является сортировка ведра. Он быстрый для небольших наборов данных, хотя и не так быстро, как Quicksort, но он производит в два раза больше запусков, чем выбор замены. Когда вы попадаете в многоуровневое слияние, количество прогонов и, следовательно, количество проходов слияния полностью доминирует на фазе распределения, связанной с процессором.
Я реализовал пакет sort-merge для COBOL много лет назад, прямо из Knuth vol. III, с распределением по выбору замены и сбалансированным слиянием с манекенами. На достаточно больших наборах данных он легко превосходил Unix-сортировку, с увеличением градиента по мере увеличения N, а "достаточно большой" - это не столько большие размеры дисков в эти дни.
Разделите файл на более мелкие файлы, отсортируйте файлы меньшего размера с помощью большого количества cpus, объедините их обратно.
Я делал это в прошлом:
split -l5000000 data.tsv '_tmp';
ls -1 _tmp* | while read FILE; do sort $FILE -o $FILE & done;
sort -m _tmp* -o data.tsv.sorted
это сработало для меня.
Пример производительности 20-строчного файла:
joshua10.13> wc randn20M.csv
20000000 20000000 163197726 randn20M.csv
joshua10.14> cat par_srt.sh
#!/bin/bash
split -l5000000 randn20M.csv '_tmp';
ls -1 _tmp* | while read FILE; do sort $FILE -o $FILE & done;
sort -m _tmp* -o data.tsv.sorted
joshua10.15> time ./par_srt.sh
1.516u 0.344s 0:05.85 31.6% 0+0k 0+522584io 0pf+0w
joshua10.16> time sort randn20M.csv -o dataone.sorted
21.461u 0.596s 0:24.08 91.5% 0+0k 0+318752io 0pf+0w
Примечание: если вы привязаны к вводу/выводу (например, 20-гигабайтный файл с 20 строками), это не поможет.