Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I want to filter efficiently a list of integers for duplicates in a way that only the resulting set needs to be stored.

One way this can be seen:

  • we have a range of integers $S = \{1, \dots{}, N\}$ with $N$ big (say $2^{40}$)
  • we have a function $f : S \to S$ with, supposedly, many collisions (the images are uniformly distributed in $S$)
  • we then need to store $f[S]$, that is $\{f(x) | x \in S\}$

I have a quite accurate (probabilistic) estimation of what $|f[S]|$ is, and can therefore allocate data structures in advance (say $|f[S]| \approx 2^{30}$).

I have had a few ideas, but I am not sure what would be the best approach:

  • a bitset is out of the question because the input set does not fit into memory.
  • a hash table, but (1) it requires some memory overhead, say 150% of $|f[S]|$ and (2) the table has to be explored when built which requires additional time because of the memory overhead.
  • an "on the fly" sort, preferably with $O(N)$ complexity (non-comparison sort). Regarding that, I am not sure what is the major difference between bucket sort and flashsort.
  • a simple array with a binary search tree, but this requires $O(N \log |f[S]|)$ time.
  • maybe using Bloom filters or a similar data structure could be useful in a relaxation (with false positives) of the problem.

Some questions on stackoverflow seem to tackle with this sort of things (http://stackoverflow.com/questions/12240997/sorting-array-in-on-run-time, http://stackoverflow.com/questions/3951547/java-array-finding-duplicates), but none seems to match my requirements.

share|improve this question
2  
Do you need to enumerate f[S] (whatever it is), or to be able to tell quickly whether some x is in it? –  Gilles Sep 3 '12 at 20:13
    
@Gilles: I believe that, since no obvious structure can be found in f[S], the two solutions are equivalent. –  doc Sep 3 '12 at 21:23
    
Your numbers don't add up. The expected image of a random function on a domain of size $N$ is roughly $(1-1/e)N$. Another issue is that going through $2^{56}$ is going to take too long unless you have a supercomputer or a large cluster at your disposal. –  Yuval Filmus Sep 4 '12 at 15:20
1  
The time for the binary search tree would be $O(N \log |f[S]|)$, which may or may not be close to $O(N\log N)$ in practice but still is more accurate. –  jmad Sep 15 '12 at 8:25
1  
With $N \sim 2^{56}$, won't a linear time algorithm be prohibitive too? (From my calculations, even if you consider one element of $S$ in 1 nano-second, it would take you a good 2 years!). –  Aryabhata Sep 26 '12 at 18:55
show 12 more comments

migrated from stackoverflow.com Sep 4 '12 at 12:28

This question came from our site for professional and enthusiast programmers.

1 Answer

Why not bin and chain?

The idea is to store positive integers representable by $n = k+m$ bits in an array $A$ of $2^k$ entries representing ranges of values: entry $A[y]$, $y \ge 0$, represents the range $[2^m y, 2^m(y+1)-1]$. For any $1 \le x \lt 2^n$ we may write $x = 2^m y + z$ where $y$ has $k$ bits and $z$ has $m$ bits. Try to store $z$ (not $x$!) at location $y$:

  • When $A[y]=z$ already, do nothing: $x$ is a duplicate.

  • When $A[y]$ is uninitialized, store $z$ at $A[y]$.

  • Otherwise, store an index into a separate array used to chain the $z$'s (which have collided at $y$) in linked lists. You will have to search linearly through the list headed by $A[y]$ and, depending on what the search uncovers, potentially insert $z$ into the list.

At the end, $f(S)$ is easy to recover by looping through the initialized entries of $A$ and--by merely concatenating two bitstrings--reassembling each $z$ found at location $y$ (either directly or within a chain referenced there) into the original value $x = 2^m y + z$.

When the distribution is close to uniform and $2^k$ exceeds $N$, there will not be much chaining (this can be assessed in the usual ways) and the chains will tend to be short. When the distribution is nonuniform, the algorithm still works, but can reach quadratic timing. If that's a possibility, use something more efficient than chains (and pay a little overhead for storage).

The storage needed is at most $2^n$ bits for $A$ and $2^{2k}$ bits for the chains (assuming $m \le k$). This is exactly the space needed to store $2^k$ values of $n$ bits each. If you're confident in the uniformity, you can underallocate the storage for the chains. If nonuniformity is a possibility, you may want to increase $k$ and fully advocate the chain storage.

An alternative way of thinking about this solution is that it is a hash table with a particularly nice hash function (take the $k$ most significant bits) and, because of that, we only need to store the least significant $m=n-k$ bits in the table.

There are ways to overlay storage for the chains with the storage for $A$ but it doesn't seem worth the bother, because it wouldn't save much (assuming $m$ is much smaller than $k$) space and would make the code harder to develop, debug, and maintain.

share|improve this answer
1  
I think the second-to-last paragraph is the central one here, and should probably be at the top (as idea). I don't know the term "bin and chain" (although it makes sense after reading the post). This idea can be extended to tries. –  Raphael Nov 22 '12 at 10:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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