Есть ли в Unix утилита для сортировки больших файлов, содержащих двоичные записи фиксированной длины?
Другими словами, я ищу что-то вроде sort (1), но для двоичных файлов с записями фиксированной длины.
Я мог бы преобразовать файлы в текст, затем отсортировать их с помощью sort (1), а затем преобразовать обратно в двоичное представление, но я ищу что-то более эффективное по времени и пространству.
Одним из решений может быть преобразование входного файла в шестнадцатеричный, при этом каждая запись закодирована в отдельной строке, отсортировать ее и преобразовать обратно в двоичный:
record_size=32
cat input \
|xxd -cols $record_size -plain \
|sort \
|xxd -cols $record_size -plain -revert
Однако он медленный (на моей машине xxd преобразует около 40 МБ / с)
Итак, поскольку мне это было нужно, я написал binsort, который выполняет свою работу:
binsort --size 32 ./input ./output
С участием --size 32, он предполагает 32-байтовые записи фиксированного размера, читает ./input, записывает отсортированные записи в ./output.
Утилита сортировки Unix подходит для двоичных данных на основе расположения байтов в записях, если вы ссылаетесь на них относительно первой «записи». Например, -k1.28,1.32.
Сортировка в Unix менее гибка в отношении понятия конца строки. В зависимости от ваших данных вы можете сделать гораздо более простое редактирование потока, чем предлагает пользователь 68497 на основе xxd, и использовать строки с завершающим нулем. Тем не менее, это по-прежнему, вероятно, потребует большого объема копирования данных в памяти и не приблизится к скорости подхода на основе mmap.
Если вы все же используете сортировку unix, будьте осторожны с локалью. sort предполагает, что его ввод - это текст, а языковой стандарт влияет на порядок сортировки.
Оказывается, вам повезло; есть программа unix в стиле GNU, которая делает именно это: bsort.
bsort - это сверхэффективная реализация поразрядной сортировки на месте с особым вниманием к шаблонам доступа к памяти при работе с файлами, размер которых превышает размер оперативной памяти. Под эффективностью я имел в виду http://sortbenchmark.orgЭнергоэффективная сортировка 10 ^ 8 на оборудовании в 2014 году с середины 2014 года - рекорд составлял 889 джоулей, ранний прототип этой системы мог сортировать то же самое в 335 джоулей на стандартном MacBook Pro. Для "небольших" наборов данных, которые полностью помещаются в RAM (трехзначные мегабайты), это примерно в 3 раза быстрее, чем библиотека qsort libc.