5 ms·

You could use a faster sort implementation, such as radix sort which is O(n) and also probably faster in practice when well-implemented. One option is this one

You could use a faster sort implementation, such as radix sort which is O(n) and also probably faster in practice when well-implemented. One option is this one [1] which I actually wrote as part of this exact task: de-duplicating a list of integers, as part of working on [2]. I wrote about the types of speedups you can expect with radix sort here [3] - it depends on the size of the input elements and their distribution (e.g., if many top bits are zero, radix sort will be much faster), but in my test case I see a ~5x speedup for moderate or large input sizes (thousands of elements or more). Of course, the same could be said about hash tables... [1] https://github.com/travisdowns/sort-bench/blob/master/radix7.cpp https://github.com/travisdowns/sort-bench/blob/master/radix7... [2] https://lemire.me/blog/2019/05/07/almost-picking-n-distinct-numbers-at-random/ https://lemire.me/blog/2019/05/07/almost-picking-n-distinct-... [3] https://travisdowns.github.io/blog/2019/05/22/sorting.html https://travisdowns.github.io/blog/2019/05/22/sorting.html

fwip 7y ago
Radix sort is not O(1), did you mean O(n)? And even then it's only true for a constant k (where k is the size of the possible key space).
- kragen 7y ago
  Patricia is O(N) in the size of the input data to be sorted, even without a bound on the key size, as are several more recently discovered suffix array sorting algorithms. Some other radix sorts are not, it's true.
  - rocqua 7y ago
    I did some work on suffix arrays, but didn't come across sorting algorithms. Would you mind linking a few papers?
    - kragen 7y ago
      They're pretty new! I think the first linear-time suffix-sorting algorithm was the "skew algorithm" introduced in "Linear work suffix array construction," J. Kärkkäinen, P. Sanders, and S. Burkhardt. Journal of the ACM, 53(6):918–936, 2006, although I think Kärkkäinen and Sanders published it in 2003 ("Simple linear work suffix array construction", J.C.M. Baeten et al. (Eds.): ICALP 2003, LNCS 2719, pp. 943–955, 2003.) SA-IS, from 2009, has a vulgar explanation (by Satan!) at https://zork.net/~st/jottings/sais.html; https://zork.net/~st/jottings/sais.html; he cites the paper as “Linear Suffix Array Construction by Almost Pure Induced-Sorting” by G. Nong, S. Zhang and W. H. Chan, which seems to be http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%20Construction%20by%20Almost%20Pure%20Induced-Sorting.pdf http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%... (404; from https://code.google.com/archive/p/ge-nong/ https://code.google.com/archive/p/ge-nong/). Nong seems to have gone on to do related external-sorting work until at least 2014, which is of course very important if you want to use suffix arrays to index large corpuses. In 2016 Gonzalo Navarro and a couple of other guys published https://arxiv.org/abs/1607.04346 https://arxiv.org/abs/1607.04346, "Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time", J. Ian Munro, Gonzalo Navarro, Yakov Nekrich (Submitted on 15 Jul 2016 (v1), last revised 14 Nov 2016 (this version, v2)). This constructs not only the suffix array but in fact an entire compressed index similar to the FM-index. This seems to follow up 2014 work by Belazzougui. I think there's a third totally different linear-time suffix-array construction algorithm from the mid-oughties but I can't remember it.
      - deleted 7y ago
        [deleted]
      - deleted 7y ago
        [deleted]
      - deleted 7y ago
        [deleted]
      - deleted 7y ago
        [deleted]
      - deleted 7y ago
        [deleted]
  - AstralStorm 7y ago
    Patricia tries are less local than typical Radix tree implementations. In typical usage of thousands of items, locality wins, low constant factors win. Simple lazily defragmented list can be faster than constant size hash table thanks to constant factors, faster than sorting. Unique objects have a perfect hashing function, but it still has to be fast. Sometimes making it an intrusive structure is a major speedup due to cache locality - let the unique object track where it is. If you cannot know the maximum size (which you will with unique objects), then get more adaptive.
- BeeOnRope 7y ago
  Right, O(n). O(1), hah, I wish! Yes, there is the caveat of constant k, but in practice this is usually implied for integer keys e.g., the int32 integers used in the OP. If the keys become arbitrarily long, hash tables also become O(n log k) since you have to hash and compare log k bits of key state.
shawnz 7y ago
Isn't the OP's "hash-unique" technique basically a radix sort?
- Sean1708 7y ago
  Not really, no. The only parallel is that you're putting things into buckets, but other than that they're very different algorithms.
  - shawnz 7y ago
    Wouldn't the complexity, number of movements, etc also be the same? What's the difference? Why wouldn't a radix sort approach suffer from the same disadvantages as the hash unique approach (e.g. locality of reference)?
    - Sean1708 7y ago
      It's worth giving the Wiki page a quick read, it's very accessible: https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort TL;DR: I guess the hash unique approach is technically a radix sort in base-64 if you hash the inputs before applying the radix sort, but a realistic radix sort will use far fewer buckets giving it much better cache locality and won't unnecessarily hash the buckets. Also it's possible to write a radix sort that doesn't use any extra indirection, but that's a much more complex implementation and I doubt it really has any performance benefits.
