从另一个数组列表中删除一个数组列表元素的最佳方法

Question

Java (7,8) 中从另一个 Arraylist 中消除 integer 元素的最佳性能方法是什么。所有元素在第一个和第二个列表中都是唯一的。

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

tempList.removeAll(tempList2);

当我操作超过10000个元素的arraylists时出现问题。例如，当我删除 65000 个元素时，延迟似乎约为 2 秒。但我需要处理包含超过 1000000 个元素的更大列表。

这个问题的策略是什么？

也许新流 API 可以解决问题？

Answer 1

嗯，由于removeAll检查tempList的每个元素是否出现在tempList2中，运行时间与第一个列表的大小成正比乘以通过第二个列表的大小，这意味着 O(N^2) 除非两个列表中的一个非常小并且可以被认为是 "constant size".

另一方面，如果您对列表进行预排序，然后用单次迭代遍历两个列表（类似于合并排序中的合并步骤），排序将需要 O(NlogN) 和迭代 O(N)，总共运行次 O(NlogN)。这里 N 是两个列表中较大者的大小。

如果你可以用排序结构替换列表（可能是 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();
    }
}

Answer 2

我怀疑从 ArrayList 中删除是一种性能命中，因为当删除中间的元素时列表可能会被分割，或者如果列表必须在删除元素后被压缩。这样做可能会更快：

创建 'Set' 个要删除的元素
创建一个你需要的新结果ArrayList，命名为R。你可以在构造时给它足够的大小。
遍历原始列表，您需要从中删除元素，如果在 Set 中找到该元素，则不要将其添加到 R，否则添加它。

这个应该有O(N)；如果创建 Set 并在其中进行查找则假定为常量。

Answer 3

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) 对 List 的调用也可能具有 O(k)，并且此实现也具有二次复杂度。但事实并非如此：您提到列表具体是 ArrayList 个实例。 ArrayList#removeAll 方法被实现为委托给一个名为 batchRemove 的方法，该方法直接对底层数组进行操作，并且不单独删除元素。

所以您所要做的就是确保包含要删除的元素的集合中的查找速度很快 - 最好是 O(1)。这可以通过将这些元素放入 Set 来实现。最后可以写成

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

旁注：

Eran 的回答有两个主要缺点：首先，它需要排序列表，即 O(n*logn) - 根本没有必要。但更重要的是（显然）：排序可能会改变元素的顺序！如果根本不需要这样做怎么办？

远程相关：removeAll 实现中还涉及一些其他细微之处。例如，在某些情况下。虽然当要删除的元素存储在列表中时，这也归结为 O(n*n)，但在这种特殊情况下，确切的行为可能确实令人惊讶。

从另一个数组列表中删除一个数组列表元素的最佳方法

Best way to remove one arraylist elements from another arraylist

java

arraylist

removeall