13
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If you are willing to store it differently, you might be able to get better results. $\endgroup$ – Realz Slaw Nov 14 '13 at 3:05
  • $\begingroup$ Also, if you are willing to get the results as an implicit data structure; you can just make such a structure that queries the two sets to answer each of its own queries. $\endgroup$ – Realz Slaw Nov 14 '13 at 3:06
  • 1
    $\begingroup$ @user917279 One big point is: you can usually trade-off preprocessing/construction time, query time and memory usage against each other. Do you edit the structe rarely, but query a lot? The other way round? Is memory a concern or not? Such questions can be answered from a practical point of view, and inform the choice of the "right" "theoretical" construct. $\endgroup$ – Raphael Nov 14 '13 at 15:52
  • 1
    $\begingroup$ @Raphael Do you suggest one could do better than the confluently persistent sets (in terms of complexity) by using more memory and/or spending more time on preparation. I'm just curious if you think it is possible. I don't see lookup tables as an option for input sets of this size. $\endgroup$ – smossen Nov 14 '13 at 17:32
  • 1
    $\begingroup$ @user917279 If you consider the example of two huge sets that are identical, then any data structure created using hash-consing would support equality testing in O(1) since equal structures will be merged when created and thus share the same memory location. The confluently persistent sets take advantage of hash-consing also when two structures are almost equal. The complexity is the best I have seen so far for ordered sets. $\endgroup$ – smossen Nov 14 '13 at 20:30
8
$\begingroup$

If you are willing to store the sets in a specialized data-structure, then you can possibly get some interesting complexities.

Let $I=\mathcal O\left(\min\left(|A|,|B|,|A\Delta B|\right)\right)$

Then you can do set operations $A\cup B, A\cap B,A\setminus B$ and $A\Delta B$, each in $\mathcal O\left(I\cdot\log\frac{|A|+|B|}{I}\right)$ expected time. So essentially, you get the minimum size of the two sets, or, the size of the symmetric difference, whichever is less. This is better than linear, if the symmetric difference is small; ie. if they have a large intersection. In fact, for the two set-difference operations you want, this is practically output-sensitive, since together they make up the size of the symmetric difference.

See Confluently Persistent Sets and Maps by Olle Liljenzin (2013) for more information.

$\endgroup$
  • $\begingroup$ The treaps in the paper are ordered search trees. I wouldn't count them as non-sorted data-structures. $\endgroup$ – smossen Nov 14 '13 at 8:18
  • $\begingroup$ @smossen true enough, I edited that out. $\endgroup$ – Realz Slaw Nov 14 '13 at 8:33
6
$\begingroup$

A linear scan is the best that I know how to do, if the sets are represented as sorted linked lists. The running time is $O(|A| + |B|)$.

Note that you don't need to compare every element of $A$ against every element of $B$, pairwise. That would lead to a runtime of $O(|A| \times |B|)$, which is much worse. Instead, to compute the symmetric difference of these two sets, you can use a technique similar to the "merge" operation in mergesort, suitably modified to omit values that are common to both sets.

In more detail, you can build a recursive algorithm like the following to compute $A \setminus B$, assuming $A$ and $B$ are represented as linked lists with their values in sorted order:

difference(A, B):
    if len(B)=0:
        return A # return the leftover list
    if len(A)=0:
        return B # return the leftover list
    if A[0] < B[0]:
        return [A[0]] + difference(A[1:], B)
    elsif A[0] = B[0]:
        return difference(A[1:], B[1:])  # omit the common element
    else:
        return [B[0]] + difference(A, B[1:])

I've represented this in pseudo-Python. If you don't read Python, A[0] is the head of the linked list A, A[1:] is the rest of the list, and + represents concatenation of lists. For efficiency reasons, if you're working in Python, you probably wouldn't want to implement it exactly as above -- for instance, it might be better to use generators, to avoid building up many temporary lists -- but I wanted to show you the ideas in the simplest possible form. The purpose of this pseudo-code is just to illustrate the algorithm, not propose a concrete implementation.

