Home Original page

[Python-ideas] Optimizing list.sort() by checking type in advance

Franklin? Lee leewangzhong+python at gmail.com
Sat Oct 15 00:15:08 EDT 2016 
On Mon, Oct 10, 2016 at 11:29 PM, Elliot Gorokhovsky
<elliot.gorokhovsky at gmail.com> wrote:
>> Note that when Python's current sort was adopted in Java, they still kept
>> a quicksort variant for "unboxed" builtin types.  The adaptive merge sort
>> incurs many overheads that often cost more than they save unless comparisons
>> are in fact very expensive compared to the cost of pointer copying (and in
>> Java comparison of unboxed types is cheap).  Indeed, for native numeric
>> types, where comparison is dirt cheap, quicksort generally runs faster than
>> mergesort despite that the former does _more_ comparisons (because mergesort
>> does so much more pointer-copying).
>
>
> Ya, I think this may be a good approach for floats: if the list is all
> floats, just copy all the floats into a seperate array, use the standard
> library quicksort, and then construct a sorted PyObject* array. Like maybe
> set up a struct { PyObject* payload, float key } type of deal. This wouldn't
> work for strings (unicode is scary), and probably not for ints (one would
> have to check that all the ints are within C long bounds). Though on the
> other hand perhaps this would be too expensive?

I happened onto a page talking about float radix sort, and thought of
this thread.

Here it is: http://stereopsis.com/radix.html
The author claimed an 8x speedup, though the test was done nearly
fifteen years ago.

I was unsure about posting publicly, because it's not as if an even
faster float sort would help decide whether specialized sorts are
worth adding to CPython. I'm posting for history.
More information about the Python-ideas mailing list