3 ms·

timsort and pdqsort seem to be significantly slower than radix sort for random inputs, but presumably radix sort could also benefit from a pile of pattern-findi

timsort and pdqsort seem to be significantly slower than radix sort for random inputs, but presumably radix sort could also benefit from a pile of pattern-finding heuristics.

eesmith 4y ago
timsort and pdqsort (two comparison sort methods) and radix sort (a non-comparative sorting algorithm) have different albeit overlapping domains of applicability. Given a large number of 32-bit integers, radix sort is indeed significantly faster. While I would reach for a comparison sort method if I had a large number of arbitrary-length Unicode strings, which I wanted to sort in a case-ignoring order. Also, I found timsort faster than radix sort when there was a small number (as I recall, <100 or so) of elements.
- anonymoushn 4y ago
  > timsort and pdqsort (two comparison sort methods) and radix sort (a non-comparative sorting algorithm) have different albeit overlapping domains of applicability. Most comparators are of the form "compare by this, then if tied, compare by that, then if tied, compare by the other thing" which is pretty well suited to radix sort. You are correct though. > While I would reach for a comparison sort method if I had a large number of arbitrary-length Unicode strings, which I wanted to sort in a case-ignoring order. It seems like the radix sort is likely to be a lot faster for this too, mainly due to cache effects. If you have a dataset in mind I'll be happy to give it a shot. > Also, I found timsort faster than radix sort when there was a small number (as I recall, <100 or so) of elements. For sure. 100 isn't so far from the threshold where a radix sort should fall back to something else anyway.
  - eesmith 4y ago
    > which is pretty well suited to radix sort Yes, the general approach is to convert the input data into a fixed-length bit-string with the same sort order as the input. Your example assumes that construction overhead is short. If tie-breaking is rare, and breaking the tie requires an expensive operation, then the trade-off point for radix might be much higher than 100 elements. The fixed-length requirement works well for small items with relatively equal-length fields. Ragged items, like Wikipedia titles, causes a problem. There is one title which is 253 bytes long. Now, Wikipedia titles are limited to 255 bytes, so radix is certainly directly applicable, but 1) it changes the trade-off point, and 2) reduces cache effects. Finally, it requires a sort-order-preserving transformation. I mentioned case-insensitive collation of Unicode strings as a well-known difficult problem. I do not believe there is mapping to an order-preserving representation which can be done bitwise. At the very least, it will be difficult to support all of the collation styles that currently exist (eg, French collation is different than Dutch).
    - anonymoushn 4y ago
      This is basically all incorrect. Maybe you are writing about LSB radix sort? I am writing about MSB radix sort. You can get some off-the-shelf MSB radix sort for sorting strings of arbitrary lengths here[0]. While this repository is mainly about parallel string sorts, I've found a version of this MSB radix sort that does not perform a bunch of unnecessary copies and caches more bytes at a time[1] to be competitive with the parallel sorts in the repo. In general MSB radix sort will have to look at the same parts of the input elements as multi-key quick sort, but one hopes that it gets to make fewer passes over the array. A comparator-based sort would look at about the same parts of the input elements as well, but it would look at them many times more than necessary. > Finally, it requires a sort-order-preserving transformation. I mentioned case-insensitive collation of Unicode strings as a well-known difficult problem. I do not believe there is mapping to an order-preserving representation which can be done bitwise. At the very least, it will be difficult to support all of the collation styles that currently exist (eg, French collation is different than Dutch). The requirements are a bit underspecified, but I think these can be solved by unicode normalization + tolower + codepoint-wise comparison, which is probably what you'd do in your comparator for a comparison-based sort as well. [0]: https://github.com/bingmann/parallel-string-sorting/blob/master/src/rantala/msd_a.hpp https://github.com/bingmann/parallel-string-sorting/blob/mas... [1]: https://github.com/dendibakh/perf-challenge6/blob/Solution_RobertBurke/wordcount.cpp#L474 https://github.com/dendibakh/perf-challenge6/blob/Solution_R...
      - eesmith 4y ago
        > for sorting strings of arbitrary lengths here Ahh, I see. It only loads CACHED_BYTES at a time. This could be used to delay the tie-breaking loads until needed, with some sort of on-the-fly encoding, and potentially skip those loads completely. I did not consider that. Thanks! You are right - my experience is with LSB radix sorts, most specifically the one in NumPy. I see it references https://github.com/eloj/radix-sorting#-key-derivation https://github.com/eloj/radix-sorting#-key-derivation which says "an LSB implemention is not well suited to sort character strings of any significant length. For those, a MSB radix sort is better" and in turn links to an implementation which includes benchmarks https://github.com/eloj/radix-sorting#cpp-benchmark https://github.com/eloj/radix-sorting#cpp-benchmark . It in turn cites Bingmann. Another thanks for pointing out a missing part of my understanding. The radix approach still requires a mapping to a byte representation which is order-preserving. > but I think these can be solved by unicode normalization + tolower + codepoint-wise comparison, which is probably what you'd do in your comparator for a comparison-based sort as well tolower() doesn't work for all collations. Quoting https://unicode.org/reports/tr10/ https://unicode.org/reports/tr10/ "Some dictionaries and authors collate uppercase before lowercase while others use the reverse ... Sometimes the case ordering is mandated by the government, as in Denmark." codepoint-wise comparison doesn't work for all collations. Quoting the same source, "There are additional complications in certain languages, where the comparison is context sensitive and depends on more than just single characters compared directly against one another" as well as "In some French dictionary ordering traditions, however, it is the last accent difference that determines the order".

