java如何有效地获得数百万未排序的浮点数的排名？

Question

有2亿次浮动，可能有些是重复的

什么是一种有效的方法（例如，内存小于1G）来获取其中每个元素的排名（它们一开始是未排序的）

像这样：

输入：[3.2,3.2,3.4,7.81,1.0]

输出：[2,2,4,5,1]

我想到了bitmap sort，但在这种情况下它看起来没有内存效率

Answer 1

我不认为你能在1G内完成所有工作。请注意，200 Mvalue数据集将占用约763 MiB，只剩下约261 MiB可用于辅助数据。这就排除了任何需要在存储值的同时存储索引的方法，因为一个200 mV值的索引至少需要28位。实际上，您确实需要32位，这将占用与原始（大概是32位）浮点值相同的空间

一种考虑的方法是对原始数据执行排序，同时将决策信息记录到位图，然后用秩索引替换原始数据，并使用日志反转排列。p>

然而，在最坏的情况下，产生的排列将需要至少log2(N!) > N log2(N) - N log2(e)位的存储（因此无法通过使用基数排序或其他方法来绕过它）。对于指定的问题，请注意log2(200M)>27所以日志可能需要超过(200M * 25.5) / (8bits/byte) ~ 608 MiB的空间——几乎与原始数据集一样大，并且远大于指定的辅助空间

您可以将决策日志写入磁盘，然后重新读取以生成答案。但是如果你允许磁盘I/O，你也可以做一个外部排序，这将允许你解决比你的内存容量大得多的问题

Answer 2

如果您使用的是标准的Java排序方法和浮点数组，那么您可以使用~1.2GB IMO，因为它已经使用了非常节省空间且快速的（n lg（n））排序方法（TimSort，MergeSort）-请参阅数组。排序

为了更快，您可以将浮点数转换为整数（但需要预先知道精度），然后应用integer sort或前面提到的基数排序