I don't think it's possible to do any better, if your sets are represented as sorted lists and you want the output to be provided as a sorted list. You fundamentally have to look at every element of $A$ and $B$. Informal sketch of justification: If there is any element that you haven't looked at, you can't output it, so the only case where you can omit looking at an element is if you know it is present in both $A$ and $B$, but how could you know that it is present if you haven't looked at its value?

$\endgroup$
  • $\begingroup$ fantastic , do we have other options if the constraint that the sets are to be stored as sorted lists is removed? $\endgroup$ – user917279 Nov 14 '13 at 15:15
2
$\begingroup$

If A and B are of equal size, disjoint and interleaved (e.g. odd numbers in A and even numbers in B), then pairwise comparison of items in linear time is probably optimal.

If A and B contain blocks of items that are in exactly one of A or B, or in both of them, it is possible to compute set difference, union and intersection in sub linear time. As an example, if A and B differ in exactly one item, then the difference can be computed in O(log n).

http://arxiv.org/abs/1301.3388

$\endgroup$
  • 1
    $\begingroup$ He says the sets are ordered, which could mean they are stored as lists, search trees or something else. If data has to be stored as lists, it is quite uninteresting to ask for "the best algorithm to compute A-B" when no algorithm could do better than scanning the lists in linear time (which he already found an algorithm for). $\endgroup$ – smossen Nov 13 '13 at 20:44
  • 1
    $\begingroup$ gosh, you linked the same paper as I (I, same as you, rather)... name your links next time :D $\endgroup$ – Realz Slaw Nov 14 '13 at 5:48
  • $\begingroup$ @smossen fantastic, to whatever knowledge(?) that I have, I represented them as sorted lists, but would humbly welcome other suggestions too. $\endgroup$ – user917279 Nov 14 '13 at 6:34
1
$\begingroup$

one option is to use bitvectors to represent the sets (where the $n$th position represents presence or absence of an item) and set-type operations then reduce to binary operations which can be performed quickly (& on multiple bits in parallel) on digital computers. in this case $A-B$ = $a \wedge \overline b$ where $a,b$ are the bitvectors. the relative efficiency of this technique over other techniques also depends on the sparsity. for more dense sets it may be more efficient than other approaches. also of course the whole operation is embarrassingly parallel so set operations can be done in parallel.

$\endgroup$
  • $\begingroup$ With $10^{10}$ possible entries, bit vectors are not at all practical. $\endgroup$ – Raphael Nov 14 '13 at 13:49
  • $\begingroup$ R., misses the point. a single long can store 32 elements or 1 byte, 8 elements. so 1M entries can be stored in only ~125K RAM! the storage can be significantly more efficient than other representations depending on how the problem is implemented... $\endgroup$ – vzn Nov 15 '13 at 5:18
  • $\begingroup$ So you'd need over 12MB for sets the OP is interested in. That blows all caches (currently) and will be horrible for sparse sets. In particular, creating an empty set dominates all other operations (for sparse sets). Knuth addresses this issue in TAoCP, by the way. $\endgroup$ – Raphael Nov 15 '13 at 8:14
  • $\begingroup$ 12MB? huh? poster said he only has 2 sets. the poster did not specify the sparsity/density of his set. this is pointed out in my answer. are you assuming he has sparse sets? there is no One Correct Answer, the approach is pointed out as an alternative option that may be useful depending on circumstances. it is not uncommonly used in this context... $\endgroup$ – vzn Nov 15 '13 at 16:06
  • $\begingroup$ I suggest you re-read the question: "Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long." There are $10^{10}$ different numbers that can occur, and there are about $10^6$ ones in the list. That means only 0.01% of all entries in your bit vector are 1 -- I'd call that very sparse indeed. (Turns out my 12MB were too low; you need of course $10^{10}\mathrm{b} \approx 1.15\mathrm{GB}$.) $\endgroup$ – Raphael Nov 15 '13 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.