Java: Efficient ArrayList filtering?

Question

I need to filter an ArrayList and remove found elements. Being relatively new to Java, I'm wondering what the most efficent method is to achieve this (matters because it runs on mobile devices). Currently I do this:

// 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);

Can it be done without temporary objects? Maybe by directly manipulating (removing) elements of the list being iterated?

There are other data structures for which item removal is more efficient. Removal from a LinkedList would have O(n) performance. Removal from a HashMap would have constant time performance. — Programmer Bruce
– Programmer Bruce, Commented Jun 8, 2011 at 15:40

Stephen C · Accepted Answer · 2018-04-12 14:54:33Z

19

Efficiently removing a number of elements from an ArrayList requires some thought. The naive approach is something like this:

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

The problem is that each time you remove an element you copy (on average) half of the remaining elements. This is because removing an element from an ArrayList entails copying all elements after element removed one position to the left.

Your original solution involving the list of elements to be removed essentially does the same thing. Unfortunately, the properties of an ArrayList don't allow removeAll to do better than the above.

If you expect to remove a number of elements, the following is more efficient:

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);

We are copying (almost) the entire list twice, so this should break even (on average) if you remove as few as 4 elements.

It is interesting to note that functional programming languages / libraries typical support a filter method, and that can do this task in one pass through the list; i.e. a lot more efficiently. I think we can expect significant improvements if / when Java supports lambdas, and the collection APIs are enhanced to use them.

UPDATE and with Java 8 lambdas and streams, we get them ... for this use-case.

edited Apr 12, 2018 at 14:54

answered Jun 8, 2011 at 15:18

Stephen C

723k95 gold badges849 silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Bachi Over a year ago

Thanks Stephen, for your superb in-depth explanation! So the take-home message is it's generally better to fill a new ArrayList than to remove elements from an existing one. Good to know!

Petar Minchev · Accepted Answer · 2011-06-08 14:51:24Z

7

If you use an iterator you can remove safely elements while iterating.

answered Jun 8, 2011 at 14:51

Petar Minchev

47.5k12 gold badges107 silver badges120 bronze badges

1 Comment

Andreas Dolk Over a year ago

(if the iterator provides an implementation for remove - it may throw an UnsupportedOperationException - so this only works if you know your Iterator very well)

Joshua · Accepted Answer · 2011-06-08 14:56:41Z

4

One way would use the iterator instead of the for each:

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

answered Jun 8, 2011 at 14:56

Joshua

26.8k22 gold badges80 silver badges107 bronze badges

Collectives™ on Stack Overflow

Java: Efficient ArrayList filtering?

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related