java - 在处理具有 1 亿个元素的 ArrayList 时提高速度和内存消耗

Question

我使用其中包含短字符串(10 位数字)的文本文件。文件大小约为1.5Gb，行数达到1亿行。

每天我都会收到另一个文件并需要提取新元素(每天数万个)。

解决我的问题的最佳方法是什么？

我尝试在 ArrayList 中加载数据 - 每个文件大约需要 20 秒，但数组的减法需要永远。

我使用这段代码:

dataNew.removeAll(dataOld);

尝试在 HashSets 中加载数据 - HashSets 的创建是无止境的。与 LinkedHashset 相同。

尝试加载到 ArrayLists 中并仅对其中一个进行排序

Collections.sort(dataNew);

但并没有加快

dataNew.removeAll(dataOld);

内存消耗也相当高 - sort() 仅以 15Gb 的堆完成(13Gb 是不够的)。

我尝试使用旧的好 linux util diff，它在 76 分钟内完成了任务(同时消耗 8Gb 的 RAM)。

因此，我的目标是在 1 小时的处理时间内(当然或更短)并消耗 15Gb(或更好的 8-10Gb)来解决 Java 中的问题。

有什么建议吗？也许我不需要 ArrayList 的字母排序，而是其他东西？

更新:这是一份全国范围内的无效护照 list 。它作为全局列表发布，因此我需要自己提取增量。

数据未排序，每一行都是唯一的。所以我必须将 100M 元素与 100M 元素进行比较。数据线例如为“2404,107263”。无法转换为整数。

有趣的是，当我将最大堆大小增加到 16Gb 时

java -Xms5G -Xmx16G -jar utils.jar

加载到 HashSet 变得很快(第一个文件 50 秒)，但是程序被系统内存不足 killer 杀死，因为它在将第二个文件加载到第二个 HashSet 或 ArrayList 时消耗了大量 RAM

我的代码很简单:

List<String> setL = Files.readAllLines(Paths.get("filename"));
HashSet<String> dataNew = new HashSet<>(setL);

程序获取第二个文件

杀了

[1408341.392872] 内存不足:杀死进程 20538 (java) 得分 489 或牺牲子进程[1408341.392874] 终止进程 20531 (java) total-vm:20177160kB, anon-rss:16074268kB, file-rss:0kB

更新 2:

感谢您的所有想法!

最终解决方案是:将行转换为 Long + 使用 fastutil 库 (LongOpenHashSet)

RAM 消耗量变为 3.6Gb，处理时间仅为 40 秒!

有趣的观察。当使用默认设置启动 java 时，将 1 亿个字符串加载到 JDK 的 native HashSet 是无休止的(我在 1 小时后中断)，从 -Xmx16G 开始将过程加速到 1 分钟。但是内存消耗很荒谬(大约 20Gb)，处理速度相当不错 - 2 分钟。

如果有人不受 RAM 的限制，原生 JDK HashSet 在速度方面并没有那么差。

附注也许这项任务没有明确解释，但我看不到任何不完全加载至少一个文件的机会。因此，我怀疑内存消耗能否进一步降低很多。

Answer 1

首先，不要执行 Files.readAllLines(Paths.get("filename")) 然后将所有内容传递给 Set，它拥有不必要的巨大数据量。尽量始终保持尽可能少的线条。

逐行阅读文件并边读边处理。这会立即大大减少您的内存使用量。

Set<String> oldData = new HashSet<>();
try (BufferedReader reader = Files.newBufferedReader(Paths.get("oldData"))) {
    for (String line = reader.readLine(); line != null; line = reader.readLine()) {
        // process your line, maybe add to the Set for the old data?
        oldData.add(line);
    }
}

Set<String> newData = new HashSet<>();
try (BufferedReader reader = Files.newBufferedReader(Paths.get("newData"))) {
    for (String line = reader.readLine(); line != null; line = reader.readLine()) {
        // Is it enough just to remove from old data so that you'll end up with only the difference between old and new?
        boolean oldRemoved = oldData.remove(line);
        if (!oldRemoved) {
            newData.add(line);
        }
    }
}

您最终会得到两个集合，分别只包含旧数据集中存在的数据或新数据集中存在的数据。

其次，如果可能的话，尝试预先调整容器的大小。当它们达到其容量时，它们的大小(通常)会翻倍，这可能会在处理大型集合时产生大量开销。

此外，如果您的数据是数字，您可以只使用 long 并保存它而不是尝试保存 String 的实例吗？有很多集合库可以让你做到这一点，例如Koloboke、HPPC、HPPC-RT、GS Collections、fastutil、Trove。即使是它们的 Objects 集合也可能为您提供很好的服务，因为标准的 HashSet 有很多不必要的对象分配。