I have two large sets of integers $A$ and $B$.  Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long.  What is the best algorithm to compute $A\setminus B$ and $B\setminus A$? In other words, how can I efficiently compute the list of entries of $A$ that are not in $B$ and vice versa?  What would be the best data structure to represent these two sets, to make these operations efficient?The best approach I can come up with is storing these two sets as sorted lists, and compare every element of $A$ against every element of $B$, in a linear fashion.  Can we do better?
Computing set difference between two large sets
algorithms;data structures;sets