timsort and pdqsort seem to be significantly slower than radix sort for random inputs, but presumably radix sort could also benefit from a pile of pattern-finding heuristics.

eesmith 4y ago

timsort and pdqsort (two comparison sort methods) and radix sort (a non-comparative sorting algorithm) have different albeit overlapping domains of applicability. Given a large number of 32-bit integers, radix sort is indeed significantly faster. While I would reach for a comparison sort method if I had a large number of arbitrary-length Unicode strings, which I wanted to sort in a case-ignoring order. Also, I found timsort faster than radix sort when there was a small number (as I recall, <100 or so) of elements.

anonymoushn 4y ago
> timsort and pdqsort (two comparison sort methods) and radix sort (a non-comparative sorting algorithm) have different albeit overlapping domains of applicability. Most comparators are of the form "compare by this, then if tied, compare by that, then if tied, compare by the other thing" which is pretty well suited to radix sort. You are correct though. > While I would reach for a comparison sort method if I had a large number of arbitrary-length Unicode strings, which I wanted to sort in a case-ignoring order. It seems like the radix sort is likely to be a lot faster for this too, mainly due to cache effects. If you have a dataset in mind I'll be happy to give it a shot. > Also, I found timsort faster than radix sort when there was a small number (as I recall, <100 or so) of elements. For sure. 100 isn't so far from the threshold where a radix sort should fall back to something else anyway.
- eesmith 4y ago
  > which is pretty well suited to radix sort Yes, the general approach is to convert the input data into a fixed-length bit-string with the same sort order as the input. Your example assumes that construction overhead is short. If tie-breaking is rare, and breaking the tie requires an expensive operation, then the trade-off point for radix might be much higher than 100 elements. The fixed-length requirement works well for small items with relatively equal-length fields. Ragged items, like Wikipedia titles, causes a problem. There is one title which is 253 bytes long. Now, Wikipedia titles are limited to 255 bytes, so radix is certainly directly applicable, but 1) it changes the trade-off point, and 2) reduces cache effects. Finally, it requires a sort-order-preserving transformation. I mentioned case-insensitive collation of Unicode strings as a well-known difficult problem. I do not believe there is mapping to an order-preserving representation which can be done bitwise. At the very least, it will be difficult to support all of the collation styles that currently exist (eg, French collation is different than Dutch).
  - anonymoushn 4y ago
    This is basically all incorrect. Maybe you are writing about LSB radix sort? I am writing about MSB radix sort. You can get some off-the-shelf MSB radix sort for sorting strings of arbitrary lengths here[0]. While this repository is mainly about parallel string sorts, I've found a version of this MSB radix sort that does not perform a bunch of unnecessary copies and caches more bytes at a time[1] to be competitive with the parallel sorts in the repo. In general MSB radix sort will have to look at the same parts of the input elements as multi-key quick sort, but one hopes that it gets to make fewer passes over the array. A comparator-based sort would look at about the same parts of the input elements as well, but it would look at them many times more than necessary. > Finally, it requires a sort-order-preserving transformation. I mentioned case-insensitive collation of Unicode strings as a well-known difficult problem. I do not believe there is mapping to an order-preserving representation which can be done bitwise. At the very least, it will be difficult to support all of the collation styles that currently exist (eg, French collation is different than Dutch). The requirements are a bit underspecified, but I think these can be solved by unicode normalization + tolower + codepoint-wise comparison, which is probably what you'd do in your comparator for a comparison-based sort as well. [0]: https://github.com/bingmann/parallel-string-sorting/blob/master/src/rantala/msd_a.hpp https://github.com/bingmann/parallel-string-sorting/blob/mas... [1]: https://github.com/dendibakh/perf-challenge6/blob/Solution_RobertBurke/wordcount.cpp#L474 https://github.com/dendibakh/perf-challenge6/blob/Solution_R...
    - eesmith 4y ago
      > for sorting strings of arbitrary lengths here Ahh, I see. It only loads CACHED_BYTES at a time. This could be used to delay the tie-breaking loads until needed, with some sort of on-the-fly encoding, and potentially skip those loads completely. I did not consider that. Thanks! You are right - my experience is with LSB radix sorts, most specifically the one in NumPy. I see it references https://github.com/eloj/radix-sorting#-key-derivation https://github.com/eloj/radix-sorting#-key-derivation which says "an LSB implemention is not well suited to sort character strings of any significant length. For those, a MSB radix sort is better" and in turn links to an implementation which includes benchmarks https://github.com/eloj/radix-sorting#cpp-benchmark https://github.com/eloj/radix-sorting#cpp-benchmark . It in turn cites Bingmann. Another thanks for pointing out a missing part of my understanding. The radix approach still requires a mapping to a byte representation which is order-preserving. > but I think these can be solved by unicode normalization + tolower + codepoint-wise comparison, which is probably what you'd do in your comparator for a comparison-based sort as well tolower() doesn't work for all collations. Quoting https://unicode.org/reports/tr10/ https://unicode.org/reports/tr10/ "Some dictionaries and authors collate uppercase before lowercase while others use the reverse ... Sometimes the case ordering is mandated by the government, as in Denmark." codepoint-wise comparison doesn't work for all collations. Quoting the same source, "There are additional complications in certain languages, where the comparison is context sensitive and depends on more than just single characters compared directly against one another" as well as "In some French dictionary ordering traditions, however, it is the last accent difference that determines the order".