java - 比较java中的2个非常大的arraylists

Question

当您需要比较 2 个非常大的数组列表时，正确的方法是什么？

这些 arraylist 的大小都是 100,000 项，并且在简单地逐项比较时肯定会崩溃。

for (CItem c : cItems) {
        for (CItem r : rItems) {
            if (c.getID().equals(r.getID())) {
                Mismatch m = compareItems(c, r);
                if (m != null) {
                    mismatches.add(m);
                }
            }
        }
    }

现在我不是 100% 确定垃圾收集在这种情况下是如何工作的，但我们得到的错误是:

java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOfRange(Arrays.java:3664) ~[na:1.8.0_73]
at java.lang.String.<init>(String.java:207) ~[na:1.8.0_73]
at java.lang.StringBuilder.toString(StringBuilder.java:407) ~[na:1.8.0_73]

和

java.lang.OutOfMemoryError: GC overhead limit exceeded
at java.util.Arrays.copyOf(Arrays.java:3181) ~[na:1.8.0_73]
at java.util.ArrayList.grow(ArrayList.java:261) ~[na:1.8.0_73]
at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235) ~[na:1.8.0_73]
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227) ~[na:1.8.0_73]
at java.util.ArrayList.add(ArrayList.java:458) ~[na:1.8.0_73]

目前可能的解决方案是

• 将每个列表分成最多 x 个项目并比较这些多个列表(有点复杂)
• 创建一个新数据库并查询每个项目(这会非常慢并且现在不可行)
• 购买 200 GB 内存

如有任何意见，我们将不胜感激。

Answer 1

如果任何项目列表中的 ID 是唯一的，您可以为您的 rItems 使用 Map 并将 ID 作为键。

Map<Long, CItem> rItemMap = new HashMap<>(rItems.size());
for (CItem r : rItems) {
    rItemMap.put(r.getID(), r);
}

现在您可以直接检查具有相同 ID 的 rItems:

for (CItem c : cItems) {
    CItem r = rItemMap.get(c.getID());
    if (r != null) {
        Mismatch m = compareItems(c, r);
        if (m != null) {
            mismatches.add(m);
        }
    }
}

即使 ID 不是唯一的，您仍然可以使用 Map，您只需要一个包含该 ID 的所有项目的列表作为一个 Map.Entry 的值，并且您只需要迭代那几个项而不是遍历整个列表。

关于 OutOfMemory 的编辑

我刚刚从您的异常中看到，您正在使用 ArrayList。使用 LinkedList 可能会有所帮助，因为 ArrayList 基于一个(固定大小的)数组，当该数组填满时，将分配一个新的 - 更大的 - 数组并复制旧数组中的数据到新阵列，然后释放。

因此，如果您有一个大小为 1000 的数组并且它已满，则可以创建一个新数组，例如分配了大小 2000。在那一刻，需要 3000 个项目的内存(尽管 1000 个很快就会被释放)。

LinkedList 只是为您添加到它的每个项目分配内存(加上指向下一个和上一个元素的内存)。