Home Original page

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

"Martin v. Löwis" martin at v.loewis.de
Sun Mar 13 03:29:10 CET 2011 
> [steve at sylar ~]$ python2.7 -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))"
> 10000 loops, best of 3: 25.1 usec per loop
>
> [steve at sylar ~]$ python2.7 -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))"
> 1000 loops, best of 3: 236 usec per loop
>
>
> So for a short list, I get a factor of ten difference. For a longer
> list, I'd expect the key function to win out. Much to my astonishment,
> it doesn't -- I get similar results regardless of the size of L.

This shouldn't be surprising. The cost is primarily in the comparisons,
not in the creation of the Fraction objects. Now, the number of
comparisons won't change whether you use a cmp function or key objects;
the algorithm will compare and switch the same objects in the same
order. So if a Fraction.__lt__ takes seven times as long as a cmp call,
this ratio is preserved even for very long lists.

A lot can be saved if the __lt__ would assume that the other object
is of the same kind:

class Fcomp(tuple):
     def __lt__(self, other):
         return self[0]*other[1] < self[1]*other[0]

python -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)"

Regards,
Martin
More information about the Python-Dev mailing list