[SciPy-dev] Scipy-dev Digest, Vol 67, Issue 12
Charles R Harris
Thu May 7 14:30:03 CDT 2009
On Thu, May 7, 2009 at 12:30 PM, Andrew Schein <firstname.lastname@example.org>wrote:
> Date: Thu, 7 May 2009 11:49:08 -0600
>> From: Charles R Harris <email@example.com>
>> Subject: Re: [SciPy-dev] fast sorting of most numpy array types
>> To: SciPy Developers List <firstname.lastname@example.org>
>> Numpy has quicksort, mergesort, and heapsort and now and then someone on
>> list suggests adding radix sort. No doubt radix is suitable for certain
>> types, char arrays seem a natural. But there are problems with byte order
>> for the different integer types and floats can become complicated. And
>> unlike quicksort radix sort isn't done inplace. So it isn't clear that a
>> radix sort is the way to go for sorting in general but it could be useful
>> some places.
> Do you have some time results?
> Hi Charles -
> There are time results against glibc qsort() in the original post. The
> distribution of usort also provides an optimized quicksort with inlined
> comparisons and the capacity to test this against glibc. The "win" from
> inlining comparions is not as great as using radix sort.
> I have not timed against heap/merge sorts... since I believe these are
> slower on average on randomized inputs.
The three sorts cover three different needs: fast (quicksort),
guaranteed/stable (mergesort), guaranteed/inplace (heapsort).
> By byte order were you referring to endianess of different architectures?
> This could be a deal breaker as the code is written.
Yep. Note that the actual code is generated when numpy is built so you might
be able to work around this.
> The usort library already consists of in-place routines.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Scipy-dev