Classificando arquivos binários grandes

Question

Existe utilitário Unix para ordenar arquivos grandes contendo registros binários de tamanho fixo?

Em outras palavras, estou procurando algo como sort (1), mas para arquivos binários com registros de comprimento fixo.

Eu poderia converter os arquivos em texto, então classificar usando sort (1), e então converter de volta na representação binária, mas estou procurando algo mais eficiente em termos de tempo e espaço.

    

Answer 1

Acontece que você está com sorte; existe um programa unix estilo GNU que faz exatamente isso: bsort .

bsort é uma implementação eficiente de uma ordenação radix inplace com atenção especial aos padrões de acesso à memória ao trabalhar com arquivos maiores que o RAM. Por eficiência quero dizer foi capaz de melhor link 2014 tipo de registro 10 ^ 8 eficiente em energia em hardware a partir de meados de 2014 - o recorde foi de 889 Joules, um protótipo inicial deste foi capaz de classificar o mesmo em 335 Joules em um estoque macbook pro. Para conjuntos de dados "pequenos" que se encaixam inteiramente em memória RAM (megabytes de três dígitos), são cerca de 3 vezes mais rápidos que a biblioteca de qsort da libc.

    

Answer 2

Uma solução poderia ser converter o arquivo de entrada em hexadecimal, com cada registro codificado em uma linha separada, classificar isso e converter de volta para binário:

record_size=32
cat input \
    |xxd -cols $record_size -plain \
    |sort \
    |xxd -cols $record_size -plain -revert

No entanto, é lento (o xxd converte cerca de 40MB / s na minha máquina)

Então, como eu precisava, escrevi binsort , que faz o trabalho:

binsort --size 32 ./input ./output

Com --size 32 , ele assume registros de tamanho fixo de 32 bytes, lê ./input , grava registros classificados em ./output .

    

Answer 3

O utilitário de ordenação do Unix é OK para dados binários baseados em locais de byte dentro dos registros, se você se referir a eles em relação ao primeiro "registro". Eg -k1.28,1.32.

A ordenação Unix é menos flexível em relação à sua noção de fim-de-linha. Dependendo dos seus dados, você poderá fazer uma edição de fluxo muito mais simples do que a proposta pelo user68497 baseada em xxd e usar linhas terminadas em null. No entanto, é provável que isso envolva uma grande quantidade de cópias de dados na memória e não se aproxime da velocidade de uma abordagem baseada em mmap.

Se você usar unix sort de alguma maneira, tenha cuidado com o locale. sort supõe que sua entrada é text e locale afeta a ordem de classificação.