12

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

文本文件中的条目如下所示：

1337698339089|blaasdasd
1337698339089|asdasdas
1337698338089|kasda

可以有相同的条目。

我想对整数上的条目进行排序（按升序），保留任何重复的整数并保留 (integer, string) 对。我采取的方法会导致内存错误，因此我正在寻找替代方法。

我的方法是这样的（使用一些伪代码）：

// 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 循环运行时间过长）。

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

非常感谢！

4

8 回答 8

13

如果您有足够的内存，您应该可以使用列表来执行此操作。我会为条目创建一个单独的类：

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

    // Constructor etc
}

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

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

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

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

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

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

于 2012-05-22T15:14:40.603 回答
2

我可能会考虑使用数据库（如 H2；这很方便，因为您可以将其直接拉入您的 Java 项目）并按照您想要的方式设置索引。数据库已经解决了处理大量数据和组织数据的问题。然后您可以执行 SQL 查询以按顺序获取结果并将它们写回。

结果集会将数据分块流式传输给您；不要尝试将所有内容加载到单个列表中。

虽然 H2 确实支持内存；在这种情况下，我会将其配置为使用磁盘，除非您有大量 RAM 和 64 位 Java。

于 2012-05-22T15:15:59.480 回答
1

为什么使用 adouble来存储 a long？

AMap<Long, String>不能有重复的键。一个会覆盖另一个。

我怀疑您是否可以将所有这些都放入记忆中。那是 0.5 GB 仅用于存储长整数，更多用于存储字符串。使用 32 位 JVM 可能无法做到这一点。

于 2012-05-22T15:12:57.947 回答
1

你给 JVM 更多内存了吗？尝试使用 -Xmx1024M 命令行选项运行它。而且 treeMap 显得不必要的复杂，你可以使用内置的 Java 命令

于 2012-05-22T15:18:36.790 回答
1

您的问题看起来有两部分：

  1. 算法：我建议使用一些内置的 java 排序算法。在 google 上很容易找到参考资料，例如this。
  2. JVM：您的问题的根源听起来可能没有足够的内存分配给您的 java 虚拟机。我建议增加最大大小，因为您正在处理的信息量下降。

您正在寻找的 JVM 参数应该是：

  • -Xms指定初始 Java 堆大小和

  • -Xmx最大 Java 堆大小。

参考：http ://www.rgagnon.com/javadetails/java-0131.html

于 2012-05-22T15:34:27.813 回答
0

抛出了什么错误？你能成功地将所有数据加载到内存中吗？我建议你试试 Java Comparator 类。也许我会尝试创建一个自定义对象来表示这对：

class Entry{
    long i;
    String s;
}

然后创建一个自定义比较器

class IComp implements Comparator<Entry>{
    public int compare(Entry e1, Entry e2){
      if(e1.i < e2.i) return -1;
      //complete the rest

    }
}

然后将所有对象放入一个数组 Entry[] 条目中，并创建一个比较器 IComp icomp 使用 Arrays.sort(entry, icomp)

由于您将创建 5000 万个对象，因此您需要确保有足够的堆空间。

如果您有大量重复的字符串，并且这些字符串是不可变的；您可以创建一个 Set 来存储字符串，并回收它们以在您的条目中创建更轻的对象

Entry.s = set.get()...

于 2012-05-22T15:19:56.787 回答
0

我很想通过对数据块进行排序并将它们写入不同的文件并对这些文件应用合并排序来解决这个问题。这是 工作演示，可能对您的场景有所帮助。

于 2012-05-23T04:33:53.630 回答
0

我不确定您是否要在完成排序后使用所有值。但是 5000 万这个数字给了我一个暗示，你有可能只是在排序之后取最高的 X 值并用它们做一些事情。

在这种情况下：只需使用最小堆，每次遇到大于堆顶的数字时，从堆中删除最小并添加新数字。这样，您不必将所有数字都保存在内存中，只需将其中的 X 个保存在内存中。

于 2012-05-27T11:06:01.910 回答