比较 java 中的 2 个非常大的数组列表

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

可以在采集界面使用方法removeAll:)

rItems.removeAll(cItems);

如果您查看实现的内部，该方法也使用等号进行比较...

这种方法可以让您从每个列表中获取与另一个列表不匹配的项目。

Answer 2

看起来你想看看 2 个具有相同 ID 的对象在另一种比较时是否相同。

这里可能的问题是您相互检查了 100.000 x 100.000 个对象。更糟糕的是，您只需将这些添加到新列表中...

选项1) 您没有说明您是如何创建 ArrayList() 的。如果您从数据库中获取对象，您可能只是查询它。（那些擅长那个，即使你不擅长）

选项2) 将2个ArrayList()加在一起，它们似乎是同一类对象。使对象可排序（可能按 ID），对单个列表进行排序。（产生另一个问题）然后使用循环将现在排序的对象与它们的邻居进行比较。

Answer 3

如果任何 item-list 中的 ID 是唯一的，您可以使用 Map 作为您的 rItems 并以 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 不是唯一的，您仍然可以使用地图，您只需要一个包含该 ID 的所有项目的列表作为一个 Map.Entry 的值，并且您只需要迭代这几个项目而不是迭代整个列表。

关于 OutOfMemory 的编辑

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

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

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

Answer 4

对2个列表进行排序，然后按顺序进行比较。排序成本 O(n log n) 并比较成本 O(n)。

Comparator<CItem> idComparator = new Comparator<CItem>() {
    @Override
    public int compare(CItem i1, CItem i2) {
        // Implementation depends on the type of CItem ID:
        // if ID is an integer or double, maybe you need
        // return i1.getID() - i2.getID();
        return i1.getID().compareTo(i2.getID());
    }
});

Collections.sort(cItems, idComparator);
Collections.sort(rItems, idComparator);

int minLen = Math.min(cItems.size(), rItems.size());
for (int i = 0, j = 0; i < minLen && j < minLen; ) {

    CItem c = cItems.get(i);
    CItem r = rItems.get(j);

    // c.getID().equals(r.getID())
    if (idComparator.compare(c, r) == 0) {
        Mismatch m = compareItems(c, r);
        if (m != null) {
            mismatches.add(m);
        }
        i++;
        j++;

    // item c's ID does not exist in list rItems
    } else if (idComparator.compare(c, r) < 0) {
        i++;

    // item r's ID does not exist in list cItems
    } else {
        j++;
    }
}

Answer 5

我也遇到了同样的问题。所以我尝试使用LinkedList。所以我有 2 个链表，最多可以包含 350 万条字符串记录。然后我是运行

LinkedList diflist= (LinkedList) ListUtils.subtract(sourceList, targetList);

得到不同之处，但我的应用程序在此基础上堆叠。

那么有什么比较好的算法可以比较列表吗？

比较 java 中的 2 个非常大的数组列表

Comparing 2 very large arraylists in java

java

arraylist

out-of-memory