[SciPy-dev] Scipy-dev Digest, Vol 67, Issue 12

[Charles R Harris]

On Thu, May 7, 2009 at 12:30 PM, Andrew Schein <andrew at andrewschein.com>wrote:

> Date: Thu, 7 May 2009 11:49:08 -0600
>> From: Charles R Harris <charlesr.harris at gmail.com>
>> Subject: Re: [SciPy-dev] fast sorting of most numpy array types
>> To: SciPy Developers List <scipy-dev at scipy.org>
>>
>> Numpy has quicksort, mergesort, and heapsort and now and then someone on
>> the
>> 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
>> in
>> 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.
>

Good.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20090507/80f3b124/attachment.html>