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

[Bernardo Sulzbach]

On 10/10/2016 03:18 AM, Elliot Gorokhovsky wrote:
> Hi,
>
> I posted here a while back asking what you guys thought about
> implementing radix sort for strings in list.sort(). You gave me a lot of
> reasons why that would be a bad idea. However, it got me thinking, and I
> came up with something that you may find interesting.
>
> First, some simple benchmark results (numbers are seconds, check out the
> extension module at https://github.com/embg/python-fast-listsort.git):
>
> *** 1e3 ints ***
> F.fastsort(): 0.00018930435180664062
> F.sort(): 0.0002830028533935547
> *** 1e3 strings ***
> F.fastsort(): 0.0003533363342285156
> F.sort(): 0.00044846534729003906
> *** 1e7 ints ***
> F.fastsort(): 5.479267358779907
> F.sort(): 8.063318014144897
> *** 1e7 strings ***
> F.fastsort(): 9.992833137512207
> F.sort(): 13.730914115905762
>

The numbers are good. How does this interfere with sorting very small 
lists? Obviously, even if it does not help with very small lists, we can 
always put a threshold on the size and take this path or not.

-- 
Bernardo Sulzbach
http://www.mafagafogigante.org/
mafagafogigante at mafagafogigante.org