java - 在 Java 中从另一个集合中删除长整型集合的最快方法

Question

我有两个 Long 类型的集合。两者的规模均20-30百万。从第一个中删除第二个中常见的那些内容的最快方法是什么？占用的堆空间越小越好，因为还有其他事情并行进行。

我知道使用 Iterator 进行删除时 LinkedList 比 ArrayList 更好，但我不确定是否需要迭代每个元素。我想轮询是否有更好的方法，两个集合都已排序。

编辑:我之前说过我的 Collection 规模为 2-3 百万，我意识到它是20-30 百万。会有很多重叠。集合的确切类型也有争议。

Answer 1

由于计数在数百万范围内，复杂度为 O(n²) 的解决方案应该被淘汰。这里有两个基本解决方案:

• 对第二个集合进行排序，并使用二分搜索得到 O((N+M)*logM) 的解决方案，或者
• 将第二个集合中的元素放入哈希容器中，以获得 O(N+M) 解决方案

上面，N 是第一个集合中的元素数量，M 是第二个集合中的元素数量。

Set<Long> toRemove = new HashSet<Long>(collection2);
Iterator<Long> iter = collection1.iterator();
while (iter.hasNext()) {
    if (toRemove.contains(iter.next())) {
        iter.remove();
    }
}

请注意，如果collection1是一个ArrayList，这将非常慢。如果您必须将其保留为ArrayList，您可以这样做:

int rd = 0, wr = 0;
// Copy the elements you are keeping into a contiguous range
while (rd != arrayList1.size()) {
    Long last = arrayList1.get(rd++);
    if (!toRemove.contains(iter.next()) {
        arrayList1.put(wr++, last);
    }
}
// Remove "tail" elements
while (rd > wr) {
    arrayList1.remove(--wr);
}