Сортировка больших двоичных файлов

Существует ли утилита Unix для сортировки больших файлов, содержащих двоичные записи фиксированной длины?

Другими словами, я ищу что-то вроде sort(1), но для двоичных файлов с записями фиксированной длины.

Я мог бы преобразовать файлы в текст, затем отсортировать, используя sort(1), и затем преобразовать обратно в двоичное представление, но я ищу что-то более эффективное с точки зрения времени и пространства.

Источник

3 ответа

Решение

Оказывается, тебе повезло; есть программа Unix в стиле GNU, которая делает именно это: bsort.

bsort является гиперэффективной реализацией сортировки radix на месте с вниманием к шаблонам доступа к памяти при работе с файлами, большими, чем ram. Под эффективностью я имею в виду, что с середины 2014 года на http://sortbenchmark.org/2014 году была достигнута лучшая энергоэффективность 10 ^ 8 записей на аппаратном уровне - рекорд составил 889 джоулей, ранний прототип этого был способен сортировать то же самое в 335 джоулей на стоковом MacBook Pro. Для "маленьких" наборов данных, которые полностью помещаются в оперативную память (трехзначные мегабайты), это примерно в 3 раза быстрее, чем библиотека qsort в libc.

Источник

Одним из решений может быть преобразование входного файла в шестнадцатеричное, с каждой записью, закодированной в отдельной строке, сортировкой и преобразованием обратно в двоичный файл:

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 менее гибка с точки зрения конца строки. В зависимости от ваших данных, вы можете сделать намного более простое редактирование потока, чем предлагает пользователь x49d на основе xxd, и использовать нулевые завершенные строки. Это все еще может потребовать большого количества копирования данных в память и не приблизится к скорости подхода, основанного на mmap.

Если вы используете сортировку Unix каким-либо образом, будьте осторожны с локалью. сортировка предполагает, что ее вводом является текст, а локаль влияет на порядок сортировки.

Источник
Другие вопросы по тегам