Unix-сортировка для частично упорядоченных наборов данных
Итак, у меня очень большой файл (около 10 ГБ), и мне нужно его отсортировать, как при использовании утилиты sort, но более эффективно.
Проблема в том, что у меня нет памяти, мощности процессора, времени или свободного места подкачки для питания всего вида.
Хорошо, что файл уже частично упорядочен (могу сказать, что расстояние каждой строки от ее конечной позиции меньше некоторого значения N). Этот вид напоминает мне классический пример компьютерного класса по использованию для этой цели heapsort с кучей размера N.
Вопрос: Есть ли какой-нибудь инструмент Unix, который уже делает это эффективно, или мне нужно самому его кодировать?
Спасибо -мк
2 ответа
Было бы проще разбить файл на более мелкие разделы и отсортировать их. Разделять:-
split --lines=100000 large_file file_part.
Затем отсортируйте каждый из них, используя обычную сортировку
for suffix in `ls file_part.* | cut -f2 -d.`
do
sort file_part.${suffix} > file_sorted.${suffix}
done
затем вы можете объединить с помощью сортировки слиянием
sort -m file_sorted.*
Это должно быть намного проще на вашей машине.
Сортировка, использование алгоритма R-way merge sort. Самый быстрый способ сделать вашу работу будет:
sort myfile
это подразумевает O(n logn) временную сложность и O(n) время.
Если вы разделите данные, вы, вероятно, заплатите их по времени.
Код выше имеет проблему. С сортировкой -m файлы не гарантируются для взаимной сортировки.
из руководства по Unix:
-m, --merge
merge already sorted files; do not sort
например
файл1: a b c k l q файл2: дем
sort -m file1 file2
a b c k l q d e m
который не в своем роде.
Кроме того, тот факт, что элементы находятся в местах, которые меньше N, не гарантирует сортированный вывод с приведенным выше кодом:
файл: aebcdhfg
в файле N=3 и все элементы занимают менее 3 мест, чем их правильное место
файл1: hfg, файл2: b c d, файл3: a e
sort file1
производит:
файл1: фгх, файл2: b c d, файл3: a e
а также
sorm -m file3 file2 file1
выходы:
aebcdfgh
что неправильно.