我有两个 Long
类型的集合。两者的规模均20-30百万。从第一个中删除第二个中常见的那些内容的最快方法是什么?占用的堆空间越小越好,因为还有其他事情并行进行。
我知道使用 Iterator 进行删除时 LinkedList
比 ArrayList
更好,但我不确定是否需要迭代每个元素。我想轮询是否有更好的方法,两个集合
都已排序。
编辑:我之前说过我的 Collection 规模为 2-3 百万,我意识到它是20-30 百万。 会有很多重叠。集合的确切类型也有争议。
最佳答案
由于计数在数百万范围内,复杂度为 O(n2) 的解决方案应该被淘汰。这里有两个基本解决方案:
- 对第二个集合进行排序,并使用二分搜索得到 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);
}
关于java - 在 Java 中从另一个集合中删除长整型集合的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26653433/