How can I Subtract these lists faster?

Question

I want to subtract two ArrayLists so I can have the child that are not in the other list.

I do it this way:

removeIDs=(ArrayList<Integer>) storedIDs.clone();
removeIDs.removeAll(downloadedIDs);

downloadIDs=(ArrayList<Integer>) downloadedIDs.clone();
downloadIDs.removeAll(storedIDs);

The Problem is that both lists contain 5000childs and it takes almost 4 seconds on my androidphone.

Is there a fast way to do this? Is using sets faster?(i dont have duplicate values in the lists)

I develop an android app

Answer 1

Use HashSet instead of ArrayList unless you need to keep the order.

Removing an element requires a scan of the full List for list implementations, a HashSet by comparison is just the calculation of a hash code and then identification of a target bucket.

Answer 2

Sets should be must faster. Right now, it's basically doing an n^2 loop. It loops over every element in removeIDs and checks to see if that id is in downloadedIDs, which requires searching the whole list. If downloadedIDs were stored in something faster for searching, like a HashSet, this would be much faster and become an O(n) instead of O(n^2). There might also be something faster in the Collections API, but I don't know it.

If you need to preserver ordering, you can use a LinkedHashSet instead of a normal HashSet but it will add some memory overheard and a bit of a performance hit for inserting/removing elements.