使用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);

我在这里使用随机数来确保可以在树形图中输入重复的整数(通过将它们在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个字节 time
• text字段为4个字节
• 字符串约为54字节(8字节开销+ 3 int字段IIRC + char[]数组引用+ 10字符数组约32字节)
• 4个字节用于数组中的引用或 ArrayList

所以每个实例大约有80个字节 - 比如100个向上舍入.要存储50,000,000个字节,需要5,000,000,000字节,即5GB,这比我相信的32位JVM还要多.

因此,要在内存中完成所有这些操作,您将需要64位计算机和64位JVM,然后由于更大的引用等原因,开销可能会有所增加.可行,但不是非常令人愉快.

然而,很大一部分原因是弦乐.如果你真的想要高效,你可以创建一个巨大的char数组,然后在其中存储偏移量Foo.在读取文本数据时读入数组,然后在排序后使用它来写出数据.更复杂,更丑陋,但内存效率更高.

或者,你可以这样做不是所有的内存-我敢肯定,如果你搜索你周围会发现很多信息通过文件系统排序.