ОК, пришло время проверить результаты предложенных подходов. Вот какие подходы я протестировал (имя каждого подхода также является именем класса в моих источниках):
NaiveRemoveManyPerformer - ArrayList с итератором и удалением - первая и наивная реализация, приведенная в моем вопросе. BetterNaiveRemoveManyPerformer - ArrayList с обратной итерацией и удалением от конца к фронту. LinkedRemoveManyPerformer - наивный итератор и удалить, но работает на LinkedList. Недостаток: работает только для LinkedList. CreateNewRemoveManyPerformer - ArrayList создается как копия (добавляются только сохраненные элементы), итератор используется для обхода ввода ArrayList. SmartCreateNewRemoveManyPerformer - лучше CreateNewRemoveManyPerformer - начальный размер (емкость) результата ArrayList устанавливается на окончательный размер списка. Недостаток: вы должны знать окончательный размер списка при запуске. FasterSmartCreateNewRemoveManyPerformer - еще лучше (?) SmartCreateNewRemoveManyPerformer - использовать индекс элемента (items.get(idx)) вместо итератора. MagicRemoveManyPerformer - работает на месте (без копии списка) для ArrayList и сжимает отверстия (удаленные элементы), начиная с элементов в конце списка. Недостаток: этот подход меняет порядок элементов в списке. ForwardInPlaceRemoveManyPerformer - работает на месте для ArrayList - перемещать удерживающие элементы, чтобы заполнить отверстия, в конце возвращается subList (без окончательного удаления или очистки). GuavaArrayListRemoveManyPerformer - Google Guava Iterables.removeIf используется для ArrayList - почти так же, как ForwardInPlaceRemoveManyPerformer, но выполняет окончательное удаление элементов в конце списка.
Полный исходный код приведен в конце этого ответа.
Тесты, выполняемые с различными размерами списка (от 10 000 до 10 000 000 элементов) и разными коэффициентами удаления (определяющими, сколько элементов необходимо удалить из списка).
Поскольку я писал здесь в комментариях для других ответов - я думал, что копирование элементов из ArrayList во второй ArrayList будет быстрее, чем итерация LinkedList и просто удаление элементов. Java-документация Sun гласит, что постоянный коэффициент ArrayList ниже по сравнению с постоянным коэффициентом LinkedList, но, как ни странно, в моей проблеме это не так.
На практике LinkedList с простой итерацией и удалением имеет большую производительность в большинстве случаев (этот подход реализован в LinkedRemoveManyPerformer). Обычно только MagicRemoveManyPerformer производительность сопоставима с LinkedRemoveManyPerformer, другие подходы значительно медленнее. Google Guava GuavaArrayListRemoveManyPerformer работает медленнее, чем ручной код (потому что мой код не удаляет ненужные элементы в конце списка).
Пример результатов для удаления 500 000 элементов из 1 000 000 исходных элементов:
NaiveRemoveManyPerformer: тест не выполнен - я не такой пациент, но он работает хуже, чем BetterNaiveRemoveManyPerformer. BetterNaiveRemoveManyPerformer: 226080 миллисекунд LinkedRemoveManyPerformer: 69 миллисекунд CreateNewRemoveManyPerformer: 246 милли (с) SmartCreateNewRemoveManyPerformer: 112 миллисекунд FasterSmartCreateNewRemoveManyPerformer: 202 миллисекунды MagicRemoveManyPerformer: 74 милли (с) ForwardInPlaceRemoveManyPerformer: 69 милли (с) GuavaArrayListRemoveManyPerformer: 118 миллисекунд
Пример результатов для удаления 1 элемента из 1 000 000 исходных элементов (первый элемент удален):
- BetterNaiveRemoveManyPerformer: 34 милли (с)
- LinkedRemoveManyPerformer: 41 миллисекунда
- CreateNewRemoveManyPerformer: 253 миллисекунды
- SmartCreateNewRemoveManyPerformer: 108 миллисекунд
- БыстрееСмартСоздатьНовое УдалятьМаниПерформер: 71 миллисекунда
- MagicRemoveManyPerformer: 43 миллисекунды
- ForwardInPlaceRemoveManyPerformer: 73 милли (ов)
- GuavaArrayListRemoveManyPerformer: 78 миллисекунд
Пример результатов для удаления 333 336 элементов из 1 000 000 исходных элементов:
- BetterNaiveRemoveManyPerformer: 253206 миллисекунд
- LinkedRemoveManyPerformer: 69 миллисекунд
- CreateNewRemoveManyPerformer: 245 миллисекунд
- SmartCreateNewRemoveManyPerformer: 111 миллисекунд
- Быстрее УмнееСоздатьНовое УдалитеМногоПроизводителя: 203 миллисекунды
- MagicRemoveManyPerformer: 69 миллисекунд
- ForwardInPlaceRemoveManyPerformer: 72 миллисекунды
- GuavaArrayListRemoveManyPerformer: 102 милли (ов)
Пример результатов для удаления 1 000 000 (всех) элементов из 1 000 000 исходных элементов (все элементы удаляются, но с обработкой по одному, если вы заранее знаете, что все элементы должны быть удалены, список следует просто очистить):
- BetterNaiveRemoveManyPerformer: 58 милли (s)
- LinkedRemoveManyPerformer: 88 милли (s)
- CreateNewRemoveManyPerformer: 95 милли (s)
- FasterSmartCreateNewRemoveManyPerformer: 48 миллисекунд
- MagicRemoveManyPerformer: 61 миллисекунда
- ForwardInPlaceRemoveManyPerformer: 49 миллилитров (с) * 11
Мои окончательные выводы: используйте гибридный подход - если имеете дело с LinkedList - лучше всего использовать простую итерацию и удаление, если имеет дело с ArrayList - это зависит от важности порядка элементов - используйтеForwardInPlaceRemoveManyPerformer тогда, если порядок элементов может быть изменен - лучший выбор - MagicRemoveManyPerformer,Если коэффициент удаления известен априори (вы знаете, сколько элементов будет удалено и сохранено), тогда можно будет добавить еще несколько условий, чтобы выбрать подход, который будет работать еще лучше в конкретной ситуации.Но известный коэффициент удаления не является обычным случаем ... Google Guava Iterables.removeIf является таким гибридным решением, но с несколько иным допущением (необходимо изменить исходный список, создать новый нельзя, а порядок элементов всегда имеет значение) - это наиболее распространенные предположениятак что removeIf - лучший выбор в большинстве случаев из реальной жизни.
Обратите внимание, что все хорошие подходы (наивный - это не хорошо!) достаточно хороши - любой из них должен хорошо работать в реальном приложении, нонужно избегать наивного подхода.
Наконец - мой исходный код для тестирования.
package WildWezyrListRemovalTesting;
import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class RemoveManyFromList {
public static abstract class BaseRemoveManyPerformer {
protected String performerName() {
return getClass().getSimpleName();
}
protected void info(String msg) {
System.out.println(performerName() + ": " + msg);
}
protected void populateList(List<Integer> items, int itemCnt) {
for (int i = 0; i < itemCnt; i++) {
items.add(i);
}
}
protected boolean mustRemoveItem(Integer itemVal, int itemIdx, int removeFactor) {
if (removeFactor == 0) {
return false;
}
return itemIdx % removeFactor == 0;
}
protected abstract List<Integer> removeItems(List<Integer> items, int removeFactor);
protected abstract List<Integer> createInitialList();
public void testMe(int itemCnt, int removeFactor) {
List<Integer> items = createInitialList();
populateList(items, itemCnt);
long startMillis = System.currentTimeMillis();
items = removeItems(items, removeFactor);
long endMillis = System.currentTimeMillis();
int chksum = 0;
for (Integer item : items) {
chksum += item;
}
info("removing took " + (endMillis - startMillis)
+ " milli(s), itemCnt=" + itemCnt
+ ", removed items: " + (itemCnt - items.size())
+ ", remaining items: " + items.size()
+ ", checksum: " + chksum);
}
}
private List<BaseRemoveManyPerformer> rmps =
new ArrayList<BaseRemoveManyPerformer>();
public void addPerformer(BaseRemoveManyPerformer rmp) {
rmps.add(rmp);
}
private Runtime runtime = Runtime.getRuntime();
private void runGc() {
for (int i = 0; i < 5; i++) {
runtime.gc();
}
}
public void testAll(int itemCnt, int removeFactor) {
runGc();
for (BaseRemoveManyPerformer rmp : rmps) {
rmp.testMe(itemCnt, removeFactor);
}
runGc();
System.out.println("\n--------------------------\n");
}
public static class NaiveRemoveManyPerformer
extends BaseRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
if (items.size() > 300000 && items instanceof ArrayList) {
info("this removeItems is too slow, returning without processing");
return items;
}
int i = 0;
Iterator<Integer> iter = items.iterator();
while (iter.hasNext()) {
Integer item = iter.next();
if (mustRemoveItem(item, i, removeFactor)) {
iter.remove();
}
i++;
}
return items;
}
@Override
public List<Integer> createInitialList() {
return new ArrayList<Integer>();
}
}
public static class BetterNaiveRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
// if (items.size() > 300000 && items instanceof ArrayList) {
// info("this removeItems is too slow, returning without processing");
// return items;
// }
for (int i = items.size(); --i >= 0;) {
Integer item = items.get(i);
if (mustRemoveItem(item, i, removeFactor)) {
items.remove(i);
}
}
return items;
}
}
public static class LinkedRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> createInitialList() {
return new LinkedList<Integer>();
}
}
public static class CreateNewRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
List<Integer> res = createResultList(items, removeFactor);
int i = 0;
for (Integer item : items) {
if (mustRemoveItem(item, i, removeFactor)) {
// no-op
} else {
res.add(item);
}
i++;
}
return res;
}
protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
return new ArrayList<Integer>();
}
}
public static class SmartCreateNewRemoveManyPerformer
extends CreateNewRemoveManyPerformer {
@Override
protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
int newCapacity = removeFactor == 0 ? items.size()
: (int) (items.size() * (removeFactor - 1L) / removeFactor + 1);
//System.out.println("newCapacity=" + newCapacity);
return new ArrayList<Integer>(newCapacity);
}
}
public static class FasterSmartCreateNewRemoveManyPerformer
extends SmartCreateNewRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
List<Integer> res = createResultList(items, removeFactor);
for (int i = 0; i < items.size(); i++) {
Integer item = items.get(i);
if (mustRemoveItem(item, i, removeFactor)) {
// no-op
} else {
res.add(item);
}
}
return res;
}
}
public static class ForwardInPlaceRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
int j = 0; // destination idx
for (int i = 0; i < items.size(); i++) {
Integer item = items.get(i);
if (mustRemoveItem(item, i, removeFactor)) {
// no-op
} else {
if (j < i) {
items.set(j, item);
}
j++;
}
}
return items.subList(0, j);
}
}
public static class MagicRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
for (int i = 0; i < items.size(); i++) {
if (mustRemoveItem(items.get(i), i, removeFactor)) {
Integer retainedItem = removeSomeFromEnd(items, removeFactor, i);
if (retainedItem == null) {
items.remove(i);
break;
}
items.set(i, retainedItem);
}
}
return items;
}
private Integer removeSomeFromEnd(List<Integer> items, int removeFactor, int lowerBound) {
for (int i = items.size(); --i > lowerBound;) {
Integer item = items.get(i);
items.remove(i);
if (!mustRemoveItem(item, i, removeFactor)) {
return item;
}
}
return null;
}
}
public static class GuavaArrayListRemoveManyPerformer
extends BaseRemoveManyPerformer {
@Override
protected List<Integer> removeItems(List<Integer> items, final int removeFactor) {
Iterables.removeIf(items, new Predicate<Integer>() {
public boolean apply(Integer input) {
return mustRemoveItem(input, input, removeFactor);
}
});
return items;
}
@Override
protected List<Integer> createInitialList() {
return new ArrayList<Integer>();
}
}
public void testForOneItemCnt(int itemCnt) {
testAll(itemCnt, 0);
testAll(itemCnt, itemCnt);
testAll(itemCnt, itemCnt - 1);
testAll(itemCnt, 3);
testAll(itemCnt, 2);
testAll(itemCnt, 1);
}
public static void main(String[] args) {
RemoveManyFromList t = new RemoveManyFromList();
t.addPerformer(new NaiveRemoveManyPerformer());
t.addPerformer(new BetterNaiveRemoveManyPerformer());
t.addPerformer(new LinkedRemoveManyPerformer());
t.addPerformer(new CreateNewRemoveManyPerformer());
t.addPerformer(new SmartCreateNewRemoveManyPerformer());
t.addPerformer(new FasterSmartCreateNewRemoveManyPerformer());
t.addPerformer(new MagicRemoveManyPerformer());
t.addPerformer(new ForwardInPlaceRemoveManyPerformer());
t.addPerformer(new GuavaArrayListRemoveManyPerformer());
t.testForOneItemCnt(1000);
t.testForOneItemCnt(10000);
t.testForOneItemCnt(100000);
t.testForOneItemCnt(200000);
t.testForOneItemCnt(300000);
t.testForOneItemCnt(500000);
t.testForOneItemCnt(1000000);
t.testForOneItemCnt(10000000);
}
}