<div class="gmail_quote">On Sat, Mar 12, 2011 at 9:17 PM, Terry Reedy <span dir="ltr"><<a href="mailto:tjreedy@udel.edu">tjreedy@udel.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">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.</div>
</blockquote></div><div><br></div><div>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:</div>
<div><br></div><div>max_denominator_sq = max(q for p, q in fraction_list) ** 2 # Strictly larger than the lcm between any pair</div><div>fraction_list.sort(key=lambda p, q: p*max_denominator_sq//q)</div><div><br></div><div>
Using the above, key is 4 times faster than cmp in Python2.6:</div><div><br></div><div><br></div><div>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))'</div>
<div><div><div>10 loops, best of 3: 23.3 msec per loop</div></div><div><br></div><div>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])'</div>
<div><div>100 loops, best of 3: 5.52 msec per loop</div></div></div><div><br></div><div><br></div><div>with a further speed improvement in 3.2:</div><div><br></div><div><br></div><div><div>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])'</div>
<div>100 loops, best of 3: 4.89 msec per loop</div></div><div><br></div><div><br></div><div>and more speed improvements with my experimental changes targeting 3.3 (not yet in the bug tracker): :-)</div><div><br></div><div>
<br></div><div><div>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])'</div>
<div>100 loops, best of 3: 3.73 msec per loop</div></div><div><br></div><div>-- <br>Daniel Stutzbach<br>
</div>