> This is in response to what? Are you trying to talk me out of the pigeonhole principle? On Saturday, 16 November 2013 at 23:40:39 UTC, Andrei Alexandrescu wrote: Have you thought about ways to deal with that? You would also get absolutely horrible locality of While sorting just the pointers means moving things around less, This is sort of an interesting problem that you propose, because > Do we already have something like that available somewhere or is it possible to make one eventually? Obj1.foo > Of course, the programmer can choose any relevant member property to sort the collection. However, the algorithm woulnd't be so trivial to implement because each comparison shall be done using the Object's member's value : Because the swaps are done on the actual pointers (and not the Objects pointed), the Quicksort should be very efficient. The library would make possible, for example, to sort the `class objects` using one of their members as the key. > BTW I'm very interested in finding a library which could Quicksort an array of pointers, where each pointer points to a class object (or a structure) address. On Saturday, 16 November 2013 at 14:20:32 UTC, Jean Christophe In order to preserve stability, stable sorting algorithms need to do nonnegative extra work. This has nothing to do with it doing more work than an unstable sort that is just as nicely optimized.Īt the end of the day whatever stable sorting algorithms are out there, their set is included in the set of all sorting algorithms. I understand and appreciate that Timsort is a nicely optimized algorithm. > / Xinok/ XSort/blob/ master/ benchsort.d
CACHE XSORT AND QSORT SORT.CC CODE
> I decided to make a nice little test using my benchmark code here: This is in response to what? Are you trying to talk me out of the pigeonhole principle? > in many cases by exploiting patterns in the data. > There's something fishy about a more restricted algorithm doing better > On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei Alexandrescu wrote:
That's why I suggest making Timsort the default sorting algorithm. SwapRanges( base.arr], base.arr]) Īnd the results (last number is predicate calls): This is the permutation I designed for the test:Īuto arr = Xinok/ XSort/blob/ master/ benchsort.d I decided to make a nice little test using my benchmark code here: It's able to achieve better performance in many cases by exploiting patterns in the data. We must improve unstable sort, not make stable sort the default. > There's something fishy about a more restricted algorithm doing better than one that's less restricted. > cases in which it's faster and stable sorting isn't needed. Quick sort would still be available for those It's the better choice in many (most?) cases > * Regardless of these improvements, I think Timsort should be the On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei Alexandrescu wrote: Let's see if I can't get a pull request done by the end of the day. Quick sort would still be available for those cases in which it's faster and stable sorting isn't needed. It's the better choice in many (most?) cases and, well, it's stable. * Regardless of these improvements, I think Timsort should be the default sorting algorithm. My idea is to use this by default and specialize the linear insertion sort when the element type and predicate are known. It's about 15-20% slower when sorting an array of integers. This reduces comparisons as well but also adds a fair amount of overhead. * My solution uses a binary insertion sort for sublists up to 32 elements long. It adds nearly zero overhead and results in a noticeable decrease in comparisons (predicate calls). * It chooses the pivot from a median-of-five. * It's an introsort which falls back to a bottom-up binary heap sort after so many recursions to guarantee O(n log n) performance in the worst-case. Xinok/XSort/ blob/master/ unstablesort.d
Anyways, I posted a bug report about this problem long ago and a working solution has been gathering dust waiting to be implemented in Phobos. I'm a horrible procrastinator, I should have had this fixed over a year ago, lol. On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote:
0 kommentar(er)
