对大型二进制文件进行排序

Question

是否有用于对包含固定长度二进制记录的大文件进行排序的 Unix 实用程序？

换句话说，我正在寻找类似于 sort(1) 的东西，但是对于具有固定长度记录的二进制文件。

我可以将文件转换为文本，然后使用 sort(1) 进行排序，然后再转换回二进制表示，但我正在寻找更节省时间和空间的方法。

Answer 1

一种解决方案是将输入文件转换为十六进制，每条记录编码在单独的行上，对其进行排序，然后转换回二进制：

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

但是，它很慢（xxd 在我的机器上转换大约 40MB/s）

所以，因为我需要它，所以我写了binsort，它可以完成这项工作：

binsort --size 32 ./input ./output

使用 时--size 32，它假定 32 字节固定大小的记录，读取./input、写入已排序的记录到./output。

Answer 2

Unix 的排序实用程序适用于基于记录中字节位置的二进制数据，前提是您相对于第一个“记录”来引用它们。例如 -k1.28,1.32。

Unix 排序在行尾的概念方面不太灵活。根据您的数据，您可以进行比基于 user68497 提出的 xxd 更简单的流编辑，并使用空终止行。尽管如此，这仍然可能涉及在内存中复制大量数据，并且不会接近基于 mmap 的方法的速度。

如果您确实以某种方式使用 unix sort，请注意语言环境。sort 假定它的输入是文本，并且语言环境会影响排序顺序。

Answer 3

事实证明你很幸运；有一个 GNU 风格的 unix 程序可以做到这一点：bsort。

bsort是就地基数排序的超高效实现，在处理大于 RAM 的文件时，会特别注意内存访问模式。我所说的高效是指从 2014 年中期开始就能够在硬件上超越http://sortbenchmark.org的 2014 年能效 10^8 记录排序 - 记录为 889 焦耳，其早期原型能够在库存 MacBook Pro 上为 335 焦耳。对于完全适合 ram（三位数兆字节）的“小”数据集，它比 libc 的 qsort 库快大约 3 倍。