http://hackage.haskell.org/package/discrimination-0.3/docs/D...
A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time. Sadly, this information is not well distributed among software engineers in industry.
Most modern, thorough upper-division computer science programs cover how the sorting itself works. I think MIT Open Courseware has one [1].
Before thinking about how to do it productively, imagine that you sorted a list of objects based off their identity, and their identity was trivially comparable. Once sorted, the algorithm would be simple. You'd iterate the list, and every time you see a new object you didn't just see before (you only need a history of one object), you copy it to the output.
To do this in a productive way, you'd actually need to turn each potential bucket you're sorting into a future and then process all of those asynchronously (and ideally in parallel). Top down sorts like American Flag are uniquely suited to this.
[0]: https://www.cs.ox.ac.uk/projects/utgp/school/henglein2012c.p...
This is better than the O(nklog(n)) you get with comparison based sort. It turns out that you can implement radix sort for pretty much any type, where instead of a comparison operator for that type you have a 'split into buckets' operator.
The types might look something like this (in Haskell notation):
class Ord a where
compare :: a -> a -> Ordering
class Bucketable a where
splitIntoBuckets :: (b -> a) -> [b] -> [[b]]It means you can map them over any concrete, acyclic structure. Which means you can sort anything with radix sort.
def distinct(l):
seen = set()
for s in l:
if s.lower() not in seen:
yield s
seen.add(s.lower()) unique_array = list(set(non_unique_array))Worst case is for people who've intentionally written bad hash functions. (https://xkcd.com/221/) Python has put significant effort into good default hashes[1] so you won't be vulnerable to attackers feeding in maliciously colliding hashes, nor will you have performance degradation from biased bits in the hashes if you've written an insufficiently uniform hash function.[2]
[1] https://python-security.readthedocs.io/vuln/cve-2012-1150_ha...
[2] For instance, pointers are usually aligned to cache line boundaries, and are biased toward page boundaries, and in C++, the hash function of an integer/pointer is the identity function. So in C++, a std::unordered_set of pointers will have ridiculously high collision rates. If you have 1024 pointers in a set of size 2048, you will only have only 32 buckets that have values in them, and each of those buckets will have roughly 32 elements, and the zero bucket will even more. Python doesn't let you shoot yourself in the foot, and whitens your hashes before going to the dictionary. C++ "solves" this problem by providing an API which allows you to override the hash function.
No, it's actually not. Everyone else and the article were using the worst case asymptotic, so you'reswitching to this vernacular and suggesting, "Oh we mean the asymptotic of the average."
Redefining the entire conversation to your notational convenience is not a very fair call, and doesn't speak well of your intentions.
And what's more, it's typical to use big-theta notation to discuss average performance anyways. So even if we WERE using that, we'd be using different notation to be more consistent with the literature and less confusing.
> Worst case is for people who've intentionally written bad hash functions.
No. It's for people who do not know what kind of input they're going to receive or what kind of hardware they're going to execute on.
Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers).
> Sadly, this information is not well distributed among software engineers in industry.
Agreed, although you may be interested to know most software 3D rendering engines in the 90's used American flag sorting variants to efficiently implement the painter's algorithm.
It is more subtle than this. Top-down radix sort (which discrimination generalizes) is linear time in the number of input bytes, rather than the number of input records. One special case is when each element has a constant number of bytes, like you mention, but it isn't the only case.
Everything we work with is amenable to Radix Sort. This was a big part of Henglein's work.