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

Question

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

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

1. Создайте новый ArrayList и добавьте элементы, которые не соответствуют условию. После итерации меняйте старый массив на новый без элементов.

2. Создайте новый ArrayList и добавьте элементы, соответствующие условию. После итерации используйте метод removeAll(), передавая ArrayList с удаляемыми объектами.

Есть ли более эффективный способ удаления объектов из ArrayList?

Answer 1

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

Answer 2

Другой способ: у Iterator есть дополнительный метод remove (), который реализован для ArrayList. Вы можете использовать его во время итерации.

Я не знаю, какой вариант наиболее эффективен, вы должны его измерить.

starblue прокомментировал, что сложность не очень хорошая, и это правда (и для removeAll () тоже), потому что ArrayList должен копировать все элементы, если в середине элемент добавлен или удален. В этом случае LinkedList должен работать лучше. Но, поскольку мы все не знаем ваших реальных сценариев использования, лучше всего измерить все варианты, чтобы выбрать лучшее решение.

Answer 3

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

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

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

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

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

Answer 4

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

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

Метод итератора:

List data = ...;

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

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

Answer 5

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

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

Answer 6

int sizepuede= listaoptionVO.size();
for (int i = 0; i < sizepuede; i++) {
    if(listaoptionVO.get(i).getDescripcionRuc()==null){
        listaoptionVO.remove(listaoptionVO.get(i));
        i--;
        sizepuede--;
     }
}

редактировать: добавлен отступ

Answer 7

Существует скрытая стоимость удаления элементов из 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, чтобы избежать копирования резервного массива при его расширении.

Answer 8

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

public ArrayList filterThings() {

    ArrayList pileOfThings;
    ArrayList filteredPileOfThings = new ArrayList();

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

Answer 9

Несмотря на то, что это противоречит интуиции, я значительно ускорил эту операцию.

Именно то, что я делал:

ArrayList < HashMap < String , String >> results; // This has been filled with a whole bunch of results

ArrayList > discard = findResultsToDiscard (results);

results.removeall (отбрасывания);

Однако метод remove all занимал более 6 секунд (НЕ включая метод получения результатов сброса), чтобы удалить приблизительно 800 результатов из массива 2000 (ish).

Я попробовал метод итератора, предложенный gustafc и другими в этом посте.

Это немного ускорило операцию (примерно до 4 секунд), однако этого было недостаточно. Поэтому я попробовал что-то рискованное ...

 ArrayList < HashMap < String, String>> results;

  List < Integer > noIndex = getTheDiscardedIndexs(results);

for (int j = noIndex.size()-1; j >= 0; j-- ){
    results.remove(noIndex.get(j).intValue());
}

пока getTheDiscardedIndexs сохраняют массив индексов, а не массив HashMaps. Это ускоряет процесс удаления объектов (примерно на 0,1 секунды) и повышает эффективность использования памяти, так как нам не нужно создавать большой массив результатов для удаления.

Надеюсь, это кому-нибудь поможет.

Answer 10

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

Iterator itr = list.iterator();
String strElement = "";
while(itr.hasNext()){

  strElement = (String)itr.next();
  if(strElement.equals("2"))
  {
    itr.remove();
  }