0

有2 亿个浮点数，也许有些是重复的。

什么是获得其中每个元素排名的有效方法（例如，内存小于 1G）（它们最初是未排序的）？

像这样：

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

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

我想到了bitmap sort，但在这种情况下它看起来并不节省内存。

4

5 回答 5

1

我认为您无法在 1G 中完成所有操作。请注意，您的 200 Mvalue 数据集将占用 ~763 MiB，仅留下 ~261 MiB 可用于辅助数据。这排除了任何需要您同时存储索引和值的方法，因为 200 个 Mvalue 的索引至少需要 28 位。实际上，您确实需要 32 位，这将占用与原始（可能是 32 位）浮点值相同的空间。

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

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

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

于 2012-08-23T00:00:40.407 回答
0

您不想对数组进行排序，但您想获得排序后位置所在的索引数组。它需要超过 1 GB 的内存，并且您可能需要进行一些后处理才能使相等的元素具有相同的等级，但您应该能够使用此解决方案作为起点：获取索引排序后的数组？

于 2012-08-22T21:19:27.067 回答
0

您可以根据浮点数的值对浮点数范围进行排序，int例如Float.floatToRawInt(float).

如果您有 1 GB 并且每个值存储 8 个字节，则可以对多达 1.28 亿个或 2^27 个值的组进行排序。这意味着您将能够通过 2^5 或 32 次传球对它们进行排名。

于 2012-08-22T21:26:35.903 回答
0

您可以尝试按照维基百科的说明进行外部排序。

在处理浮点数据时尝试使用内存映射文件。

public static void main(String[] args) throws IOException {
    RandomAccessFile raf = new RandomAccessFile("floats.dat", "rw");
    FileChannel fc = raf.getChannel();
    MappedByteBuffer mbb = fc.map(FileChannel.MapMode.READ_WRITE, 0, 1024 * 1024 * 1024);
    FloatBuffer fb = mbb.asFloatBuffer();
    Random random = new Random();
    for (int i = 0; i < 200000000; i++) {
        float rand = random.nextFloat();
        fb.put(rand);
    }
    fb.flip();

    // Read data in chunks, tune the size
    float[] f = new float[100000];
    fb.get(f, 0, f.length);

    // Process the data using some merge strategy
}

据我了解，不应该对浮点数组本身进行排序。也使用内存映射文件存储 int 数组。

于 2012-08-22T21:27:38.117 回答
0

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

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

于 2012-09-02T21:35:54.530 回答