- BeeOnRope 7y ago
  A little bit, yeah: it's like a bit like single-pass radix sort, i.e., where the "digit" in the radix sort is selected to be large enough that one digit encompasses the whole key. Another difference is bucket management strategy is different: using a fixed set of buckets with chaining rather than counting ahead of time the buckets you'll need and laying them out linearly. Note that locality of reference is so important that even though "single pass" radix sort does the least work, the ideal radix turns out to be 6-10 bits usually, even if that means e.g., 5-10x more instructions executed for 64-bit keys: because sparsely writing into buckets spread across memory is just really slow.
xvector 7y ago
Can you also hash every key to effectively turn them into a number, and then perform radix sort? If you hash with SHA-256 then any sorting operation seems like it’d just take O(256N)=O(N). What am I missing? Clearly this cannot work because otherwise everyone would do this as we accept O(NlogN) as the norm!
- jstanley 7y ago
  Calculating SHA256 is neither O(1) nor cheap. Your idea is interesting and might be useful in some applications! But calculating a SHA256 takes time linear in the length of the thing you're hashing. Even if you assume fixed-size keys, SHA256 isn't fast. It's not designed to be fast. You'd likely need an extremely high N before O(N) SHA256's is faster than O(N log N) comparisons.
  - jlokier 7y ago
    > But calculating a SHA256 takes time linear in the length of the thing you're hashing. Ahem, so does hashing. And so does sort comparison. The GP's idea is actually quite effective for medium-to-large objects. As a bonus, you can cache and store the SHA256 of each object for future in-set testing and uniqueness-finding without looking at the objects themselves. (You cannot do this with non-cryptographic hashes or sorting by comparisons.) This is basically what Git does.
  - BeeOnRope 7y ago
    Well SHA256 is a red herring here: one could suggest any suitable fast hash, non-crytopgraphic hash instead. Yes, it takes time linear in the length of the thing you are sorting, but comparison sort is generally worse in that respect: comparison also takes up to linear time in the comprands, and you have to compare each element not just once but log n times [1]. So the time to hash all the elements once (if the hash is not already cached in the element) is going to be a small part of the sort time. [1] There are ways around repeatedly re-comparing the entire key, but they work mostly in specialized cases.
- Dylan16807 7y ago
  > What am I missing? Clearly this cannot work because otherwise everyone would do this as we accept O(NlogN) as the norm! Let's assume a perfect hash that never collides or leaves gaps, the best case for this. For a radix sort in some base with K digits, N can only go so high before you have duplicates. Specifically, base^K >= N Take the log of both sides. K >= logN So with arbitrarily large numbers the time taken to sort is actually NlogN. With fixed-size numbers it's "O(K*N)" but K is larger than logN would be.

fwip 7y ago

Radix sort is not O(1), did you mean O(n)? And even then it's only true for a constant k (where k is the size of the possible key space).

kragen 7y ago
Patricia is O(N) in the size of the input data to be sorted, even without a bound on the key size, as are several more recently discovered suffix array sorting algorithms. Some other radix sorts are not, it's true.
- rocqua 7y ago
  I did some work on suffix arrays, but didn't come across sorting algorithms. Would you mind linking a few papers?
  - kragen 7y ago
    They're pretty new! I think the first linear-time suffix-sorting algorithm was the "skew algorithm" introduced in "Linear work suffix array construction," J. Kärkkäinen, P. Sanders, and S. Burkhardt. Journal of the ACM, 53(6):918–936, 2006, although I think Kärkkäinen and Sanders published it in 2003 ("Simple linear work suffix array construction", J.C.M. Baeten et al. (Eds.): ICALP 2003, LNCS 2719, pp. 943–955, 2003.) SA-IS, from 2009, has a vulgar explanation (by Satan!) at https://zork.net/~st/jottings/sais.html; https://zork.net/~st/jottings/sais.html; he cites the paper as “Linear Suffix Array Construction by Almost Pure Induced-Sorting” by G. Nong, S. Zhang and W. H. Chan, which seems to be http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%20Construction%20by%20Almost%20Pure%20Induced-Sorting.pdf http://ge-nong.googlecode.com/files/Linear%20Suffix%20Array%... (404; from https://code.google.com/archive/p/ge-nong/ https://code.google.com/archive/p/ge-nong/). Nong seems to have gone on to do related external-sorting work until at least 2014, which is of course very important if you want to use suffix arrays to index large corpuses. In 2016 Gonzalo Navarro and a couple of other guys published https://arxiv.org/abs/1607.04346 https://arxiv.org/abs/1607.04346, "Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time", J. Ian Munro, Gonzalo Navarro, Yakov Nekrich (Submitted on 15 Jul 2016 (v1), last revised 14 Nov 2016 (this version, v2)). This constructs not only the suffix array but in fact an entire compressed index similar to the FM-index. This seems to follow up 2014 work by Belazzougui. I think there's a third totally different linear-time suffix-array construction algorithm from the mid-oughties but I can't remember it.
    - deleted 7y ago
      [deleted]
    - deleted 7y ago
      [deleted]
    - deleted 7y ago
      [deleted]
    - deleted 7y ago
      [deleted]
    - deleted 7y ago
      [deleted]
