使用浮点值的字节表示进行排序

Question

12

如果有一段 8 字节的数据，将双精度浮点数写入其中，在什么情况下数值比较和字典序排序会产生相同结果？

我认为，如果这个数字是正数，并且表达方式是大端序，那么浮点数的数值排序将与字典序排序的字节顺序匹配。

这个想法是，首先按指数排序，然后按尾数排序。即使是“非规格化”的 IEEE 表示法也不应该有任何问题。

这是真的吗？

（我正在使用 Node 的 Buffer::writeDoubleBE，但这并不重要。）

我认为，一个简单的修改可以将其扩展到负数：对所有正数进行 XOR 运算，结果为 0x8000...，对所有负数进行 XOR 运算，结果为 0xffff...。这应该翻转两个数字的符号位（所以负数排在前面），然后反转负数的排序顺序。有人看到这里是否存在问题？

- cloudfeet

虽然不是C++，但Java Math具有nextUp和类似的函数，可用于广泛的单元测试。 - Joop Eggen

@JoopEggen 我希望得到一个通用的“否”或“可以肯定”。当涉及到位级别的东西时，在我手头上运行一些消费者机器的测试并不能给我足够的信心。我希望有些比我稍微低级的经验的人能够说：“是的，鉴于 XYZ，这将在所有架构上都能工作。” - cloudfeet

1

注意：使用这种方法，-NaN值将被排序为低于-Inf，而+NaN值将被排序为高于+Inf。根据使用情况，这可能有意义，也可能没有意义（它打破了±Inf是可能值范围的边界的假设——另一方面，除了在“数字”范围之外，还有哪里可以对NaN值进行排序呢？） - saxbophone

2个回答

2

如果您想让基数排序保持稳定的排序算法，您需要再次交换负部分中相等元素的所有子部分，因为当您交换负数时，原始的稳定排序是有序的。

奥斯陆大学副教授Arne Maus

- Arne Maus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Netch · Accepted Answer

您的方法：

我认为一个简单的修改可以将其扩展到负数：用0x8000...异或所有正数和0xffff....异或所有负数。这应该会翻转两者的符号位（使负数排在前面），然后反转负数的顺序。有人看到问题吗？

绝对是正确答案。此外，例如在dBase和克隆版本中用于组织对浮点列的排序，我猜新的数据库也会采用这种方式。

而且，它与IEEE-754二进制表示的“全序”相同。（但不适用于十进制，后者更加复杂。）

更新：如@Sneftel所建议：在转换为位字符串之前，您可以发现将-0替换为+0很有用。