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

[Daniel Stutzbach]

On Sat, Mar 12, 2011 at 9:17 PM, Terry Reedy <tjreedy at udel.edu> wrote:

> But in this case, they are much slower. To be faster, one would need
> something like "key=lambda p,q:p*(lcm//q)", where lcm is the least common
> multiple of of all the q's (denominators). For the example above, lcm = 700.
> But for longer lists, it could be outrageously large.
>

You can get away with less precision.  It's okay if the key function loses
some information, as long as it still has enough to distinguish each pair of
numbers.  In other words, you just need a number that's at least as large as
the largest lcm between any pair:

max_denominator_sq = max(q for p, q in fraction_list) ** 2  # Strictly
larger than the lcm between any pair
fraction_list.sort(key=lambda p, q: p*max_denominator_sq//q)

Using the above, key is 4 times faster than cmp in Python2.6:


stutzbach-glaptop:~$ python2.6 -m timeit -s 'fractions = [(i, j) for i in
range(100) for j in range(1, 100)]'  'sorted(fractions, cmp=lambda
(p,q),(r,s): cmp(p*s, q*r))'
10 loops, best of 3: 23.3 msec per loop

stutzbach-glaptop:~$ python2.6 -m timeit -s 'fractions = [(i, j) for i in
range(100) for j in range(1, 100)]' 'max_denominator_sq = max(q for p, q in
fractions)**2' (1,2), (3,4), (0,5), (9,100), (3,7), (2,8)'sorted(fractions,
key=lambda t: t[0]*max_denominator_sq//t[1])'
100 loops, best of 3: 5.52 msec per loop


with a further speed improvement in 3.2:


stutzbach-glaptop:~$ ~/python/cpython-3.2/python -m timeit -s 'fractions =
[(i, j) for i in range(100) for j in range(1, 100)]' 'max_denominator_sq =
max(q for p, q in fractions)**2' 'sorted(fractions, key=lambda t:
t[0]*max_denominator_sq//t[1])'
100 loops, best of 3: 4.89 msec per loop


and more speed improvements with my experimental changes targeting 3.3 (not
yet in the bug tracker):   :-)


stutzbach-glaptop:~$ ~/python/cpython/python -m timeit -s 'fractions = [(i,
j) for i in range(100) for j in range(1, 100)]' 'max_denominator_sq = max(q
for p, q in fractions)**2' 'sorted(fractions, key=lambda t:
t[0]*max_denominator_sq//t[1])'
100 loops, best of 3: 3.73 msec per loop

-- 
Daniel Stutzbach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20110313/1fc253e3/attachment.html>