5 ms·

This article is incomplete. The Haskell Library "discrimination" has a linear time, "productive" (in that it can output partial results before the full input ha

This article is incomplete. The Haskell Library "discrimination" has a linear time, "productive" (in that it can output partial results before the full input has been seen) version of this: http://hackage.haskell.org/package/discrimination-0.3/docs/Data-Discrimination.html#v:nub 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.

viraptor 8y ago
Do you have some good description / paper for that algorithm? The code is not super clear.
- KirinDave 8y ago
  If you check my submission history you'll see me mention it a few times. The library has links[0] to the papers which describe how to use American Flag Sort in functional contexts to get high performance linear time sorts. 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.pdf https://www.cs.ox.ac.uk/projects/utgp/school/henglein2012c.p... [1]: https://www.youtube.com/watch?v=pOKy3RZbSws https://www.youtube.com/watch?v=pOKy3RZbSws
  - viraptor 8y ago
    I feel like there's some reasonably simple idea trying to get out of those pages of literate Haskell ;-)
    - twanvl 8y ago
      This library is essentially a generic version of radix sort. For example to sort an array of strings in O(nk), where k is the maximum length all strings: use bucket sort to split the strings into 256 buckets based on the first character. Take O(n) * recursively sort each bucket based on the remaining k-1 characters. Takes O(n(k-1)). concatenate sorted buckets 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]]
      - viraptor 8y ago
        Perfect. That's what I was after. It makes sense.
      - KirinDave 8y ago
        This is the paper. The library, well the library literally discovers a new category theoretic construct that previously no one believed existed in Haskell.
    - KirinDave 8y ago
      The first big insight Henglein brings in the first paper is structural: you can map searches sensibly over products and sums. This is actually a profound thing, but most folks outside of Haskell circles don't work with ADTs so they don't understand the universal applicability of this insight. It means you can map them over any concrete, acyclic structure. Which means you can sort anything with radix sort.
inoop 8y ago
> A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time. 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.
- frankmcsherry 8y ago
  > Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers). 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.
- KirinDave 8y ago
  Can you name a non-infinite dataset with an unbounded domain? One without a trivial mapping function? Everything we work with is amenable to Radix Sort. This was a big part of Henglein's work.
bpicolo 8y ago
You can get partial results with really any enumerable style api pretty easily, e.g. python def distinct(l): seen = set() for s in l: if s.lower() not in seen: yield s seen.add(s.lower())
- franey 8y ago
  There's also the classic one-liner: unique_array = list(set(non_unique_array))
  - KirinDave 8y ago
    Which is fine. I'm fairly sure that's n log n, although sometimes those end up being n^2 if they're biased towards memory friendliness.
    - nwallin 8y ago
      It's O(n). Python's set has O(1) insertion and lookup. https://wiki.python.org/moin/TimeComplexity#set https://wiki.python.org/moin/TimeComplexity#set
      - KirinDave 8y ago
        The page you link says it's O(n) for lookup.
        nwallin 8y ago
        It says O(1) for lookup. Average case is the one that matters here. Worst case is for people who've intentionally written bad hash functions. (https://xkcd.com/221/ 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_hash_dos.html 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.

viraptor 8y ago

Do you have some good description / paper for that algorithm? The code is not super clear.

KirinDave 8y ago
If you check my submission history you'll see me mention it a few times. The library has links[0] to the papers which describe how to use American Flag Sort in functional contexts to get high performance linear time sorts. 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.pdf https://www.cs.ox.ac.uk/projects/utgp/school/henglein2012c.p... [1]: https://www.youtube.com/watch?v=pOKy3RZbSws https://www.youtube.com/watch?v=pOKy3RZbSws
- viraptor 8y ago
  I feel like there's some reasonably simple idea trying to get out of those pages of literate Haskell ;-)
  - twanvl 8y ago
    This library is essentially a generic version of radix sort. For example to sort an array of strings in O(nk), where k is the maximum length all strings: use bucket sort to split the strings into 256 buckets based on the first character. Take O(n) * recursively sort each bucket based on the remaining k-1 characters. Takes O(n(k-1)). concatenate sorted buckets 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]]
    - viraptor 8y ago
      Perfect. That's what I was after. It makes sense.
    - KirinDave 8y ago
      This is the paper. The library, well the library literally discovers a new category theoretic construct that previously no one believed existed in Haskell.
  - KirinDave 8y ago
    The first big insight Henglein brings in the first paper is structural: you can map searches sensibly over products and sums. This is actually a profound thing, but most folks outside of Haskell circles don't work with ADTs so they don't understand the universal applicability of this insight. It means you can map them over any concrete, acyclic structure. Which means you can sort anything with radix sort.

inoop 8y ago

> A simpler non-productive algorithm uses sorting, but you can do so in linear time and we have known about this for some time. 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.

frankmcsherry 8y ago
> Nitpick, but you can only sort in linear time if your sort key domain is bounded (e.g. 64-bit integers). 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.
KirinDave 8y ago
Can you name a non-infinite dataset with an unbounded domain? One without a trivial mapping function? Everything we work with is amenable to Radix Sort. This was a big part of Henglein's work.

bpicolo 8y ago

You can get partial results with really any enumerable style api pretty easily, e.g. python def distinct(l): seen = set() for s in l: if s.lower() not in seen: yield s seen.add(s.lower())

franey 8y ago
There's also the classic one-liner: unique_array = list(set(non_unique_array))
- KirinDave 8y ago
  Which is fine. I'm fairly sure that's n log n, although sometimes those end up being n^2 if they're biased towards memory friendliness.
  - nwallin 8y ago
    It's O(n). Python's set has O(1) insertion and lookup. https://wiki.python.org/moin/TimeComplexity#set https://wiki.python.org/moin/TimeComplexity#set
    - KirinDave 8y ago
      The page you link says it's O(n) for lookup.
      - nwallin 8y ago
        It says O(1) for lookup. Average case is the one that matters here. Worst case is for people who've intentionally written bad hash functions. (https://xkcd.com/221/ 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_hash_dos.html 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.