RE: Duplicate Detection in an arbitrary set

["Young, Michael" <Michael dot Young at paetec dot com>]

> Tyler Earman wrote:
> > Does anyone know of a semi-efficient way of detecting duplicates in a
> > given set of data (specifically duplicate integers) other than just
> > sorting the data into an array and then stepping through each element in
> > the array?
> >
> > Preferably a solution wouldn't involve something implementation specific
> > (like loading the array into a different data type and measuring the
> > differences between the two, saw someone doing that with Java ArrayLists
> > and HashSets) but rather some sort of mathematically correct method of
> > doing it.
>
> I don't believe there's any way of doing this that is more efficient than
> a hash table.  An informal proof of this is that you have to store each
> element somewhere, and you only check each element once for duplicates,
> given a hash table sufficiently large to make collisions improbable.
> The time to insert one element into a hash table is ~ O(1).  So, the runtime
> for detecting duplicates in a bag of N elements is ~ O(n).
>
> Andrew.

Depending on what language / libraries you are using, you might want to consider using the C++ STL set class.  IIRC, there is a boolean that is returned (along with an iterator pointing to an instance of the value) from the insert() member function and is set according to whether the value specified to insert was preexisting or not.  Despite a lot of "noise" (baseless arguments) to the contrary, STL algorithms tend to be rather efficient at runtime.