[Python-Dev] Python3 regret about deleting list.sort(cmp=...)

[Paul Moore]

On 13 March 2011 03:00, Raymond Hettinger <raymond.hettinger at gmail.com> wrote:
>> But in Python 3 this solution is no longer available. How bad is that?
>> I'm not sure. But I'd like to at least get the issue out in the open.
>>
>
> Python3.2 should be substantially better in this regard.
> It no longer wraps key objects around every input.  Instead, it
> sorts two parallel arrays of pointers.   You can thank Daniel
> Stutzbach (another Googler I believe) for this effort.

For what it's worth:

PS D:\Data> D:\Apps\Python27\python.exe -m timeit -s "L = [(1,2),
(3,4), (0,5), (9,100), (3,7), (2,8)]" "sorted(L, lambda (p,q),(r,s):
cmp(p*s, q*r))"
100000 loops, best of 3: 5.19 usec per loop
PS D:\Data> D:\Apps\Python27\python.exe -m timeit -s "L = [(1,2),
(3,4), (0,5), (9,100), (3,7), (2,8)]" -s "from fractions import
Fraction" "sorted(L, key=lambda t: Fraction(*t))"
10000 loops, best of 3: 51.6 usec per loop
PS D:\Data> D:\Apps\Python27\python.exe -m timeit -s "L = [(1,2),
(3,4), (0,5), (9,100), (3,7), (2,8)]" -s "from fcomp import Fcomp"
"sorted(L, key=Fcomp)"
100000 loops, best of 3: 8.6 usec per loop
PS D:\Data> D:\Apps\Python32\python.exe -m timeit -s "L = [(1,2),
(3,4), (0,5), (9,100), (3,7), (2,8)]" -s "from fractions import
Fraction" "sorted(L, key=lambda t: Fraction(*t))"
10000 loops, best of 3: 64.4 usec per loop
PS D:\Data> D:\Apps\Python32\python.exe -m timeit -s "L = [(1,2),
(3,4), (0,5), (9,100), (3,7), (2,8)]" -s "from fcomp import Fcomp"
"sorted(L, key=Fcomp)"
100000 loops, best of 3: 8.41 usec per loop

This says to me that using Fraction as a key is substantially worse
(and worse still in 3.2 over 2.7). Using a custom key is closer to a
comparison function (but still 60-70% slower) and is marginally faster
in 3.2. Clearly, the nature of the key is critical here, so take this
with even more of a pinch of salt than you normally would with a
benchmark.

None of my real code is affected either way, but it seems to me that
the removal of the comparison function option was (sadly) a case of
purity being allowed to beat practicality. Luckily, adding it back
wouldn't be a backward compatibility issue :-) Whether it's worth
doing, I'll leave to those who would be doing the work to judge...

Paul.