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

Question

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

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

tempList.removeAll(tempList2);

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

这个问题的策略是什么？

也许新的 Stream API 可以解决这个问题？

Answer 1

tl;dr:

保持简单。使用

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

相反。

---

正如 Eran 在 his answer 中提到的那样: 低性能源于这样一个事实，即通用 removeAll 实现的 pseudocode 是

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 方法被实现为委托(delegate)给一个名为 batchRemove 的方法，该方法直接对底层数组进行操作，并且 不 删除元素个别地。

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

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

---

旁注:

Eran 的回答有两个恕我直言的主要缺点:首先，它需要对列表进行排序，时间复杂度为 O(n*logn) - 而这根本没有必要。但更重要的是(显然):排序可能会改变元素的顺序!如果根本不需要这样做怎么办？

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