java - 使用 Java 对数百万个 int/string 对进行排序

Question

我在一个文本文件中有 50,000,000 个(整数、字符串)对。整数是以毫秒为单位的时间，因此长度为 13 位数字(例如 1337698339089)。

文本文件中的条目是这样的:

1337698339089|blaasdasd
1337698339089|asdasdas
1337698338089|kasda

可以有相同的条目。

我想对整数条目进行排序(按升序)，保留任何重复的整数并保留(整数，字符串)对。我采用的方法会导致内存错误，因此我正在寻找替代方法。

我的方法是这样的(使用一些伪代码):

// declare TreeMap to do the sorting
TreeMap<Double, String> sorted = new TreeMap<Double, String>();

// loop through entries in text file, and put each in the treemap:
for each entry (integer, string) in the text file:

   Random rand = new Random();
   double inc = 0.0;

   while (sorted.get(integer + inc) != null) {
       inc = rand.nextDouble();
   }

   sorted.put(integer + inc, string);

我在这里使用随机数来确保可以在 TreeMap 中输入重复的整数(通过将它们递增 0 到 1 之间的两倍)。

// to print the sorted entries:
for (Double d : sorted.KeySet()) {
    System.out.println(Math.round(d) + "|" + sorted.get(d));
}

这种方法有效，但在 50,000,000 个条目时失效(我认为是因为树状图变得太大；或者可能是因为 while 循环运行的时间太长)。

我想知道更有经验的程序员会采用什么方法。

非常感谢!

Answer 1

如果你有足够的内存，你应该可以用一个列表来做到这一点。我会为条目创建一个单独的类:

class Foo : Comparable<Foo> {
    private final long time;
    private final String text;

    // Constructor etc
}

在内存方面，您需要能够存储 5000 万个实例，以及对它们的引用。在 32 位 JVM 上，这将是:

• 每个对象 8 字节的开销 (IIRC)
• 8 个字节用于时间
• text 字段为 4 个字节
• ~54 字节用于字符串(8 字节开销 + 三个 int 字段 IIRC + char[] 数组引用 + ~32 字节用于 10 个字符的数组)<
• 4字节用于数组或ArrayList
中的引用

因此，每个实例大约有 80 个字节 - 假设 100 个四舍五入。要存储其中的 50,000,000 个，需要 5,000,000,000 字节，也就是 5GB，我认为这比 32 位 JVM 可以处理的要多。

因此，要在内存中执行所有这些操作，您需要一台 64 位机器和 64 位 JVM，然后由于较大的引用等原因，开销可能会有所增加。可行，但不是非常令人愉快。

然而，其中很大一部分是由于字符串。如果你真的想提高效率，你可以创建一个巨大的字符数组，然后将偏移量存储到 Foo 中。像读文本数据一样读入数组，排序后用它写出数据。更复杂、更丑陋，但内存效率更高。

或者，您可以不全部在内存中执行此操作 - 我敢肯定，如果您四处搜索，您会发现很多关于通过文件系统排序的信息。