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

"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(ps, qr))" 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