removeAll ArrayList与LinkedList性能

Question

关于这个项目我有个问题。

public class Main {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<String>();
        for(int i=0; i<100; i++){
            arrayList.add("ValueA");
            arrayList.add("ValueB");
            arrayList.add(null);
            arrayList.add("ValueC");
            arrayList.add(null);
            arrayList.add(null);            
        }
        long startTime = System.nanoTime();
        arrayList.removeAll(Collections.singleton(null));
        long endTime = System.nanoTime();
        System.out.println("ArrayList removal took: " + (endTime - startTime) + "ms");          

        List<String> linkedList = new LinkedList<String>();
        for(int i=0; i<100; i++){
            linkedList.add("ValueA");
            linkedList.add("ValueB");
            linkedList.add(null);
            linkedList.add("ValueC");
            linkedList.add(null);
            linkedList.add(null);
        }

        startTime = System.nanoTime();
        linkedList.removeAll(Collections.singleton(null));
        endTime = System.nanoTime();
        System.out.println("LinkedList removal took: " + (endTime - startTime) + "ms");
    }
}

系统输出是：

ArrayList去除率: 377953ms LinkedList去除率: 619807ms

为什么linkedList在removeAll上比arrayList占用更多的时间？

Answer 1

正如奶妈提到的，这不是你应该做基准测试的方法，但我相信你得到的结果仍然有效。

让我们看看“幕后”，看看这两种实现：

ArrayList.removeAll调用batchRemove

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

如您所见，ArrayList首先“销毁”基础数组，方法是用随后的元素覆盖需要删除的元素(complement作为false传递，因此只复制非null的对象)：

if (c.contains(elementData[r]) == complement)
    elementData[w++] = elementData[r];

下面的if (r != size)处理一个从c.contains抛出的异常，它使用“魔术函数”System.arraycopy将其余的元素从当前索引复制到末尾--这个部分由本机代码运行，应该相当快，这就是我们可以忽略它的原因。

在最后一个if：if (w != size) {...}中，它简单地将null分配给列表的其余部分，以便符合条件的对象能够被GC收集。

操作总数为O(n)，每个操作都使用对数组的直接访问。

现在，让我们看一下LinkedList的实现，它的实现相当短：

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove(); // <-- calls the iterator remove method
            modified = true;
        }
    }
    return modified;
}

如您所见，实现使用迭代器通过调用：it.remove();删除元素

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        AbstractList.this.remove(lastRet); // <-- this is what actually runs
        if (lastRet < cursor)
            cursor--;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException e) {
        throw new ConcurrentModificationException();
    }
}

这反过来又要求：

public E remove(int index) {
    rangeCheck(index);
    checkForComodification();
    E result = l.remove(index+offset); // <-- here
    this.modCount = l.modCount;
    size--;
    return result;
}

这就要求：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index)); // <-- here
}

这就要求：

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

要而论之

尽管理论上LinkedList中的LinkedList操作应该是O(1)，而ArrayList实现应该采用O(n)，但是在处理批处理时，删除ArrayList的实现更简洁，通过移动对象来覆盖我们删除的对象(某种程度的碎片整理)，而LinkedList的实现递归地调用5个不同的方法(每个方法都运行自己的安全检查.)对于它移除的每一个元素，这最终都会产生您所经历的巨大开销。

Answer 2

首先，100个元素不足以测试性能。但从理论上看:数组中的数据(通常)是一个接一个地存储在内存中。在链接列表中，您有值以及指向另一个对象的指针。这意味着，当您删除数组时，您只需遍历连接的内存。如果从链接列表中删除，则必须遍历随机段，内存取决于指针。数组和链接列表之间有更多的区别。就像添加元素、删除元素等等，这就是为什么我们有数组和链接列表。看看这里，Array vs Linked list

Answer 3

这个问题的答案归结为for循环的执行时间的不同。当深入研究这两个对象的removeAll()代码时，您会看到removeAll() of ArrayList调用了batchRemove()，如下所示：

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

另一方面，当您调用removeAll() of LinkedList时，它会调用removeAll() of AbstractCollection，如下所示：

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

显然，在ArrayList的情况下，与LinkedList中基于Iterator的for循环相比，执行一个简单的for循环。

对于像Iterator这样的数据结构，LinkedList更好，但是对于数组来说，传统的for循环仍然要慢一些。

您可以更多地了解这两个循环here在性能上的差异。