从另一个arraylist中删除一个arraylist元素的最佳方法

Question

Java(7,8)中用于消除彼此integer元素的最佳性能方法是什么Arraylist.所有元素在第一和第二列表中都是唯一的.

目前我知道API方法removeall并以这种方式使用它:

tempList.removeAll(tempList2);

当我操作arraylists有超过10000个元素时出现问题.例如,当我删除65000个元素时,延迟似乎约为2秒.但我需要使用超过1000000个元素的更大的列表进行操作.

这个问题的策略是什么？

也许新的Stream API应该解决它？

Answer 1

TL;博士:

把事情简单化.使用

list.removeAll(new HashSet<T>(listOfElementsToRemove));

代替.

正如Eran在他的回答中已经提到的那样:低性能源于通用实现的伪代码的事实removeAll

public boolean removeAll(Collection<?> c) {
    for (each element e of this) {
        if (c.contains(e)) {
            this.remove(e);
        }
    }
}

因此,contains对要删除的元素列表执行的调用将导致O(n*k)性能(n要删除的元素数量,以及k调用该方法的列表中元素的数量).

天真地,人们可以想象this.remove(e)对a 的调用List可能也有O(k),并且这种实现也会具有二次复杂性.但事实并非如此:您提到列表是具体的ArrayList实例.和ArrayList#removeAll方法被实现为委托给被调用方法batchRemove直接操作底层阵列上,并且不会不单独删除的元素.

因此,您所要做的就是确保包含要删除的元素的集合中的查找很快 - 最好是O(1).这可以通过将这些元素放入一个Set.最后,它可以写成

list.removeAll(new HashSet<T>(listOfElementsToRemove));

附注:

Eran的回答有恕我直言的两个主要缺点:首先,它需要对列表进行排序,即O(n*logn) - 并且根本不需要.但更重要的是(显然):排序可能会改变元素的顺序!如果根本不需要怎么办？

远程相关:removeAll实现中还涉及其他一些细微之处.例如,HashSet removeAll方法在某些情况下出乎意料地慢.虽然当要删除的元素存储在列表中时,这也归结为O(n*n),但在这种特定情况下,确切的行为可能确实令人惊讶.

Answer 2

好吧,既然removeAll检查每个元素tempList是否出现tempList2,运行时间与第一个列表的大小成比例乘以第二个列表的大小,这意味着O(N^2)除非两个列表中的一个非常小并且可以被视为"恒定大小".

另一方面,如果您对列表进行预排序,然后使用单次迭代迭代两个列表(类似于合并排序中的合并步骤),则排序将采用O(NlogN)迭代O(N),从而为您提供总运行时间O(NlogN).这N是两个列表中较大的一个的大小.

如果您可以按排序结构替换列表(可能是a TreeSet,因为您说元素是唯一的),您可以removeAll在线性时间内实现,因为您不必进行任何排序.

我没有测试过,但像这样可以工作(假设两个tempList和tempList2排序):

Iterator<Integer> iter1 = tempList.iterator();
Iterator<Integer> iter2 = tempList2.iterator();
Integer current = null;
Integer current2 = null;
boolean advance = true;
while (iter1.hasNext() && iter2.hasNext()) {
    if (advance) {
        current = iter1.next();
        advance = false;
    }
    if (current2 == null || current > current2) {
        current2 = iter2.next();
    }
    if (current <= current2) {
        advance = true;
        if (current == current2)
            iter1.remove();
    }
}