4
$\begingroup$

let $A = [ a_1 \dots a_n ]$ be a sorted list of integers of length $n$. By a simple algorithm that works in-place and in linear time we can remove all duplicates and output a sorted list of unique integers that are precisely the integers which appear .

More generally, it suffices to have a list with the promise that all identical integers are merely grouped to apply the same idea.

Now let $A$ be a list of integers, neither sorted nor even grouped as above. Let us call the problem of outputting a not-necessesarily sorted list of integers that are precisely the integers appearing $A$ by the term "uniquing problem".

An algorithm to solve the "uniqueing problem" might sort the list and remove multiple entries in the obvious way, thus requireing a running time of O( n log(n) ). Can we do better? I don't think so, although there might be a speed up because we actually do not require any sorting on the output list, so this algorithm performs actually too much.

Best, Martin

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I assume you either mean non-amortized linear time or in constant space, or else a simple algorithm that records what it has seen in a hash table would solve this problem in linear time. $\endgroup$
    – Christopher Monsanto
    May 27, 2011 at 16:08
  • $\begingroup$ i am puzzled why an answer that gives a lower bound in a weak computational model was accepted given that there exists an algorithm that beats the lower bound in a general model. $n$ integers can be sorted in-place (which solves the "uniqueing problem") in $o(n \log n)$ time even when the integers are not polynomially bounded: check the link I gave $\endgroup$
    – Sasho Nikolov
    May 28, 2011 at 7:23
  • $\begingroup$ Perhaps Martin actually wanted to know if one could identify unique elements of arbitrary type, but mentioned integers for the sake of being concrete? $\endgroup$
    – Christopher Monsanto
    May 29, 2011 at 1:24

3 Answers 3

Reset to default
2
$\begingroup$

Not possible in a comparison based setting. You can easily reduce the problem of finding repeated elements to uniqueing. Since the former has a lower bound of $n \log n$ by Misra & Gries '82, it ain't gonna happen. There may be solutions that exploit the fact that you are using integers, but my intuition says this isn't true.

Edit: sorry, I meant that I didn't think there was linear time algorithm for uniqueing integers (in the general case). There is clearly a $o(n \log n)$ algorithm for uniqueing integers by Han's integer sorting routine. I could have sworn linear time was mentioned in the question, but I guess it wasn't.

Improve this answer
$\endgroup$
14
  • $\begingroup$ Actually, the following papers improved Misra and Gries to $O(n)$: Demaine ED, L ́opez-Ortiz A, Munro JI. Frequency estimation of internet packet streams with limited space. ESA, 2002; 348–360 and Karp RM, Shenker S, Papadimitriou CH. A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst. 2003; 28(1):51–55, doi:doi.acm.org/10.1145/762471.762473. They use better data structures to achieve this upper bound. $\endgroup$
    – Massimo Cafaro
    May 29, 2011 at 8:49
  • 1
    $\begingroup$ You can't "improve" a lower bound from $n \log n$ to $n$. They are either operating under different assumptions or the first paper was erroneous. Considering that the first paper is highly cited, I doubt the latter. $\endgroup$
    – Christopher Monsanto
    May 29, 2011 at 16:32
  • $\begingroup$ (Just read the last paper) their results are amortized, not worst case. $\endgroup$
    – Christopher Monsanto
    May 29, 2011 at 16:39
  • $\begingroup$ The paper from Demaine provides a worst case result, the one from Karp uses hashing and therefore provides an average case result (even though it can easily be improved to worst case using Cuckoo hashing instead of traditional hashing). The paper from Misra and Gries achieves $O(n \log n)$ using an AVL tree. Demaine uses a much smarter data structure to achieve $O(n)$: as discussed by Demain itself (see erikdemaine.org/papers/NetworkStats_ESA2002), his deterministic algorithm is identical to the one of Misra and Gries, except for the data structure used. $\endgroup$
    – Massimo Cafaro
    May 29, 2011 at 17:06
  • $\begingroup$ Again, you can't have an $O(n)$ algorithm for a $\Omega(n \log n)$ problem. I skimmed one of your papers to find the difference in assumptions, I invite you to find the difference in the other paper. $\endgroup$
    – Christopher Monsanto
    May 29, 2011 at 17:23
7
$\begingroup$

In practice you can solve this problem easily in linear expected time with a hash table: just hash everything and eliminate the duplicates when they collide with each other. See, e.g. this Python recipe which primarily uses hashing but falls back on other strategies for objects that can't be hashed.

Whether you accept this as an acceptable theoretical answer depends somewhat on your model of computation.

Improve this answer
$\endgroup$
4
  • $\begingroup$ See: my first comment on the problem? ;) $\endgroup$
    – Christopher Monsanto
    May 29, 2011 at 2:22
  • $\begingroup$ Well, yes, but it deserves to be an answer not just a comment. I've just set it to be CW, which if I understand correctly means that I don't get undeserved credit when people vote for it. $\endgroup$
    – David Eppstein
    May 29, 2011 at 6:07
  • $\begingroup$ The O(n) upper bound doesn't contradict the Ω(n log n) lower bound; it just requires a different model of computation. Misra and Gries's Ω(n log n) lower bound holds in the comparison tree model, and more generally in the algebraic decision tree and algebraic computation tree models [Steele and Yao, Ben-Or]. These models all define an algorithm as a family of binary or ternary decision trees. Hashing and radix sort violate this assumption; the code A[i]=hash(x) is making a multi-way decision based on the value of hash(x). $\endgroup$
    – Jeffε
    May 29, 2011 at 19:44
  • $\begingroup$ @JeffE, is anyone arguing the opposite? $\endgroup$
    – Christopher Monsanto
    May 29, 2011 at 20:47
3
$\begingroup$

On the other hand there exists a relatively simple linear-time algorithm for well-bounded integers. The algorithm that does do more than compare elements: it uses bit manipulations and radix sort.

If $a_i$ are polynomially bounded, then there exists an in-place version of radix sort that works in $O(n)$ time: FMP. They have various improvements (stability, etc.), but the basic idea is easy to describe. First you sort the first $n/\log n$ numbers using in-place mergesort in time $O(n)$. Then, the sorted integers can be compressed to free-up $\Omega(n)$ bits: the intuitive reason for this is that the binary entropy of sorted sequences is smaller than the entropy of arbitrary sequences. The details of how to do the compression in-place in linear time are not very hard: the technique is an extension of the idea that in a sorted array you can remove the most significant bit of every integer and just remember the index of the smallest integer that has a most significant bit 1. That's not quite enough, but they can remove the most significant $\log (n/3)$ bits, and that gives enough savings.

The next step is the obvious thing: use the usual radix sort with the freed-up space to sort the remainder of the array.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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