3
$\begingroup$

Let U be a pre-determined and fixed universal set (and |U| = n = 2k for some integer k, so the set may be huge).

I create many arbitrary subsets of U in running time (These sets may be or may not be sparse).

I do not need to check whether an element is in a set.

But I need to be able to

  • check whether a set is empty,
  • do the basic set operations difference and intersection, and
  • calculate the cardinality of a set.

What is the most time-efficient data structure for this? It should be also space-efficient, if possible.

I have bit vector in my mind. Elements of U are numbered from 0 to n-1. Each of n bits represents the existence of the corresponding element.

  • For k ≤ 5 or k ≤ 6 (depends on the computer architecture and the programming language) I can implement these sets as [unsigned] integers.
  • But there will be a need for multi-word arithmetics in general case. So I believe, the space complexity of any set is ϴ(n) and time complexities of operations are ϴ(n) using bitwise operations and hamming weight.
$\endgroup$
  • $\begingroup$ ϴ(n) is not correct, O(n) is, though (using the multi-word bitvector), for n =|U|. Efficient BST-based or hash table-based implementations can do much better for both space and time. As far as I can tell, BST-based approaches can be superior if your operations are not destructive/in-place (you want to keep old as well as new sets around). You can have optimal size as well as (maybe, not sure) optimal non-destructive difference and intersection in O(m log(1+n/m)), where m,n = smaller,larger input sets. $\endgroup$ – Omar Jun 23 '17 at 15:58
  • $\begingroup$ @chi, I don't quite see how a BST will be better than a sorted list. Care to write an answer and explain? $\endgroup$ – D.W. Jun 23 '17 at 16:20
  • $\begingroup$ @D.W. Probably it is not. I somehow assumed insertion was also needed, but the OP does not mention that. A sorted list seems much simpler, then. $\endgroup$ – chi Jun 23 '17 at 16:25
  • $\begingroup$ @chi, I think BSTs do have some advantages over using a sorted array/list. See my comment under D.W.'s answer. $\endgroup$ – Omar Jun 23 '17 at 19:20
  • $\begingroup$ @Omar why ϴ(n) is not correct? In the mentioned solution, all sets have n bits, not only the universal set. For example, if U = {0, 1, 2, 3} then the set {0, 2, 3} is implemented as binary digit 1101. Am I doing it wrong? $\endgroup$ – Ersin 101 Jun 23 '17 at 20:56
4
$\begingroup$

Yes, using a bitvector, the running time will be $\Theta(n)$, i.e., $\Theta(2^k)$, for all operations.

If most sets are small in cardinality, a better option may be to use a sorted list of the elements in the set. In this way, you can compute the intersection or difference of two sets of size $m_1,m_2$ in $\Theta(m_1+m_2)$ time (they work similar to the "merge" operation in mergesort). You can compute the cardinality of a set of size $m$ in $\Theta(m)$ time, and test emptiness in $O(1)$ time. If the size of the sets is small compared to $n$, this might be much faster.

You can make the cardinality operation take $O(1)$ time when using a sorted list by augmenting the data structure: when you construct the list, compute its cardinality and store that in a separate slot along with the list. Now cardinality lookup takes $O(1)$ time. It is easy to keep track of the cardinality of the new set when performing an intersection or differencing operator.

If there is some "pattern" to the set of elements in the set, another option might be to use a binary decision diagram (BDD). You think of each element of $U$ as a $k$-bit vector, and think of a set as a set of $k$-bit vectors. Then, you can use a BDD to represent that set. Alternatively, we can associate to any set $S$ of a function $f:\{0,1\}^n \to \{0,1\}$ so that $f(x)=1$ if $x \in S$; then represent $f$ as a BDD (this is equivalent, and just a different way of thinking about the same thing). If there is sufficient "structure" in the elements of the set, this might allow a more concise representation of the sets and more efficient operations. The running time to compute the intersection or difference of two BDDs is related to the sizes of those BDDs. In many contexts BDDs might be ineffective (they add implementation complexity with no improvements in performance), but in some special cases they might be useful.

$\endgroup$
  • $\begingroup$ I believe BSTs allow for an asymptotically better time for the union, difference and intersection operations. The bound mentioned in my earlier comment under the question is at most O(m_1 + m_2) in fact, and often much smaller (logarithmic in the larger input) due to sub-BST sharing via pointers. Yet of course, arrays are easier to implement efficiently, offer high locality and rely on one contiguous allocation.. $\endgroup$ – Omar Jun 23 '17 at 19:12
  • $\begingroup$ @Omar, if you have a better solution, perhaps you might be interested to write your own answer? I'd be interested to see your analysis... especially if you can quantify "often". $\endgroup$ – D.W. Jun 23 '17 at 22:45
  • $\begingroup$ Thanks for your invitation. I will consider doing so when I have some time (unless a "correct" answer is chosen before then). $\endgroup$ – Omar Jun 24 '17 at 21:35
1
$\begingroup$

If you want a class that can be generally used without any special casing, and which is as efficient as possible, you'd use different data structures depending on which kind of set it is.

For the general case, you store a set as a bitmap: Assume we can store k bits in one word efficiently (whatever a "word" is, for example 32, 64, 128, 256 bits). If all set elements are less than n then we need n / k words, rounded up to the nearest integers. If there are no elements ≤ m then we can not store m / k words, rounded down to the nearest integer. Storage is about n - m bits. Emptiness and first or last element are O (1). Element count is O (n - m) but can be cached. Union, intersection etc. are O (n - m) depending on the values of n, m of both operands.

For sets with few elements, we can store an array containing the sorted list of elements instead. Storage is proportional to the number of elements. Set operations are proportional to the number of elements in both sets (the smaller set for intersection). Instead of elements you could store the difference between elements. Combining both kinds of sets is still fast.

$\endgroup$

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.