0 language-agnostic sorting algorithm
这出来是不可理解的.我会改写
是否有一种算法或方法允许以这样的方式对数组进行排序,从而最大限度地减少连续元素之间的差异？
struct element
{
uint32 positions[8];
}
这些记录对顺序不敏感.
输出文件格式定义为:
byte present; // each bit indicating whether position[i] is present
uint32 position0;
-- (only bits set in Present are actually written in the file).
uint32 positionN; // N is the bitcount of "present"
byte nextpresent;
所有记录都保证是唯一的,因此0的"当前"字节表示EOF.通过使用当前字段更新"当前"结构来解析文件,并将结果添加到列表中.
例如:{1,2,3},{
2,3,2 },{ 4,2,3 } 将:111b 1 2 3 001b 4 111b 2 3 2从未
排序的方法中保存2个数字.
我的目标是最小化输出文件大小.
我认为这个问题应该用'压缩'来标记.
据我了解,你有无序的记录,由8个4字节整数组成:总共32个字节.您希望以最小文件大小存储这些记录,并决定使用基于汉明距离的某种形式的增量编码.您正在询问如何为您构建的压缩方案对数据进行最佳排序.
从你告诉我们的内容来看,我没有看到你按照你所描述的方式分割你的32个字节的任何真正原因(除了字边界很方便)!如果你得到相同的数据,你真的在乎它是否被编码为8个4字节,或16个2字节,或者是一个巨大的32字节整数？
此外,除非问题领域的某些内容使您的方法成为最受欢迎的,否则您最好的选择可能是使用经过实践检验的压缩方案.您应该能够找到已编写的代码,并且您将获得典型数据的良好性能.
回到原来的问题,如果你真的想采取这条路线.很容易想象选择一个起始记录(我认为它不会产生太大的差别,但选择'最小'或'最大'可能是有意义的),并计算汉明距离到所有其他记录.然后,您可以选择具有最小存储距离的那个,然后重复.显然这是记录数量的O(n ^ 2).不幸的是,这篇论文(我没有详细阅读或理解)使得计算从一个字符串到另一个字符串的最小汉明距离本身就很难,并且没有非常好的近似值.
显然,通过根据汉明权重(归结为32字节整数的总体数)对记录进行排序,可以获得更好的复杂性,即记录数量为O(n log(n)).然后对结果使用一些差异编码.但是我不认为这会产生一个非常好的压缩方案:从0到7的整数最终可能会像:
000,100,010,001,101,011,110,111
0,4,2,1,5,3,6,7
这让我们回到了之前问过的问题:你确定你的压缩方案比你的特定数据更标准吗？