Fastest way to remove a Collection of Longs from another in Java -

Fastest way to remove a Collection of Longs from another in Java -

i have 2 collections of long type. both of size 20-30 million. quickest way remove one, mutual in second? lesser heap space taken, better, there other things going on in parallel.

i know linkedlist improve arraylist removals using iterator, i'm not sure if need iterate on each element. want poll improve approaches, both collections sorted.

edit: stated collection sizes 2-3 million, realized 20-30 million. there lots of overlaps. exact type of collections open debate well.

with counts in range of millions, solutions o(n2) complexity should out. have 2 basic solutions here:

sort sec collection, , utilize binary search o((n+m)*logm) solution, or put elements sec collection hash container, o(n+m) solution

above, n number of elements in first collection, , m number of elements in sec collection.

set<long> toremove = new hashset<long>(collection2); iterator<long> iter = collection1.iterator(); while (iter.hasnext()) { if (toremove.contains(iter.next())) { iter.remove(); } }

note if collection1 arraylist, slow. if must maintain arraylist, can this:

int rd = 0, wr = 0; // re-create elements keeping contiguous range while (rd != arraylist1.size()) { long lastly = arraylist1.get(rd++); if (!toremove.contains(iter.next()) { arraylist1.put(wr++, last); } } // remove "tail" elements while (rd > wr) { arraylist1.remove(--wr); }

java