Thread overview | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
February 05, 2007 Sorting an array | ||||
---|---|---|---|---|
| ||||
When I use array.sort, which sorting algorithm does D use? Can the programmer overwrite the implementation of this function? Thanks! |
February 06, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Michiel | "Michiel" <nomail@hotmail.com> wrote in message news:eq8bim$2gou$1@digitaldaemon.com... > When I use array.sort, which sorting algorithm does D use? Can the > programmer > overwrite the implementation of this function? > > Thanks! DMD at least uses quicksort. You can find the actual source for it in /dmd/src/phobos/internal/qsort2.d. You can see that it just calls the C stdlib qsort() function. If you want to use a different algorithm, you'd have to change this file and recompile phobos. A daunting task.. |
February 06, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jarrett Billingsley | Jarrett Billingsley wrote: > "Michiel" <nomail@hotmail.com> wrote in message news:eq8bim$2gou$1@digitaldaemon.com... >> When I use array.sort, which sorting algorithm does D use? Can the programmer >> overwrite the implementation of this function? >> >> Thanks! > > DMD at least uses quicksort. You can find the actual source for it in /dmd/src/phobos/internal/qsort2.d. You can see that it just calls the C stdlib qsort() function. > > If you want to use a different algorithm, you'd have to change this file and recompile phobos. A daunting task.. > > I thought it used a quicksort with insertion sort for the smallest arrays. In fact such a beast seems to be in dmd/src/phobos/internal/qsort.d. Are you sure arrays use the qsort2.d implementation? --bb |
February 06, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Bill Baxter | "Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:eq8iau$2s4p$1@digitaldaemon.com... > > I thought it used a quicksort with insertion sort for the smallest arrays. > In fact such a beast seems to be in dmd/src/phobos/internal/qsort.d. > Are you sure arrays use the qsort2.d implementation? There's apparently some licensing issues with qsort.d? I'm not entirely sure, but.. well to be honest I'm not sure whether it uses qsort.d or qsort2.d. I shouldn't have jumped to that conclusion. Looking at the phobos makefile it seems to use qsort.d, but qsort2.d is also mentioned. Either way, it's probably not the fastest, as I wrote a templated _recursive_ quicksort (not even using a stack like the one in qsort.d) that consistently outperforms the builtin one by 5~10% (on my computer at least). |
February 06, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jarrett Billingsley | Jarrett Billingsley wrote:
> "Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:eq8iau$2s4p$1@digitaldaemon.com...
>> I thought it used a quicksort with insertion sort for the smallest arrays.
>> In fact such a beast seems to be in dmd/src/phobos/internal/qsort.d.
>> Are you sure arrays use the qsort2.d implementation?
>
> There's apparently some licensing issues with qsort.d? I'm not entirely sure, but.. well to be honest I'm not sure whether it uses qsort.d or qsort2.d. I shouldn't have jumped to that conclusion. Looking at the phobos makefile it seems to use qsort.d, but qsort2.d is also mentioned.
>
> Either way, it's probably not the fastest, as I wrote a templated _recursive_ quicksort (not even using a stack like the one in qsort.d) that consistently outperforms the builtin one by 5~10% (on my computer at least).
>
>
Yeh, I can believe that. qsort2 calls the TypeInfo.compare method to do its dirty work. It probably does not ever get inlined. Whereas a templated version can usually inline the compare away.
Funny, that's the #1 thing that Stroustrup has been jumping up and down about for years. It's the first thing he pulls out whenever someone says C++ is slow. No no! He says, look at std::sort! Faster than C's qsort() could ever even hope to be!
--bb
|
February 06, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Michiel | Michiel wrote: > When I use array.sort, which sorting algorithm does D use? Can the programmer > overwrite the implementation of this function? Just write a library replacement[1]. The only difference is that it will have to be called as: array.sort() instead of array.sort The advantages are several. It will be faster than the built in sort and you will have the possibility of making it support custom ordering predicates and more. IMHO, the built in .sort and .reverse properties(?) should be removed as identical in syntax and infinitely more flexible library implementations are possible. For a sample implementation, see my old and dusty std.array proposal: http://www.csc.kth.se/~ol/array.d Ugly DDoc: http://www.csc.kth.se/~ol/array.html it includes: array.sort() array.sort(predicate wrongOrder) array.stableSort() array.stableSort(predicate wrongOrder) And in-place versions: array.doSort() array.doSort(predicate wrongOrder) array.doStableSort() array.doStableSort(predicate wrongOrder) I believe it still compiles, but no guarantees as it was written for DMD 0.149 or thereabouts. /Oskar |
February 06, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Oskar Linde | Oskar Linde wrote:
> Michiel wrote:
>> When I use array.sort, which sorting algorithm does D use? Can the programmer
>> overwrite the implementation of this function?
>
> Just write a library replacement[1]. The only difference is that it will have to be called as:
>
> array.sort() instead of array.sort
>
> The advantages are several. It will be faster than the built in sort and you will have the possibility of making it support custom ordering predicates and more. IMHO, the built in .sort and .reverse properties(?) should be removed as identical in syntax and infinitely more flexible library implementations are possible.
For what it's worth, Tango contains a sort routine in tango.core.Array. In the brief testing I've done performs roughly the same as the built-in sort routine. It's a modified version of quicksort, and I found that using insertion sort for small ranges (as the built-in sort does) had no measurable effect on performance so I didn't bother with the additional complexity.
Sean
|
February 07, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jarrett Billingsley | Jarrett Billingsley wrote:
> If you want to use a different algorithm, you'd have to change this file and recompile phobos. A daunting task..
make -fwin32.mak
Really. I do it all the time :)
L.
|
February 08, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lionello Lunesu | "Lionello Lunesu" <lio@lunesu.remove.com> wrote in message news:eqcv8j$8gs$1@digitaldaemon.com... > Jarrett Billingsley wrote: >> If you want to use a different algorithm, you'd have to change this file and recompile phobos. A daunting task.. > > make -fwin32.mak > > Really. I do it all the time :) > > L. I always get all kinds of errors.. unless it's changed since 0.170 or so. I end up having to manually change a bunch of stuff in the makefiles and in the directory tree to get it to work right. |
February 08, 2007 Re: Sorting an array | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jarrett Billingsley | Jarrett Billingsley wrote:
> "Lionello Lunesu" <lio@lunesu.remove.com> wrote in message news:eqcv8j$8gs$1@digitaldaemon.com...
>> Jarrett Billingsley wrote:
>>> If you want to use a different algorithm, you'd have to change this file and recompile phobos. A daunting task..
>> make -fwin32.mak
>>
>> Really. I do it all the time :)
>>
>> L.
>
> I always get all kinds of errors.. unless it's changed since 0.170 or so. I end up having to manually change a bunch of stuff in the makefiles and in the directory tree to get it to work right.
It has changed, in fact. I've posted the issues a while back in bugzilla and Walter has addressed them all. I'm not sure about linux though, but building phobos for windows has never been easier.
L.
|
Copyright © 1999-2021 by the D Language Foundation