Итак, у меня есть очень большой файл (около 10 ГБ), и мне нужно его отсортировать, как при использовании утилиты sort, но более эффективно.
Проблема в том, что у меня нет памяти, мощности процессора, времени или свободного места для подкачки, чтобы обеспечить всю сортировку.
Хорошо то, что файл уже частично упорядочен (я могу сказать, что расстояние каждой строки от его конечной позиции меньше некоторого значения N). Этот вид напоминает мне классический пример компьютерного класса использования для этой цели heapsort с размером кучи N.
Вопрос: есть ли какой-нибудь инструмент unix, который уже делает это эффективно, или мне нужно самому написать код?
Спасибо -mk
Было бы проще разбить файл на более мелкие разделы и отсортировать их. Разделять:-
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. Самый быстрый способ выполнить свою работу:
sort myfile
это означает временную сложность O (n logn) и время O (n).
Если вы разделите данные, вы, вероятно, заплатите за это временем.
В приведенном выше коде есть проблема. Использование опции sort -m не гарантирует взаимную сортировку файлов.
из руководства по unix:
-m, --merge
merge already sorted files; do not sort
например
file1: a b c k l q file2: d e m
sort -m file1 file2
а б в к л д д м
что не в сортировке.
Также тот факт, что элементы находятся в местах меньше N, не гарантирует отсортированный вывод с помощью приведенного выше кода:
файл: a e b c d h f g
в файле N = 3 и все элементы меньше чем на 3 места, чем их положенное место
файл1: hf g, файл2: b c d, файл3: a e
sort file1
производит:
файл1: f g h, файл2: b c d, файл3: a e
и
sorm -m file3 file2 file1
выходы:
а д б в г д е ж з
что неправильно.