ArrayList 删除与 removeAll

Question

如果我想从数组列表中删除一个集合，最好使用什么？我认为 ArrayList 中的 removeAll 方法是为此任务而编写的，但在我编写的测试中，仅遍历对象并将它们单独删除要快几秒钟。

你用什么来实现这个目的？

编辑：

我在grepcode上找到的removeAll代码调用了batchRemove(c, false):

private boolean More ...batchRemove(Collection c, boolean complement) {

700         final Object[] elementData = this.elementData;
701         int r = 0, w = 0;
702         boolean modified = false;
703         try {
704             for (; r < size; r++)
705                 if (c.contains(elementData[r]) == complement)
706                     elementData[w++] = elementData[r];
707         } finally {
708             // Preserve behavioral compatibility with AbstractCollection,
709             // even if c.contains() throws.
710             if (r != size) {
711                 System.arraycopy(elementData, r,
712                                  elementData, w,
713                                  size - r);
714                 w += size - r;
715             }
716             if (w != size) {
717                 // clear to let GC do its work
718                 for (int i = w; i < size; i++)
719                     elementData[i] = null;
720                 modCount += size - w;
721                 size = w;
722                 modified = true;
723             }
724         }
725         return modified;
726     }

其实我看不懂..

我的测试代码是这样的：

public class RemoveVsRemovall {

    public static void main(String[] args){
        ArrayList<String> source = new ArrayList<>();
        ArrayList<String> toRemove = new ArrayList<>();
        for(int i = 0; i < 30000; i++){
            String s = String.valueOf(System.nanoTime());
            source.add(s);
            if(i % 2 == 0) toRemove.add(s);
        }
        long startTime = System.nanoTime();
        removeList1(source, toRemove);
        long endTime = System.nanoTime();
        System.out.println("diff: " + (endTime - startTime) * 1e-9);
    }

    static void removeList1(ArrayList<String> source, ArrayList<String> toRemove){
        source.removeAll(toRemove);
    }

    static void removeList2(ArrayList<String> source, ArrayList<String> toRemove){
        for(String s : toRemove){
            source.remove(s);
        }
    }
}

用不同的列表大小调用它几次，并在两种方法之间切换。

Answer 1

很难对这个问题给出一个笼统的答案有几个原因。

首先，您必须了解这些性能特征是依赖于实现的。实施很可能因 JDK.

的平台和版本而异

话虽如此，主要有 2 种实施策略 removeAll:

对于您 ArrayList 的每个元素，检查它是否在另一个 Collection 中；如果是，请将其删除。
对于Collection的每个元素，检查它是否在ArrayList中；如果是，请将其删除。

如果 Collection 在恒定时间内执行包含，则策略 1（渐近地）获胜。另一方面，如果contains是扫描全连接，Collection迭代很慢，策略2一般有优势，因为它只在Collection上迭代一次；但即使在那种情况下，如果 Collection 非常大并且 ArrayList 的大部分元素都在 Collection 的第一个元素中，策略 1 再次获胜......没有结束吧。

您最好相信 removeAll() 的实施；如果失败，请尝试更改数据结构；如果同样失败，请根据经验基准实施您自己的方法。

Answer 2

要考虑的另一件事：

Java 的代码已经经过了多年的考验，并且是为了适应许多不同的特殊情况而编写的（参见评论 Preserve behavioral compatibility with AbstractCollection）。

因此，实际上您可以编写自己的方法实现，这样运行会更快。但另一方面，你确定你可以处理 Java 开发人员自 Java 诞生以来所面临的所有特殊情况吗？

还要考虑到某些 Java 函数可能会使用某些 C 实现来加快速度。这显然不是这里的情况，但它可以。

ArrayList 删除与 removeAll

ArrayList remove vs removeAll

java

performance

arraylist

collections

removeall