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

Question

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

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

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

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

我使用这个代码：

dataNew.removeAll(dataOld);

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

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

Collections.sort(dataNew);

但它并没有加快

的进程

dataNew.removeAll(dataOld);

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

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

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

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

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

数据未排序，每一行都是唯一的。所以我必须将 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);

程序获取第二个文件

杀了

[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 的本地 HashSet 是无休止的（我在 1 小时后中断），从 -Xmx16G 开始将进程加速到 1 分钟。但是内存消耗是荒谬的（大约 20Gb），处理速度相当不错 - 2 分钟。

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

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

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

Answer 2

我做了一个非常简单的拼写检查器，只是检查一个词是否在字典中对于整个文档来说太慢了。我创建了一个地图结构，效果很好。

Map<String, List<String>> dictionary;

对于密钥，我使用单词的前 2 个字母。该列表包含以键开头的所有单词。为了加快速度，您可以对列表进行排序，然后使用二进制搜索来检查是否存在。我不确定密钥的最佳长度，如果您的密钥太长，您可能会嵌套地图。最后变成一棵树。实际上，trie 结构可能是最好的。

Answer 3

在 readAllLines() 时出现多次调整 ArrayList 大小的主要问题。更好的选择是 LinkedList 插入数据

try (BufferedReader reader = Files.newBufferedReader(path, StandardCharsets.UTF_8)) {
        List<String> result = new LinkedList<>();
        for (;;) {
            String line = reader.readLine();
            if (line == null)
                break;
            result.add(line);
        }
        return result;
    }

Answer 4

请将字符串分成两部分，重复任何部分（str1 或 str2）most 在其上使用 intern() 以便在堆中再次保存重复 os 相同的字符串。在这里，我在两个部分都使用了 intern() 只是为了展示示例，但不要使用它，除非它们重复 most.

Set<MyObj> lineData = new HashSet<MyObj>();
String line = null;
BufferedReader bufferedReader = new BufferedReader(new FileReader(file.getAbsoluteFile()));
while((line = bufferedReader.readLine()) != null){
    String[] data = line.split(",");
    MyObj myObj = new MyObj();
    myObj.setStr1(data[0].intern());
    myObj.setStr1(data[1].intern());
    lineData.add(myObj);
}

public class MyObj {

    private String str1;
    private String str2;

    public String getStr1() {
        return str1;
    }

    public void setStr1(String str1) {
        this.str1 = str1;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((str1 == null) ? 0 : str1.hashCode());
        result = prime * result + ((str2 == null) ? 0 : str2.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Test1 other = (Test1) obj;
        if (str1 == null) {
            if (other.str1 != null)
                return false;
        } else if (!str1.equals(other.str1))
            return false;
        if (str2 == null) {
            if (other.str2 != null)
                return false;
        } else if (!str2.equals(other.str2))
            return false;
        return true;
    }

    public String getStr2() {
        return str2;
    }

    public void setStr2(String str2) {
        this.str2 = str2;
    }

}

Answer 5

使用数据库;为了简单起见，使用 Java 嵌入式数据库（Derby、HSQL、H2 等）。有了这么多信息，您就可以真正受益于标准数据库缓存、高效存储和查询。您的伪代码将是：

if first use,
   define new one-column table, setting column as primary-key
   iterate through input records, for each:
       insert record into table
otherwise
   open database with previous records
   iterate through input records, for each:
       lookup record in DB, update/report as required

或者，如果您使用现有的 "table-diff" 库，例如 DiffKit - 来自他们的教程：

java -jar ../diffkit-app.jar -demoDB
Then configure a connection to this demo database within your favorite JDBC enabled database browser [...] Your DB browser will show you the tables TEST10_LHS_TABLE and TEST10_RHS_TABLE (amongst others) populated with the data values from the corresponding CSV files.

也就是说：DiffKit 基本上按照我上面的建议进行，将文件加载到数据库表中（它们使用嵌入式 H2），然后通过数据库查询比较这些表。

他们接受 CSV 文件格式的输入；但是从您的文本输入到他们的 CSV 的转换可以在不到 10 行代码的情况下以流方式完成。然后你只需要调用他们的 jar 来做差异，你会在他们的嵌入式数据库中得到作为表格的结果。

Answer 6

对于这种情况，您可以使用 trie 数据结构：http://www.toptal.com/java/the-trie-a-neglected-data-structure 算法如下：

逐行读取旧文件并将每一行存储在 trie 中。
逐行读取新文件并测试每一行是否正确在 trie 中：如果不是，则为新添加的行。

进一步的内存优化可以利用只有 10 个数字，因此 4 位足以存储一个数字（而不是 Java 中每个字符 2 个字节）。您可能需要从以下链接之一调整 trie 数据结构：

Trie data structures - Java
http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Answer 7

包含 11 个字符（实际上最多 12 个）的 String 对象的大小为 64 字节（在 64 位 Java 上压缩 oops）。唯一可以容纳如此多元素且大小合理的结构是数组：

100,000,000 * (64b per String object + 4b per reference) = 6,800,000,000b ~ 6.3Gb

因此您可以立即忘记 Maps、Sets 等，因为它们会引入太多内存开销。但数组实际上就是您所需要的。我的方法是：

将"old"数据加载到一个数组中，对其进行排序（这应该足够快）
创建一个与加载数组大小相同的原始布尔值备份数组（您也可以在此处使用 BitSet）
从新数据文件中逐行读取。使用二进制搜索检查旧数据数组中是否存在密码数据。如果该项目存在，则将其在布尔值 array/bitset 中的索引标记为 true（您从二进制搜索中取回索引）。如果该项目不存在，只需将其保存在某个地方（数组列表可以服务）。
处理完所有行后，从旧数组中删除布尔值 array/bitset 中具有 false 的所有项目（当然是按索引检查）。最后将您保存在某处的所有新数据添加到数组中。
可选择再次对数组进行排序并保存到磁盘，因此下次加载它时可以跳过初始排序。

我觉得这应该足够快了。初始排序是 O(n log(n))，而二分查找是 O(log(n)) 因此你最终应该得到（不包括最终删除 + 添加最多 2n）：

n log(n) (sort) + n log(n) (binary check for n elements) = 2 n log(n)

如果您能更多地解释您所拥有的字符串的结构（无论是否存在某种模式），那么还有其他可能的优化。

Answer 8

感谢您的所有想法！

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

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

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

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

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

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

Improving speed and memory consumption when handling ArrayList with 100 million elements

java

performance

arraylist

hashset