How can I Subtract these lists faster?

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