4 ms·
On C++ the tests I did two years ago showed that introsort was still the best "all around" algorithm for "uniformly distributed data". I also tested an algorith
by shin_lao 15y ago
On C++ the tests I did two years ago showed that introsort was still the best "all around" algorithm for "uniformly distributed data". I also tested an algorithm called Smoothsort that was supposed to work better for "almost sorted data" but in practice it was slower. Timsort might be a good candidate, although I wonder if the gain will translate to the C++ world.
What was surprising is that in hinting the compiler through template hacking I was able to squeeze a little more speed out of introsort (If you're interested: https://github.com/flexsortea/flex_sort https://github.com/flexsortea/flex_sort).
- JoachimSchipper 15y agoTimsort isn't intended for uniformly distributed data. In fact, I'm really surprised that quicksort didn't beat introsort in your tests - it may have some nasty edge cases, but you'll never hit those on truly random input and avoiding the (minimal) extra work of introsort should help.
- shin_lao 15y agoIntrosort only adds a depth check and size check to each recursion, that's only a couple of instructions with little memory access.
- jemfinch 15y agoTimsort optimizes for partially sorted data, but that's a long way from saying it's not intended for uniformly distributed data. It's intended for all data, that's why it's the default sort in Python. It's no less intended for all data than merge sort is. Even on random data, 50% of the time you'll pick a bad pivot. Get a slightly unlucky run and you're into quadratic behavior for that subset; the more data you're sorting, the more likely introsort's switch to heapsort on deep recursion (and insertion sort on small ranges) will help.
- JoachimSchipper 15y agoDid you ever actually time qsort? It's variability is nowhere near "it goes quadratic 50% of the time". Timings from http://www.joachimschipper.nl/posts/20111109/qsort_timing.c http://www.joachimschipper.nl/posts/20111109/qsort_timing.c (portable C, note the appended non-introspective qsort() implementation): qsort: 39 mergesort: 39 qsort: 38 mergesort: 40 qsort: 37 mergesort: 39 qsort: 38 mergesort: 40 qsort: 38 mergesort: 40 qsort: 38 mergesort: 40 qsort: 38 mergesort: 39
- jemfinch 15y agoDid you read my post? What I said was nowhere near "it goes quadratic 50% of the time". You're arguing against a straw man.
- CJefferson 15y agoI tried having a very quick dig through your code, but I couldn't actually see what you were doing. Could you perhaps post a quick description, and the gains you were seeing? I'm interested because if it isn't too hard it could always be ported into g++ / clang's libc++.
- shin_lao 15y agoIt should work to g++ easily, provided the usual "typename" adjustments. Basically I wrote each sort block as individual functors (partitioning, merging). You run that through a filter stack that decides what to do depending on the input size and the current recursion depth. It's faster (I think) because when the recursion depth is a compile-time value, the compiler can unroll the recursion. It's old code I wrote for Boost but never had the time to finish & submit. As I quickly read through it there's a couple of rough edges to polish.
- KaeseEs 15y agoFunction objects are not 'functor's. Please do not call them that. Functor is a word that has a specific meaning in category theory that winds up being relevant in some other programming languages (Haskell, ML and friends) and we don't need to shoot ourselves in the foot by overloading it with another meaning.
- shin_lao 15y agoA functor is another word for "function object". http://en.wikipedia.org/wiki/Function_object http://en.wikipedia.org/wiki/Function_object