Как упоминалось в Milkmaid, это не то, как вы должны выполнять бенчмаркинг, но я считаю, что результаты, которые вы получаете, по-прежнему актуальны.
Давайте посмотрим «под капотом» и увидеть обе реализации:
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 (w != size) {...}, он просто присваивает null s остальной части списка, чтобы объекты, имеющие право на участие, могли быть собраны 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;
}
W акие вызовы:
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;
}
Резюмируя
Даже если теоретически remove операция в LinkedList должны быть O(1) в то время как ArrayList реализация должна принять O(n), когда речь идет о партии -removes реализация ArrayList более кратка, делая все за один проход, перемещая объекты, чтобы переопределить те, которые мы удаляем (вид дефрагментации), в то время как реализация LinkedList является rec ursively вызывая 5 различных методов (каждый из которых выполняет свои собственные проверки безопасности ...) для каждого элемента, который он удаляет, и это заканчивается большими накладными расходами, которые вы испытали.
Не могли бы вы предоставить нам больше данных? В частности, я хотел бы увидеть две линии тренда для 'ArrayList' и' LinkedList' –
Почему вы ожидаете, что это будет быстрее? –
Я не думаю, что 'removeAll()' является особенно хорошим эталоном, потому что вы просто освобождаете всю структуру данных. Лучшим эталоном было бы удаление случайного элемента. –