On Tue, 23 Feb 2010 08:30:18 -0300, you wrote:
Hi folks,
While solving a puzzle, I was posed the problem of finding if there was no duplicates on a list.
Must it be a list data structure(DS) or list ADT? Mergesort can be parallelized.
Best regards,
Rafael
If space is at a premium you might want to look at a Bloom Filter. http://en.wikipedia.org/wiki/Bloom_filter The Bloom filter, conceived by Burton Howard Bloom in 1970,[1] is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives. The book "Real World Haskell" has an implementation. -- Regards, Casey