2
$\begingroup$

I recently had a lengthy exchange with someone about the most efficient way to remove duplicates from a collection. The debate was mostly centered around the specific behavior of C# collections, such as HashSet(T) and HashTable(T).

I think we agreed on the fundamentals, but where we couldn’t come to an agreement was what the constraints are with very large sets.

He told me to investigate the theoretical (ie absolute) bounds for duplicate detection in a set of objects… But I don’t really know what that means. I don’t think there’s an absolute bounds if you can break up the problem sufficiently.

There may be a point at which you can no longer use a HashSet / HashTable in .NET because I know that if you are using the framework au-naturale you are constrained by the number of unique values an Int32 can express and the amount of memory you have available.

But the issue of storage and memory issue comes much sooner than the number of unique values, which is typically what the theoretical is concerned with... For example if the data type is integers for the initial set you're removing duplicates from, you run out of memory before the numeric range of the integer type becomes a problem:

  • If I am storing integers, I know that there are 2^32 possible integer values.
  • To store an integer, I need 32 bits of space, so the total memory required to store all distinct integers is 2^32*4 bytes, which is 17.18 gigabytes.
  • The amount of memory that can be addressed in a 32 bit architecture is 2^32 bytes or approximately 4.295 gigabytes

Even if I’m not using a hashset, I can see that in order to store that many values, I would need at least four times the amount of memory addressable by the architecture for the initial collection. And that's not even factoring in the duplicates we're seeking to remove.

I would also need memory proportional to the size of the initial set for the hash set implementation and hash set value storage… So the use of a hashset quickly becomes unfeasible when you exceed millions of unique values.

I’ve already asserted to him that if you had a large digit such as a long, and you had billions of values, you would not use a hashset. Hypothetically I might store the data in distributed nodes that are pre-sorted by the unique field, or implement a distributed mapreduce sort implementation, followed by a mapreduce duplicate value removal algorithm.

He didn’t acknowledge the feasibility of the sort/remove duplicates approach though… And was quite insistent that there is an upper bound for duplicate detection.

Could anyone tell me what the ‘absolute’ bounds for duplicate detection for a set of objects is? Or what he was was referring to by it?

Improve this question
$\endgroup$
2
  • $\begingroup$ If you are storing a large portion of the elements from a fixed set, as in your 32 bit integer example, then it's redundant to store the value. You can just use a bit vector to represent whether or not the element in the set is present. $\endgroup$
    – Joe
    Dec 21, 2013 at 17:20
  • $\begingroup$ Good point. A bit vector is a very efficient means of storing digits and removing duplicates. Though we were speaking of objects in a general sense, so the more likely scenarios would involve complex objects. $\endgroup$
    – M. Smith
    Dec 22, 2013 at 5:22

1 Answer 1

Reset to default
1
$\begingroup$

I think you're asking about the "Element Distinctness Problem."

Assuming you're talking about time complexity (number of comparison operations) rather than space complexity, "lower bound" instead of "upper bound," and that you can't hash elements of your multiset (which gives you $O(n)$ expected time), then the best you can do is $\Theta(n \log n)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That seems like it could be the theoretical basis for his statement... At least in a general sense. Thank you! $\endgroup$
    – M. Smith
    Dec 21, 2013 at 7:49
  • 1
    $\begingroup$ But "can't hash" seems like a silly assumption given the context of their discussion. $\endgroup$
    – Joe
    Dec 21, 2013 at 17:17

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.