Удаление объектов от ArrayList в Java

Я хорошо разбираюсь в рекомендациях Мнемента.
Только одно предостережение:

 ConcurrentModificationException

Помните, что у вас работает не более одного потока. Это исключение может появиться, если выполняется более одного потока, а потоки плохо синхронизированы.

Может быть, Итератор метод remove () ? Классы коллекций JDK по умолчанию должны все итераторы-создатели, поддерживающие этот метод.

Если вы не уверены, что проблема, с которой вы сталкиваетесь, действительно является узким местом, я бы выбрал читаемый

public ArrayList filterThings() {

    ArrayList pileOfThings;
    ArrayList filteredPileOfThings = new ArrayList();

    for (Thing thingy : pileOfThings) {
        if (thingy.property != 1) {
            filteredPileOfThings.add(thingy);
        }            
    }
    return filteredPileOfThings;
}

Удаление элементов из ArrayList требует скрытых затрат. Каждый раз, когда вы удаляете элемент, вам нужно перемещать элементы, чтобы заполнить «дыру». В среднем это займет N / 2 назначений для списка из N элементов.

Таким образом, удаление M элементов из N элементов ArrayList составляет в среднем O (M * N) . Решение O (N) предполагает создание нового списка. Например.

List data = ...;
List newData = new ArrayList(data.size()); 

for (Iterator i = data.iterator(); i.hasNext(); ) {
    Object element = i.next();

    if ((...)) {
        newData.add(element);
    }
}

Если N большое, я предполагаю, что этот подход будет быстрее, чем подход remove для значений M, таких как 3 или 4.

Но важно создать newList достаточно большой, чтобы вместить все элементы в list , чтобы избежать копирования резервного массива при его расширении.

Я полагаю, что наиболее производительный будет использовать метод listIterator и выполнить обратную итерацию:

for (ListIterator<E> iter = list.listIterator(list.size()); iter.hasPrevious();){
    if (weWantToDelete(iter.previous()))  iter.remove();
}

Изменить: Намного позже можно было бы также добавить способ Java 8 удаления элементов из списка (или любой коллекции!) С использованием лямбда-выражения или ссылки на метод. Встроенный фильтр для коллекций, если хотите:

list.removeIf(e -> e.isBad() && e.shouldGoAway());

Это, вероятно, лучший способ очистить коллекцию. Поскольку он использует внутреннюю итерацию, реализация коллекции может использовать ярлыки, чтобы сделать это как можно быстрее (для ArrayList s это может минимизировать количество необходимого копирования).

Во-первых, я бы удостоверился, что это действительно узкое место производительности, иначе я бы выбрал наиболее чистое и выразительное решение.

Если это узкое место производительности, просто попробуйте разные стратегии и посмотрите, какая из них самая быстрая. Я делаю ставку на создание нового ArrayList и размещение в нем желаемых объектов, отказавшись от старого ArrayList.

Вы можете выполнять итерацию в обратном направлении и удалять по мере прохождения через ArrayList. Это имеет то преимущество, что последующие элементы не нужно перемещать, и их легче программировать, чем двигаться вперед.

Очевидно, из двух упомянутых вами методов номер 1 более эффективен, так как ему нужно пройти по списку только один раз, тогда как с методом номер 2 список нужно пройти два раза (первый найти элементы, которые нужно удалить, и их, чтобы удалить их).

На самом деле, удаление списка элементов из другого списка, вероятно, является алгоритмом хуже, чем O (n), поэтому метод 2 еще хуже.

Итератор метод:

List data = ...;

for (Iterator i = data.iterator(); i.hasNext(); ) {
    Object element = i.next();

    if (!(...)) {
        i.remove();
    }
}

Я нашел альтернативное более быстрое решение:

  int j = 0;
  for (Iterator i = list.listIterator(); i.hasNext(); ) {
    j++;

    if (campo.getNome().equals(key)) {
       i.remove();
       i = list.listIterator(j);
    }
  }