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

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

每天我都会收到另一个文件，需要提取新元素（每天数万个）。

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

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

我使用这段代码：

dataNew.removeAll(dataOld);

尝试在 HashSet 中加载数据 - HashSet 的创建是无止境的。 LinkedHashset 也是如此。

尝试加载到 ArrayList 中并仅对其中之一进行排序

Collections.sort(dataNew);

但并没有加快这个进程

dataNew.removeAll(dataOld);

而且内存消耗相当高 - sort() 仅用 15Gb 的堆完成（13Gb 是不够的）。

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

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

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

UPDATE:这是全国范围内无效护照的清单。它是作为全局列表发布的，所以我需要自己提取delta。

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

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

java -Xms5G -Xmx16G -jar utils.jar

加载到 HashSet 变得很快（第一个文件需要 50 秒），但程序会被系统内存不足杀手杀死，因为它在将第二个文件加载到第二个 HashSet 或 ArrayList 时会消耗大量 RAM

我的代码很简单：

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

在第二个文件上，程序得到

Killed

[1408341.392872]内存不足：杀死进程20538（java）分数489或牺牲孩子 [1408341.392874]杀死进程20531（java）total-vm：20177160kB，anon-rss：16074268kB，file-rss：0kB

UPDATE2:

感谢您的所有想法！

最终解决方案是：使用fastutil库（LongOpenHashSet）将行转换为Long +

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

有趣的观察。虽然使用默认设置启动 java 会导致无休止地加载 1 亿个字符串到 JDK 的本机 HashSet（我在 1 小时后中断），但从 -Xmx16G 开始将过程加速到 1 分钟。但内存消耗非常可笑（大约 20Gb），处理速度相当不错 - 2 分钟。

如果不受 RAM 限制，原生 JDK HashSet 在速度方面还不错。

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

首先，不要做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有很多不必要的对象分配。