- AstralStorm 7y ago
  Patricia tries are less local than typical Radix tree implementations. In typical usage of thousands of items, locality wins, low constant factors win. Simple lazily defragmented list can be faster than constant size hash table thanks to constant factors, faster than sorting. Unique objects have a perfect hashing function, but it still has to be fast. Sometimes making it an intrusive structure is a major speedup due to cache locality - let the unique object track where it is. If you cannot know the maximum size (which you will with unique objects), then get more adaptive.
BeeOnRope 7y ago
Right, O(n). O(1), hah, I wish! Yes, there is the caveat of constant k, but in practice this is usually implied for integer keys e.g., the int32 integers used in the OP. If the keys become arbitrarily long, hash tables also become O(n log k) since you have to hash and compare log k bits of key state.

shawnz 7y ago

Isn't the OP's "hash-unique" technique basically a radix sort?

Sean1708 7y ago
Not really, no. The only parallel is that you're putting things into buckets, but other than that they're very different algorithms.
- shawnz 7y ago
  Wouldn't the complexity, number of movements, etc also be the same? What's the difference? Why wouldn't a radix sort approach suffer from the same disadvantages as the hash unique approach (e.g. locality of reference)?
  - Sean1708 7y ago
    It's worth giving the Wiki page a quick read, it's very accessible: https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort TL;DR: I guess the hash unique approach is technically a radix sort in base-64 if you hash the inputs before applying the radix sort, but a realistic radix sort will use far fewer buckets giving it much better cache locality and won't unnecessarily hash the buckets. Also it's possible to write a radix sort that doesn't use any extra indirection, but that's a much more complex implementation and I doubt it really has any performance benefits.
BeeOnRope 7y ago
A little bit, yeah: it's like a bit like single-pass radix sort, i.e., where the "digit" in the radix sort is selected to be large enough that one digit encompasses the whole key. Another difference is bucket management strategy is different: using a fixed set of buckets with chaining rather than counting ahead of time the buckets you'll need and laying them out linearly. Note that locality of reference is so important that even though "single pass" radix sort does the least work, the ideal radix turns out to be 6-10 bits usually, even if that means e.g., 5-10x more instructions executed for 64-bit keys: because sparsely writing into buckets spread across memory is just really slow.

xvector 7y ago

Can you also hash every key to effectively turn them into a number, and then perform radix sort? If you hash with SHA-256 then any sorting operation seems like it’d just take O(256N)=O(N). What am I missing? Clearly this cannot work because otherwise everyone would do this as we accept O(NlogN) as the norm!

jstanley 7y ago
Calculating SHA256 is neither O(1) nor cheap. Your idea is interesting and might be useful in some applications! But calculating a SHA256 takes time linear in the length of the thing you're hashing. Even if you assume fixed-size keys, SHA256 isn't fast. It's not designed to be fast. You'd likely need an extremely high N before O(N) SHA256's is faster than O(N log N) comparisons.
- jlokier 7y ago
  > But calculating a SHA256 takes time linear in the length of the thing you're hashing. Ahem, so does hashing. And so does sort comparison. The GP's idea is actually quite effective for medium-to-large objects. As a bonus, you can cache and store the SHA256 of each object for future in-set testing and uniqueness-finding without looking at the objects themselves. (You cannot do this with non-cryptographic hashes or sorting by comparisons.) This is basically what Git does.
- BeeOnRope 7y ago
  Well SHA256 is a red herring here: one could suggest any suitable fast hash, non-crytopgraphic hash instead. Yes, it takes time linear in the length of the thing you are sorting, but comparison sort is generally worse in that respect: comparison also takes up to linear time in the comprands, and you have to compare each element not just once but log n times [1]. So the time to hash all the elements once (if the hash is not already cached in the element) is going to be a small part of the sort time. [1] There are ways around repeatedly re-comparing the entire key, but they work mostly in specialized cases.
Dylan16807 7y ago
> What am I missing? Clearly this cannot work because otherwise everyone would do this as we accept O(NlogN) as the norm! Let's assume a perfect hash that never collides or leaves gaps, the best case for this. For a radix sort in some base with K digits, N can only go so high before you have duplicates. Specifically, base^K >= N Take the log of both sides. K >= logN So with arbitrarily large numbers the time taken to sort is actually NlogN. With fixed-size numbers it's "O(K*N)" but K is larger than logN would be.