Java: эффективная фильтрация ArrayList?

Question

Мне нужно отфильтровать ArrayList и удалить найденные элементы.Будучи относительно новым для Java, мне интересно, какой самый эффективный метод для этого (важно, потому что он работает на мобильных устройствах).В настоящее время я делаю это:

// We display only top-level dealers (parentId=-10)
ArrayList<DealerProductCount> subDealers = new ArrayList<DealerProductCount>();
for (DealerProductCount dealer : wsResponse.Dealers) {
    if (dealer.ParentId != -10) subDealers.add(dealer);
}
wsResponse.Dealers.removeAll(subDealers);

Можно ли это сделать без временных объектов?Может быть, путем прямого манипулирования (удаления) элементов списка, который повторяется?

Answer 1

Эффективное удаление ряда элементов из ArrayList требует некоторой мысли. Наивный подход примерно такой:

Iterator<DealerProductCount> it = wsResponse.Dealers.iterator();
while (it.hasNext()) {
    if (it.next().ParentId != -10) { 
        it.remove(); 
    }
}

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

Ваше первоначальное решение, включающее список элементов, которые нужно удалить, по сути, делает то же самое. К сожалению, свойства ArrayList не позволяют removeAll работать лучше, чем указано выше.

Если вы собираетесь удалить несколько элементов, более эффективным будет следующее:

ArrayList<DealerProductCount> retain =
        new ArrayList<DealerProductCount>(wsResponse.Dealers.size());
for (DealerProductCount dealer : wsResponse.Dealers) {
    if (dealer.ParentId == -10) {
        retain.add(dealer);
    }
}
// either assign 'retain' to 'wsResponse.Dealers' or ...
wsResponse.Dealers.clear();
wsResponse.Dealers.addAll(retain);

Мы копируем (почти) весь список дважды, поэтому это должно привести к безубыточности (в среднем), если вы удалите всего 4 элемента.

---

Интересно отметить, что функциональные языки программирования / библиотеки, как правило, поддерживают метод фильтра, и это может выполнить эту задачу за один проход по списку; то есть намного эффективнее. Я думаю, что мы можем ожидать значительных улучшений, если / когда Java поддерживает лямбды, и API-интерфейсы сбора расширены для их использования.

ОБНОВЛЕНИЕ и с лямбдами и потоками Java 8 мы получаем их ... для этого варианта использования.

Answer 2

Если вы используете итератор, вы можете безопасно удалять элементы во время итерации.

Answer 3

Один способ будет использовать итератор вместо каждого для:

Iterator<DealerProductCount> iter = wsResponse.Dealers.iterator()
while(iter.hasNext()) {
    if (iter.next().ParentId != -10) iter.remove();
}