What is the most efficient algorithm to compute the difference between two set data structures? In particular, the algorithm should efficiently discover elements in the first set that are also in the second set and return the difference-set.
Although many efficient set intersection algorithms have been proposed in the literature, my recommendation is the algorithm proposed in this paper: Bolin Ding, Arnd Christian König: Fast Set Intersection in Memory. PVLDB 4(4): 255-266 (2011), which seems most practical.
Also, note that there is a related question in the stackoverflow.
Call your sets A and B respectively, and assume wlog that Card(A) = n < Card(B) = m. If you are allowed to choose a data structure, you may want to use a hash table H as follows. Store all of the elements of set B in H. Then iterate through the elements in A. For each element e, check if e is in H. If yes, output e in the intersection set, otherwise in the difference set. Since looking up an element in the hash table is O(1) (on average), the algorithm requires O(n) and is linear in the cardinality of A.
If Card(A) = Card(B), a fast intersection algorithm is to use a Bloom filter to store the sets, and then intersection is implemented with bitwise AND operations.