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?

Answer 1

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.