6
$\begingroup$

As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great).

Basically, given two sets $S$ and $T$, I want to compute the two set differences $I = T \setminus S$ and $R = S \setminus T$. The goal is that if $S$ represents a "before" set, and $T$ an "after" set, I want to know what elements were inserted into (represented by $I$) and removed from (represented by $R$) the original set $S$ to get to $T$.

A naïve approach would be to compare every element of $S$ with every element of $T$, a worst-case runtime of $O(n * m)$, where $n = |S|$ and $m = |T|$.

An improvement would be to treat $S$ as a list and sort it, then do a binary search in the sorted list for every element in $T$. This would be worst-case (I believe) $O(n \log n + m \log n)$.

However, I think I can get it down to $O(n + m)$, and here's my thought process:

If $S$ is a list of $s_i$ and $T$ a list of $t_i$, we can define a "modification" bit for each element in each list.

If we define $$c_i = \begin{cases} 1, & s_i \in R \\ 0, & \text{else} \end{cases}$$ and $$d_i = \begin{cases} 1, & t_i \in I \\ 0, & \text{else} \end{cases}$$

and we define a "concatenation" sequence of the two: $$x_i = \begin{cases} c_i, & 0 \leq i < n \\ d_{i-n}, & n \leq i < n+m \end{cases}$$

we can define a "modification" number: $$X = \sum_{i=0}^{n+m-1} 2^i x_i$$

We can then compute $R$ and $I$ by breaking down the "modification" number $X$ into $c_i$ and $d_i$, giving $$I = \{ t_i | d_i = 1 \}$$ and $$R = \{ s_i | c_i = 1 \}$$.

Now, since $c_i$ and $d_i$ rely on $R$ and $I$, we can redefine them based on how $R$ and $I$ are defined: $$(s_i \in R) \iff (s_i \in S \land s_i \notin T)$$ $$(t_i \in I) \iff (t_i \in T \land t_i \notin S)$$ So $c_i$ and $d_i$ are now: $$c_i = \begin{cases} 1, & s_i \in S \land s_i \notin T \\ 0, & \text{else} \end{cases}$$ $$d_i = \begin{cases} 1, & t_i \in T \land t_i \notin S \\ 0, & \text{else} \end{cases}$$

Therefore, the modification number $X$ only depends on the original sets/lists $S$ and $T$. Furthermore, since $X$ is composed of $n + m$ bits, any set difference algorithm should be able to compute these bits in $\Omega(n + m)$ time. It could then compute $S$ and $T$ as described above, which would take $O(n)$ and $O(m)$ time, respectively.

My primary concern is the assumption that computing $n + m$ bits should only take $\Omega(n + m)$ time - my reasoning for that is based on the proof of the lower bound of the general sorting algorithm, and how sorting a list is similar to computing $\log_2 n!$ bits, which (from Sterling's Approximation) is $O(n \log n)$.

Again, I'm mostly interested in the validity of my reasoning, and whether or not this means a linear-time algorithm exists for computing set-differences.


An example application that I'm currently interested in (and what originally inspired this) is when a SCSI host rescans its bus for changes in device topology. Typically, it has a list of custom device objects that represent the corresponding device's current state. Upon rescan, the host gets a list of devices currently on the bus, but only by a small identifier (such as it's bus location or LUN).

The problem, then, is how to efficiently map this new device list to the existing device object list, so that unchanged devices are mapped to their corresponding objects, and any device objects whose corresponding devices have been removed can be cleaned up, and any new devices can have objects allocated for them.

If I let $S$ be the list of current devices (by their ID, with some other simple mapping from the ID to the object data), and $T$ be the results of the rescan, then I can efficiently compute $I$ and $R$, and allocate new objects for devices in $I$ and clean up objects for devices in $R$ in linear ($O(n + m)$) time.

$\endgroup$
  • 1
    $\begingroup$ If you can assign indices to elements, such that same element get same index in both $S$ and $T$, and the indices are not too sparse, sorting is $O(n)$. Namely, allocate an array of $n$ (or a little more) elements and set it's $i$th element to $s_i$ produces a sorted array (the difference algorithm doesn't care that ordering was chosen arbitrarily). $\endgroup$ – Karolis Juodelė Jun 10 '14 at 16:14
  • $\begingroup$ For my example case, I could possibly map elements to indices (indexing based on SCSI target ID), but I would like to apply this to a more general case as well (for example, two lists of 64-bit pointers). $\endgroup$ – Drew McGowen Jun 10 '14 at 18:18
3
$\begingroup$

You can compute $S\setminus T$ and $T\setminus S$ from $S$ and $T$ in $O(n+m)$ time using a hash table. Put all of list $S$ into a hashtable, and then iterate through list $T$ and look it up in the hashtable. Then do the same, with $T$ in the hashtable and iterating through $S$.

Fine print for complexity purists: this is expected running time, making suitable assumptions about the hash function. However, the probability that the running time takes longer than $c \cdot (n+m)$ can be made exponentially small in $c$ with a suitable choice of hash function. For practical purposes, you typically don't need to worry about this.

You can also do it in $O(n \lg n + m \lg m)$ time, using a suitable sorting algorithm plus a standard merge algorithm. In some special circumstances, sorting might be even faster (look up counting sort and radix sort).

Which of these is faster in practice will depend upon the platform you run it on. You probably will need to implement and try both, to see which will be faster. You can't trust the asymptotic complexity in this situation, as caching effects and other implementation considerations have the potential to be more important than the asymptotics.

$\endgroup$
  • $\begingroup$ I don't think something that is necessary to make a statement correct fits the metaphor of "fineprint". ;) $\endgroup$ – Raphael Aug 9 '14 at 12:36
2
$\begingroup$

The nature of the answer depends on what you are attempting to optimize (e.g. computation, communication, interactivity) and the computational model (e.g. deterministic, probabilistic,distributed/centralized).

In the case where the two sets are on remote devices, this problem is known as the set reconciliation problem, or more generally the data reconciliation/synchronization problem.

In your application, it appears that you are just interested in computational complexity on a local host. In this case, as Karolis suggested, you can use a linear-time search algorithm (counting sort or radix sort) to get your desired complexity.

$\endgroup$
  • $\begingroup$ What is wrong with just a hashtable? That is a traditional set data structure. $\endgroup$ – Nicholas Mancuso Jun 10 '14 at 21:27
  • $\begingroup$ In practice ... that should work great. In theory, it's worst case is much worse. $\endgroup$ – Ari Trachtenberg Jun 10 '14 at 22:36
  • 1
    $\begingroup$ @NicholasMancuso is absolutely right. Hashtables are worth a try. The theory of hashtables is much misunderstood. First, hashtables behave better in practice than the naive theory would suggest. Big-Oh notation and worst-case complexity are only a tool, intended to help us predict what will work well; when a mathematical fails to predict actual behavior, we should get a better tool. Second, (if you use the right hash function) the theoretical complexity of hashtables is excellent, as long as you look at expected runtime rather than worst-case. $\endgroup$ – D.W. Jun 11 '14 at 16:22
  • 1
    $\begingroup$ This is a bit simplistic, in my opinion. Hash tables are good for certain applications. However, if you have highly correlated data (and most real data is not uniformly random), you have to use an increasingly complex hash function to get good performance, and this has a practical penalty. $\endgroup$ – Ari Trachtenberg Jun 12 '14 at 3:08

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.